[2022] WWU - CSCI 447 - Operating Systems - Assignment2: Threads and Synchronization
CSCI 447 - Operating Systems, Spring 2022
Assignment 2: Threads and Synchronization
Due Date: Tuesday, April 12, 2022 Points: 125
1 Overview and Goal
In this assignment you will review threads and gain more experience writing programs involving concurrency control. You will begin by studying the thread package, which implements multithreading.
You will make modifications and additions to the existing code. Then you will use the threads package to solve several concurrency problems.
In addition, you will gain familiarity programming in the KPL language.
If you have difficulties with this assignment or want to go into more depth, take a look at
the document called ”The Thread Scheduler and Concurrency Control Primitives”:
http://facultyweb.cs.wwu.edu/ phil/classes/blitz/BlitzDoc/ThreadScheduler.htm
http://facultyweb.cs.wwu.edu/ phil/classes/blitz/BlitzDoc/ThreadScheduler.pdf
2 Download the Files
Start by creating a new branch in your gitlab project named “a2”. Checkout the new branch and then create a directory named “a2”.
% git branch a2
% git checkout a2
% mkdir a2
Then download all the files from:
http://facultyweb.cs.wwu.edu/ phil/classes/s22/447/a2
into your directory. You should get the following files:
makefile
DISK
System.h
System.k
Runtime.s
Switch.s
List.h
List.k
Thread.h
Thread.k
Main.h
Main.k
Synch.h
Synch.k
Game.h
Game.k
In this assignment, you will modify and hand in the following files:
Main.k
Synch.h
Synch.k
Game.h
Game.k
After getting the files, you should be able to compile all the code (as is) with the UNIX make command. The program executable we are building will be called ”os”. You can execute the first program by typing:
% make
% blitz -g os
It also builds the file ”game” that can be executed in a similar way. In the course of your experimentation, you may modify other files besides Synch.h, Synch.k, Main.k, and Game.*, but the code you are required to write and turn in doesn’t require any changes to the other files other than Synch.h, Synch.k, Main.k, and Game.*. For example, you may wish to uncomment some of the print statements, to see what happens. However, your final versions of the files you change must work with the other files, exactly as they are distributed.
Be sure you copy all files. Even though there are similarities with some of the files used for assignment 1, there may be some subtle but important differences.
When adding files to the a2 branch, make sure you do not add any .o files or any executibles, e.g. os and game. All distributed files should be added to your git project before any changes have been made to the files.
Once you have the initial files in your a2 directory and committed, you should push the new branch to gitlab.
% git push --set-upstream origin a2
3 Study the Existing Code
The code provided in this assignment provides the ability to create and run multiple threads,
and to control concurrency through several synchronization methods.
Start by looking over the System package. Focus on the material toward the beginning of
file System.k, namely the functions:
print
printInt
printHex
printChar
printBool
nl
MemoryEqual
StrEqual
StrCopy
StrCmp
Min
Max
printIntVar
printHexVar
printBoolVar
printCharVar
printPtr
Get familiar with the printing functions; you’ll be calling them a lot. Some are implemented in assembly code and some are implemented in KPL in the System package.
The following functions are used to implement the heap in KPL:
KPLSystemInitialize
KPLMemoryAlloc
KPLMemoryFree
Objects can be allocated on the heap and freed with the alloc and free statements. The HEAP implementation is very rudimentary in this implementation. In your kernel, you may allocate objects during start-up but after that, YOU MUST NOT ALLOCATE OBJECTS ON THE HEAP! Why? Because the heap might fill up and then what is a kernel supposed to do? Crash.
In this assignment, you should not allocate anything on the heap.
The following functions can be ignored since they concern aspects of the KPL language that
we will not be using:
KPLUncaughtThrow
UncaughtThrowError
KPLIsKindOf
KPLSystemError
The Runtime.s file contains a number of routines coded in assembly language. It contains the program entry point and the interrupt vector in low memory. Take a look at it. Follow what happens when program execution begins at location 0x00000000 (the label ” entry”). The code labeled ” mainEntry” is included in code the compiler produces. The ” mainEntry” code will call the main function, which appears in the file Main.k.
In Runtime.s, follow what happens when a timer interrupt occurs. It makes an ”up-call” to a routine called P Thread TimerInterruptHandler. This name refers to ”a function called TimerInterruptHandler in a package called Thread.” ( P Thread TimerInterruptHandler is the name the compiler will give this function.)
6 Implement the ”Mutex” Class (30 points)
In this part, you must implement the class Mutex. The class specification for Mutex is given to you in Synch.h:
class Mutex
superclass Object
methods
Init ()
Lock ()
Unlock ()
IsHeldByCurrentThread () returns bool
endClass
You will need to provide code for each of these methods. In Synch.k you’ll see a behavior construct for Mutex. There are methods for Init, Lock, Unlock, and IsHeldByCurrentThread, but these have dummy bodies. You’ll need to write the code for these four methods.
You will also need to add a couple of fields to the class specification of Mutex to implement the desired functionality.
How can you implement the Mutex class? Take a close look at the Semaphore class; your implementation of Mutex will be quite similar.
First consider the IsHeldByCurrentThread method, which may be invoked by any thread. The code of this method will need to know which thread is holding a lock on the mutex; then it can compare that to the currentThread to see if they are the same. So, you might consider adding a field (perhaps called heldBy) to the Mutex class, which will be a pointer to the thread holding the mutex. Of course, you’ll need to set it to the current thread whenever the mutex is locked. You might use a null value in this field to indicate that no thread is holding a lock on the mutex.
When a lock is requested on the mutex, you’ll need to see if any thread already has a lock on this mutex. If so, you’ll need to put the current process to sleep. For putting a thread to sleep, take a look at the method Semaphore.Down. At any one time, there may be zero, one, or many threads waiting to acquire a lock on the mutex; you’ll need to keep a list of these threads so that when an Unlock is executed, you can wake up one of them. As in the case of Semaphores, you should use a FIFO queue, waking up the thread that has been waiting longest.
When a mutex lock is released (in the Unlock method), you’ll need to see if there are any threads waiting to acquire a lock on the mutex. You can choose one and move it back onto the readyList. Now the waiting thread will begin running when it gets a turn. The code in Semaphore.Up does something similar.
It is also a good idea to add an error check in the Lock method to make sure that the current thread asking to lock the mutex doesn’t already hold a lock on the mutex. If it does, you can simply invoke FatalError. (This would probably indicate a logic error in the code using the mutex. It would lead to a deadlock, with a thread frozen forever, waiting for itself to release the lock.) Likewise, you should also add a check in Unlock to make sure the current thread really does hold the lock and call FatalError if not. You’ll be using your Mutex class later, so these checks will help your debugging in later assignments.
The function TestMutex in Main.k is provided to exercise your implementation of Mutex. It creates 7 threads that compete vigorously for a single mutex lock.
7 Implement the Producer-Consumer Solution (30 points)
Your textbook, Silberschatz, et al., contains a discussion of the Producer-Consumer problem, including a solution. Implement this in KPL using the classes Mutex and Semaphore. Deal with multiple producers and multiple consumers, all sharing a single bounded buffer.
The Main package contains some code that will serve as a framework. The buffer is called buffer and contains up to BUFFER SIZE (e.g., 5) characters. There are 5 producer processes, each modeled by a thread, and 3 consumer processes, each modeled by a thread. Thus, there are 8 threads in addition to the main thread that creates the others.
Each producer will loop, adding 5 characters to the buffer. The first producer will add five ’A’ characters, the second producer will add five ’B’s, etc. However, since the execution of these threads will be interleaved, the characters will be added in a somewhat random order.
This is an important exercise for you to understand. It is the basis for the solution to implementing pipes in assignment 7.
8 Implement the Dining Philosopher’s Solution Using a Monitor
(15 points)
A starting framework for your solution is provided in Main.k. Each philosopher is modeled with a thread and the code we’ve provided sets up these threads. The synchronization will be controlled by a ”monitor” called ForkMonitor.
The code for each thread/philosopher is provided for you. Look over the PhilosophizeAndEat method; you should not need to change this code.
The monitor to control synchronization between the threads is implemented with a class called ForkMonitor. The following class specification of ForkMonitor is provided:
class ForkMonitor
superclass Object
fields
status: array [5] of int -- For each philosopher: HUNGRY,
-- EATING, or THINKING
methods
Init ()
PickupForks (p: int)
PutDownForks (p: int)
PrintAllStatus ()
endClass
You’ll need to provide the code for the Init, PickupForks and PutDownForks methods. You’ll also need to add additional fields and perhaps even add another method.
The code for PrintAllStatus is provided. You should call this method whenever you change
the status of any philosopher. This method will print a line of output, so you can see what is
happening.
