In this assignment you are supposed to get acquainted with some of 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.
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.
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.
Your task is to re-implement function timer_sleep() which is located in
devices/timer.c
. The purpose of this function is to
make a calling process delay for a given time (sleep). The current
implementation uses a busy-waiting strategy: it is
calling thread_yield() and checking the current time in a
loop until enough time has gone by. Obviously, this is not acceptable:
processor time is a very valuable resource and must not be wasted in
busy waiting.
In this part of the lab, you need to re-implement timer_sleep(int64_t ticks).
If the thread calls timer_sleep() then its execution is suspended for (at least) ticks
ticks. In case there are no other running threads (that is, if the system is idle),
then the thread should be awaken after exactly ticks ticks. You should not preempt
other processes if there are any running after the time has passed by, but rather
put our process into the ready-to-run queue and leave the decision when it should
be executed to the scheduler.
Hint: Implement a queue for sleeping processes. You can use
either original list from Pintos distribution
(lib/kernel/list.[c|h]
),
or write your own list implementation.
Note, that the argument to timer_sleep is provided in
ticks, not in milliseconds. The macro TIMER_FREQ defines
how many ticks there are per second (defined in
devices/timer.h
).
In your implementation you may modify other functions or add your
own code in
timer.c
and timer.h
files. Note, that
the functions similar to timer_sleep():
timer_msleep()timer_usleep()timer_nsleep()timer_sleep(), therefore there is no need to modify
them.
To test your implementation you may run make SIMULATOR=--qemu check from the threads/build
directory.
There are a number of tests:
timer_sleep() function in different ways. You may run (and debug if necessary) one test at
a time, e.g.:
timer_sleep() is
correct, although it is using busy waiting.
Hint: If you add code inside "threads" in lab 1, protect it with the following:
#ifdef USERPROG
..
#endif
| Code directories: | linuxpintos/src/threads, linuxpintos/src/devices |
| Textbook chapters: | Chapter 1.5.2: Timer Chapter 3.2: Process Scheduling Chapter 6.2: The Critical-Section Problem Chapter 6.5: Semaphores Chapter 6.6.1: The Bounded-Buffer Problem |
| Documentation: | Pintos documentation, and in particular:
Some parts of Project 1 Synchronization Interrupt Handling |