IT-Programmet, Tema 1 i termin 4:
TTIT61 Processprogrammering och Operativ System/Concurrent Programming and Operating Systems/
NachosThroughout all lab assignments in TTIT61 you will use an emulated operating system called Nachos (Not Another Completely Heuristic Operating System).
Instead of running immediately on top of hardware, like normal operating systems, Nachos runs as a single process in a real operating system. In our case, Nachos will be a simple program running on Solaris. Nachos does not manage the real hardware. Instead it emulates a MIPS processor (MIPS is an old processor). The "user programs" that Nachos runs are MIPS binaries. The instructions in the MIPS binaries are interpreted Nachos and executed on the emulated processor.
It is analogous to Java binary code and Java Virtual Machine.
SetupYou can download the code skelleton together with some documentation from here: nachos-3.4.tar.gz. Unpack the archive:
During this assignment, you will work in the directory
Give it a try:
The purpose of this lab is to give you an understanding of synchronisation mechanisms such as locks, semaphores, condition variables, and monitors.
Semaphores are already implemented. You will have to implement locks and condition variables. The corresponding code has to be written in
As a code writing methodology, I would recommend that you recompile each time you add a function or variable declaration to a header file, and after every 5-10 new lines of code that you add. I strongly discourage the method in which you write all your assignment and compile only once at the end. Even experienced programmers would get tens of errors in these cases.
Recompiling is done by invoking
Once you implemented the required functionality, you will have to test it. The test application consists of eight concurrent threads that compete for access on a buffer with a capacity of 20 integer elements. Five threads are producers, while three threads are consumers. Initially the buffer is empty.
The functionality of the producer is the following: If the buffer is not full, the producer appends an element (an arbitrary integer, could be given by the function
The functionality of the consumer is the following: If the buffer is not empty, the consumer removes the last element in the buffer (which is also the freshest element in the buffer, the most recently produced). The removal is done by calling the method
A skelleton for this functionality is given in
Only the skelletons of
RunningYou will run your program in two variants.
In the first variant, Nachos does not capture the time interrupt and does not preempt threads. Thus, we would have "co-operative multitasking", just that our threads do not co-operate. That means that they run until they are forced to stop (they block), they do not voluntarily relinquish the processor. (They block because of adversary conditions, i.e. the producer blocks because the buffer is full, the consumer blocks because the buffer is empty. Thus, if correctly implemented, your program should not deadlock. At least one thread must be running because the buffer cannot be both empty and full at the same time.) In the case of co-operative multitasking, the buffer occupancy should vary as follows: 0, 1, 2, ..., 19, 20, 19, 18, ..., 1, 0, 1, 2, ..., 19, 20, 19, 18, ...
The first variant is run by executing
In the second variant, Nachos captures the time interrupt and preempts the running threads whenever a random time interrupt arrives. Thus, we would have "preemptive multitasking". In this case, the buffer occupancy does not necessarily vary anymore from empty to full, then to back to empty, and so on, but rather oscillates somewhere in between.
The second variant is run by executing
Lab 1: Timers, Threads, Interrupts and Synchronization
In this assignment you are supposed to get acquainted with, probably, the most important mechanisms of operating systems such as timers, threads, interrupts, and, last but not least, synchronization primitives. Proper functioning of any concurrent operating system is simply impossible without them.
This assignment covers:
This lab intends to teach the basics of synchronization, starting from the thread concurrency which is achieved via thread switching triggered by the timer interrupt, through basic synchonization primitives, and, finally, finishing with patterns of thread synchronization.
In the first part you should implement timer_sleep function. Second part is devoted to synchronization.
Pintos uses three synchronization primitives: semaphores, locks and conditions. All of them are already implemented. You should fully understand how they work before you start using them.
The course book provides only little information about Locks and Conditions. However, Locks and Conditions together form the same functionality as monitors and you can find some information about that in the book. You might want to look at the DIGITAL report: An Introduction to Programming with Threads (remark: The report uses the term "mutex" where Pintos uses "lock").
To test your implementation of the primitives you will construct your own synchronized datatype - a bounded buffer. This gives you valuable insight into constructing such datatypes, which you will benefit from in the following labs. You will use primarily locks and conditions.
Using synchronization primitives you have to implement BoundedBuffer that is a circular structure with three counters: head, tail, and count. Let X be a buffer size. Initially, all counters are set to 0. As the item is added to the buffer, counters head and count are incremented. As the item is removed from the buffer the counter tail is incremented but count is decremented. Once head or tail reach X, they have to be made equal to 0 (and can be further incremented). If tail == head and count == 0, it means that the buffer is empty. If tail == head and count == X, it means that the buffer is full.
To run the test, you need to have more than one thread, so this is a good time to have a first look at the Pintos thread and scheduling subsystem. Threads are not very hard to use in Pintos, and a simple scheduling system is already implemented for you to use.
Before you begin doing your lab assignment you have to answer on the following set of questions to ensure that you are ready to continue.
Assignments in detail
Part A: Optional
Your task is to re-implement function
In this lab you will need to modify a set of functions in
In this part of the lab, you need to re-implement
Hint: Implement a queue for sleeping processes. You can use
either original List from Pintos distribution
Note, that the argument to
In your implementation you may modify other functions or add your
own code in
DO NOT re-program the (hardware) timer itself!
To test your implementation you may run gmake SIMULATOR=--qemu check from the
pintos --qemu -- run alarm-simultaneous
Note, that these tests will also pass at the very beginning because the current implementation of
Your task is to write the code for BoundedBuffer data structure that is
not included in the distribution (actually, the stub for the structure and the
corresponding functions is provided in file
In a bounded buffer you must handle two conditions: the case of an empty buffer and a full buffer. If the buffer becomes empty, all the reading processes must wait until something is put into the buffer. If the buffer becomes full, all the writing processes must wait until some place is freed by reading processes.
Before you start, you should look at the
The next step is to study throughfully an example how locks and conditions are used together.
Let us consider a list structure SynchList, which does not allow reading in case of list being empty.
The condition ConditionEmpty is needed to make a process, which tries to read from the empty list, wait until some other process writes something to the list. ListLock provides mutual exclusion such that only one process can access list at a time.
More implementation details you can find in the files
Use as an internal data structure for BoundedBuffer a simple array. Create this array upon initialization of BoundedBuffer, passing a buffer size as an argument. Make sure that counters work as expected before implementation of synchronization (a piece of paper and a pencil should help when examining your source code).
Once you have implemented BoundedBuffer, you need to re-compile Pintos by typing gmake from
The current code already contains an example of how to start up two threads in
Now you can run Pintos from
Next Laboratory work
Sidansvarig: Sergiu Rafiliu
Senast uppdaterad: 2011-09-12