A Methodology for Implementing Highly Concurrent Data Structures

Q1:
The sequential procedures have to manipulate the concurrent objects using a functional style: instead of modifying the object in place, they must compute and return a distinct version of the object.

---

Q2:
A process that wants to manipulate an object initially marks it as frozen. A new object is then initialized to contain the result object of the operation and is added to an abort set (to be freed if the operation fails). The old one is added to a commit set (to be freed if the operation succeeds). After a critical compare-and-swap, the original object is unfrozen and then, depending on the result every element of either the commit set or the abort set is unfrozen. Freezing and unfreezing simply increases or decreases a counter denoting number of readers on the object.

Q1:
The sequential procedures have to make a new copy of all changed data blocks and change the copy instead of changing the data structure in place. They also need to return a pointer to the resulting data structure.

---

Q2:
A small object is an object that can be stored in a fixed size memory block. The resulting concurrent procedure get a root pointer to the address of the current location of the small object. The concurrent procedure first call the sequential version of the procedure to get a new manipulated copy of the small object. The resulting procedure then tries to change the root pointer from the old value to the address of the new manipulated copy of the small object with an atomic compare&swap instruction. If the compare&swap instruction succeeds the procedure can complete, otherwise the value of the root pointer is read again and the procedure is retried with the new root pointer. Allocation and deallocation of memory blocks could be handled by automatic garbage collection or by the procedures alloc and free described in the paper.

Q1: The procedures must be pure functions, that is, they must not modify the object, but instead return a new copy of the object, with the operation applied.

---

Q2: Each call to the sequential procedure is replaced with the following:

1. Take a private copy of the object to modify
2. Apply the sequential procedure on the private copy
3. Use CAS to replace the old object with the new

The procedure is repeated until the CAS succeeds.

Memory is managed by keeping a pool of objects, and attaching a usage counter to each object, which is zero when the object is unused. To allocate an object, the pool is search until an object whose pointer is 0 is found. To deallocate an object, its counter is decreased.

The use counter is increased for all accessed objects, and three sets are used for book-keeping which objects need to be released again for different situations:
frozen_set: accessed objects that should always be released
commit_set: objects that should be released if the CAS succeeds
abort_set: objects that should be released if the CAS fails

Q1: They must be written in a functional style.

---

Q2:

• Copy the structure that global pointer p points at.
• Update local copy.
• Try to update p so that it points to local copy, using CAS. If failure, retry from start.

Q1: The sequential operations must be implemented in a "functional style". Thus, such an operation on an object is not allowed to change the state of the object.

---

Q2: The small word protocol starts off with a pointer to the initial shared object (the root-pointer). The block that is pointed to by the root pointer is "frozen", such that it cannot be modified by another process until it is unfrozen. It then performs the serial operation, achieving a new pointer to the modified object and attempts to compare-and-swap the modified object into the shared object. If the CAS was succesful, we are done (after some unfreezing and tidying up). Otherwise, the whole procedure is repeated until success.

Q1: They must be written such that any operation that changes the object state returns a new, different copy of the object instead of modifying it in-place.

---

Q2:

• Freeze the block that contains the object's current version
• Create new copy of the object (w/ sequential operation)
• Try compare-and-swap to replace the frozen object with the new copy. If it succeeds, we're happy; otherwise try again from the beginning.

Q1
The sequential functions must be in a functional style which means that they are not allowed to change the object's state in place and instead
they should create a new version of that object, change its state and then return it to the calling procedure.

---

Q2
According to Small Object Protocol, a sequential procedure (seq_proc) can be transformed to a concurrent one as follows:

result = freeze(object)
IF result == OK THEN

execute the seq_proc

IF object's state has changed after this operation THEN
perform CAS(old,new) to swap the old and new versions of the object
END IF

END IF
unfreeze all frozen blocks
IF CAS succeeded THEN

unfreeze all freed blocks

ELSE

unfreeze all allocated blocks

END IF

Q1
The sequential procedures must be written in a functional style, which means an operation must change compute the object and return a new version of it instead of changing the object in place.

---

Q2

• Freeze the root pointer of the object
• Execute the sequential operation and create a new object
• Apply CAS to replace the old object with the new one and the procedure loops until CAS suceeds.

Q1
"They must written in a functional style - an operation that changes the object state is not allowed to modify the object in place, instead it must compute and return a (logically) distinct version of the object."

---

Q2
On a high level, the algorithm is to first create a local copy of the altered object, and then tries to compare-and-swap the pointer of the original copy used to a pointer to the changed object. This will fail, if another process changed the original object in the meantime (and succeeded), then requireing a restart of the operation. As at least one concurrent process will always succeed with the compare-and-swap, progress for the system as a whole is guaranteed.

Q1
They must be written in a functional style.

---

Q2
1: freeze the root pointer of the object
2: call sequential operation
3: if the state of the object changed, try to exchange the old version of the object with the new one
4: if success: unfreeze object in its commit_set or its abort_set
else: goto 1
5: reset privat data structures

Q1: Copy the data (locally) if you want to update them.

---

Q2: Retry-loop

1. copy the data locally
2. update the local copy
3. check and commit the changes (or loop if the check fails)