This shows you the differences between two versions of the page.
Both sides previous revision Previous revision Next revision | Previous revision | ||
cs330_f2016:lab14 [2016/11/15 18:36] morse |
cs330_f2016:lab14 [2021/06/30 23:42] (current) |
||
---|---|---|---|
Line 1: | Line 1: | ||
- | ** This version is preliminary and subject to change until this line is removed ** | ||
====Objective:==== | ====Objective:==== | ||
Line 34: | Line 33: | ||
For the mark-and-sweep part of the assignment, you should fill in the state of the heap after the marking phase and again after the sweep phase. | For the mark-and-sweep part of the assignment, you should fill in the state of the heap after the marking phase and again after the sweep phase. | ||
- | During marking, start with the root set and traverse out in a recursive depth-first fashion marking each block that can be eventually reached. | + | During the marking phase, start with the root set and traverse out in a recursive depth-first fashion marking each block that can be eventually reached. |
- | During the sweep phase, turn all unmarked blocks until free blocks by labeling them as such, storing the length of the free block, and storing a pointer to the next free block. All newly freed blocks should be added at the head of the free list. | + | During the sweep phase, turn all unmarked blocks into free blocks by labeling them as such, storing the length of the free block, and storing a pointer to the next free block. |
+ | All newly freed blocks should be added at the head of the free list. **You must have a free list stored within the heap itself!** | ||
===Stop and Copy=== | ===Stop and Copy=== | ||
+ | |||
+ | For the stop-and-copy part of the assignment, you are given the initial fromspace, which is identical to the original heap for the mark-and-sweep part. | ||
+ | However, the interpretation is slightly different: for mark-and-sweep, you have to identify blocks as free and maintain a free-block list. | ||
+ | For stop-and-copy, there are no free blocks or a list of such. Instead, all memory above the single free pointer is unused and can be allocated. | ||
+ | |||
+ | During collection, the stop-and-copy method copies live objects from the fromspace to the tospace. | ||
+ | (You can just do this manually by copying blocks from the fromspace and pasting them to the tospace.) | ||
+ | **You must use Cheney's algorithm as discussed in class, which means there is a set order in which the live objects must be copied to the tospace.** | ||
+ | |||
+ | First copy the objects in the root set over to the tospace, | ||
+ | then begin scanning these objects. | ||
+ | As you encounter a pointer, you copy that object to the tospace and make sure to do both of the following: | ||
+ | - update the pointer you just scanned, and | ||
+ | - leave a forwarding address in the fromspace should you revisit that object again. | ||
+ | |||
+ | Continue this process until you've scanned everything that's been copied over and the scan pointer catches up with the free pointer. | ||
---- | ---- | ||
- | ===Hints:=== | + | ====Notes:==== |
+ | |||
+ | - Address 0 is intentionally not used and a reference with value = 0 should be taken as a NULL pointer. | ||
+ | - Use the "Interpretation" column for your own notes, but all necessary information must be in the heap contents, not this column! | ||
+ | |||
+ | ---- | ||
+ | |||
+ | ====Hints:==== | ||
+ | |||
+ | Since both methods should result in the same set of live objects, try comparing which blocks still remain after each approach. The order in which they appear in memory will be different, but the set of live objects should be the same. | ||
+ | |||
+ | |||
+ |