RichardBerg: Nachos Lab 1 - The trouble with concurrency

Nachos Lab 1 - The trouble with concurrency

Ways to produce incorrect behavior with yields

Append & Prepend: List Construction Error

If a yield is placed in the if(empty) section then only the item the last thread is adding will be added. This occurs because Thread 1 will yield to Thread 2 while leaving a value in temporary memory; it will be overwritten, then this new value inserted into the list when it yields back. In particular, given the usual list of natural numbers, only the odd numbers will be added while the others are forgotten.

Append & Prepend: List Truncation Error

Similarly, a yield can be placed in the else clause where the main functionality of the append/prepend operation takes place. Since the threads will alternate continuously, every element will be dropped except when the last one is finally assigned. That is, each element is copied into memory, but is forgotten before it is written to the list because the other thread overwrites it (and then yields again).

Sorted Remove: Dangling Reference Error

 TestListElement *element = first;   
 void *thing;
 if (IsEmpty()) 
	return NULL;
***    currentThread->Yield();   // should lead to dangling references
 thing = first->item;

When inserting and deleting a list of 6 elements, with the yields placed after every insert and delete for two threads, the debugging output shows that the first and last element in the list was deleted once and all other elements were deleted twice. However, this is due to the yield statement. At first, the pointer, element, is initialized to point to the first element in the list for both threads. Once it yields back to Thread 1, the first item is deleted correctly. But then the program yields to Thread 2. Thread 2 still thinks that it should delete "element." "element" has already been deleted by Thread 1, and the call is made to delete "element" again by Thread 2. This does not cause the program to crash due to the dangling reference. However, SortedRemove returns that element->next was deleted. It never really was. This causes the doubling up of deletions in the debugging statement. The reason the first and last elements in the list were only deleted once is because Thread 2 was not able to assign "thing" to equal the first element in the initial list; by the time Thread 2 reaches thing=first->next, Thread 1 has already removed the original first element due to yielding. Additionally, the last element in the debugging output shows up as being deleted once because Thread 2 reaches the list when there is only one element left before Thread 1 does and subsequently deletes it.

Sorted-Remove: Deleting from an empty list

The same yield above will, in certain situations, cause a thread to attempt a deletion from an empty list, which leads to a segmentation fault. This problem arises when there is an unequal number of items inserted (and deleted) by each thread (eg. inserting and then deleting 10 items, using 3 threads). The problem occurs as follows: assume that our list has only two elements remaining. As is seen with the above dangling reference problem, only the first thread to run will actually delete and element, thus moving the "first" pointer. When it finishes and yields to the second thread, however, the test if(first=last) now evaluates as true, so each of these pointers are set to null, removing the final item. However, when this thread finishes, it yields to the third thread, which will attempt to make the assignment "thing=first->item," and since first is now null, this will cause a segmentation fault (deleting from an empty list).

Segmentation Fault in Sorted-Insert Function

In the function Sorted-Insert, the first if statement checks to see if the list is empty. If it is, the first and last values are assigned to those of the inserted item. However, if a yield is placed in between these two assignments, a segmentation fault occurs. This happens because the first thread to insert a value will enter the if statement an assign the "first" value. However, it yields to the second thread before it assigns the "last" value. The second thread then runs, but unlike the first, it does not find the list to be empty because the "first" value has already been assigned. it then moves tot he end of the function and tries to assign a value to last->next. However, because "last" has not been assigned yet, a seg fault occurs.

Deadlock Error in Sorted-Insert Function

When a yield is placed at the beginning of the for loop in the Sorted Insert Function, the two threads will eventually reach a state in which neither can move forward, or a deadlock.

The first time each thread runs, they will work fine because neither will enter the for loop, "k" will be incremented properly, and the first two items will be inserted into the list properly. However, when the first thread enters the for loop when it tries to insert the next item, it will yield to the second thread before it does anything except assign the "ptr" value. The second thread does the same. The first thread then moves "ptr" to the next value, which is the last one. Normally, it would then break out of the for loop and add a value to the end of the list. However, it is forced to yield to the second thread before it can do so. So, the second thread breaks out of the loop and adds the value to the end of the list. When it yields back to the first thread (after incrementing k), the first thread no longer has "ptr" pointing to the last value since a new item has been added. It moves ptr to the last value, but then has to yield to the second thread again. But now the second thread has updated k, so it will skip the for loop and add a value to the end of the list. This process continues until the second thread has inserted all of the values; the first thread is stuck in the loop while the second keeps inserting values.

Now, the second thread hits the yield in between insert and remove. This allows the first thread to break out of the for loop and insert a value onto the list. However, the second thread moves into the loop in threadtest2.cc for the remove function while the first thread is still inside the loop for inserting values.

The second thread will remove a value from the front of the list and yield. However, when it does so, it alters the value of "k" when it returns. The first thread will continue to try to increment k, but each time it does so, it yields back to the second thread which removes a value and changes k again. Now, the two threads are deadlocked; the second thread keeps removing the first value of the list, and when it does so, the value it returns makes the first thread insert the same element back into the front of the list.

Sorted-Insert - Inserting out of order

 else {		
            for (ptr = first; ptr->next != NULL; ptr = ptr->next) {
            if (sortKey < ptr->next->key) {
                currentThread->Yield(); 
                element->next = ptr->next;
                ptr->next = element;
		return;
	    }
        }

With the above yield in the function SortedInsert, it is possible to insert items out of order (by sortKey) if one attempts to insert a series of elements between two other elements. For example, suppose we have two threads inserting some items into our list, which is only (sortKeys only here) 12->15->NULL at the moment. Say the first thread begins inserting an item with sortKey 13. It will traverse the code in SortedInsert until it yields to the second thread (whereupon ptr=12 and ptr->next=15). Then the second thread begins inserting an item with sortKey 14. Likewise, it will enter the for loop (whereupon ptr=12 as well) and then yield to the first thread. The first thread then completes the insert, so 12->13->15->NULL is our current list, and then yields to the second thread, still trying to insert 14. However, since ptr=12 and ptr->next is now 13, the second thread will insert 14 before 13, so the final order of the list is 12->14->13->15->NULL.

NOTE: This problem will only arise if k is incremented before the InsertSorted call in threadtest2.cc. Otherwise only duplicates of every other item will be inserted.

Sorted-Insert - Lost Insertions

If a yield is places as such in the function SortedInsert:

else {		
        for (ptr = first; ptr->next != NULL; ptr = ptr->next) {
            if (sortKey < ptr->next->key) {
                element->next = ptr->next;
                currentThread->Yield(); 
                ptr->next = element;
		return;
            }
      }

it can lead to skipped insertions, or "forgotten" items when trying to insert a series of items between two others. For example, assume we have a list consisting only of items with sortKeys 10 and 15. (So our list looks somewhat like 10->15->NULL.) Now we have two threads, and each is supposed to insert an item with a distinct key (12 for the first, 14 for the second). The first thread runs, calls SortedInsert, but only gets as far as element->next = ptr->next, so the insertion is not complete when it yields to the second thread. So after each thread yields once, the list will still look like 10->15->NULL, but there will be items with keys 12 and 14 both pointing at 15. Then the first thread runs again and ptr->next=element, so 10->12->15->NULL. It then yields to the second thread, which also makes the assignment ptr->next=element, making the list look like 10->14->15->NULL. So, while the element with key 12 still points to 15, it is effectively lost or forgotten.

Back to OperatingSystems

RichardBerg : NachosLab1

Nachos Lab 1 - The trouble with concurrency