Seite 1 von 1

Weak References Questions

Verfasst: 25. Mai 2015 18:59
von Tai

I have some further questions about the WeakRef Interpreter in the assignment 06. I've completed all spec tests, but i wrote some own tests that aren't working correctly with the interpreter implementation.

Code: Alles auswählen

  //Common code
  val emptyEnv: Env = Map()
  val emptyStack: List[Env] = emptyEnv :: Nil
1. Overwritten values with WeakRef

Code: Alles auswählen

  val st3 = new MarkAndSweepStore(3)
  val (res, _) =interp(Let('ref, WeakRef(1), Let('ref2, WeakRef(10), TryDeref('ref2, 42))), emptyStack,st3)
  println(res) // => WeakRefV(2) but should be 42
The first call (Let('ref, WeakRef(1), ...) leads to => STORE = ArraySeq(NumV(1), WeakRefV(0), null)
Within the second call (Let('ref2, WeakRef(10), ...) stores now the value 2 => STORE = ArraySeq(NumV(1), WeakRefV(0), NumV(10))
and after that it stores the WeakRef-Pointer, but the store is full, so it GC will be applied. During that, our index number 2 will be marked for deletion, because we have no pointer towards it.
So the NumV(2) entry will be deleted and WeakRef(2) will be inserted (because the NumV(10) is at position 2, originally)

TryDeref('ref2, 42) finds for 'ref2 -> WeakRef(2) => That is WeakRef(2) itself and returns it.

Possible solutions:
- check if two free spaces are available before inserting any Ref

2. Overwritten values with WeakRef || How to delete old WeakRefV || GC with old WeakRefV

Code: Alles auswählen

  val st2 = new MarkAndSweepStore(2)
  val (res5, _) =interp(Let('ref, WeakRef(1), Let('ref2, WeakRef(10), Let('ref3, WeakRef(100),TryDeref('ref3, 42)))), emptyStack,st2)
Leads for me to an infinite loop (the variable free is inconsistent with the actual memory, because of the value overwriting problem (see 1.)).
My question is, how we can implement/change the GC that it is more robust to such programs?

My first idea would be to change malloc(stack, value) to malloc(size, stack, value), but is this the only way?

Cheers T.

Re: Weak References Questions

Verfasst: 25. Mai 2015 23:34
von IvaToteva

The scenario your examples outline is a valid one. However, you don't need to handle such cases in this homework assignment.

Normally, mark-and-sweep garbage collectors do not wait until the whole memory is filled in. There is a quota, and when the number of allocated memory cells exceeds the quota, garbage collection is triggered. Thus, in practice being exactly 1 cell short of memory is not a common case. There are also probably some heuristics for determining when garbage collection should be triggered, e.g. when a method returns and all local variable used in its body can be released.

As for our garbage collector, there are different ways of ensuring that garbage collection will not introduce such invalid states in the memory:
1. As you suggested - verifying the presence of at least two empty cells before inserting a weakly referenced object in the store
2. Marking the newly added weak referenced object, so that it is not possible to delete it until the weak reference to it is also added to the store - e.g. by passing the location in the store that should not be garbage collected
3. Noting that garbage collection has occurred in the process of evaluating a WeakRef (through some boolean flags for example) and thus using WeakRefV(INVALID_LOC) directly
4. Increasing the memory on demand.

As for your second example, it should not run into an infinite loop. WeakReferences must not be deleted until they are in scope. The program should run in an out-of-memory exception.


Re: Weak References Questions

Verfasst: 26. Mai 2015 00:47
von Tai

thank you for your long answer.

I found the problem with the infinite loop.
The problem was the following:
In the GC process I was using free before the update, i just had to swap these two lines.

Here's the sequence of my old implementation that leads to this problem

Code: Alles auswählen

inserting 1
ArraySeq(NumV(1), null) 
inserting Ref
ArraySeq(NumV(1), WeakRefV(0))
inserting 10
ArraySeq(null, WeakRefV(-1)) // GC, removes WeakRefV(0), free size = 1
ArraySeq(NumV(10), WeakRefV(-1))
inserting Ref
ArraySeq(null, WeakRefV(-1)) // GC, removes unused NumV(10), free size = 1
ArraySeq(WeakRefV(0), WeakRefV(-1))
inserting 100
ArraySeq(null, WeakRefV(-1)) // GC, removes WeakRefV(0) index => (0) => itself, free size = 1 
ArraySeq(WeakRefV(-1), WeakRefV(-1)) //GC sets the WeakRefV to -1, free size doesn't get changed because of an update, free size = 1
inserting 100 leads to an infinite loop because every space was != null and free size > 0