CST334 - Week 28

This week we began to study the topic of concurrency. The readings introduced the topic of threads, which are an abstraction for a running process. In a multithreaded program, threads share an address space and heap memory, while they each have their own program counter, registers, and stack. Sometimes, within a thread, there is a piece of code, called the critical section, that we would like to execute atomically, all or nothing. Thus, we wish to provide mutual exclusion, along with fairness so that each thread has a chance to run and will avoid starvation, as well as keeping the cost of performance in mind. A solution is to create a lock variable and place it around the critical section in the code. This lock will keep track if any process owns it at that point in time and will tell whether the lock is available or acquired, only allowing one thread at a time to hold the lock and enter the critical section. Spin locks, using the test-and-set instructions, provide mutual exclusion but may lead to starvation. Ticket locks, using the fetch-and-add instructions, will guarantee that each thread will progress. In order to minimize spinning and thus wasting the CPU time, a thread can call yield(), which gives up the CPU to another thread. Another idea is to put waiting threads on a queue to sleep until a lock is free and wakes up the next thread. When dealing with data structures, one can take a more coarse-grained approach by locking the entire structure, or a fine-grained approach like locking a part of it such as one node in a linked list. Sometimes a thread wants to check if a certain condition is true before executing; that's where condition variables come in. Threads can be put on a queue and wait on a condition, waking when some other thread changes its state and signals the condition. This week's lab instructed students to write a program that multiplies matrices using different threads in order to implement what we have learned.