No longer valid in 2019
Pintos Laboratory Assignment 2: Timers, Threads, Interrupts and Synchronization
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:
- Basic interrupt management.
- A first introduction to threads switching.
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.
- What is busy waiting? Why should the programmer avoid busy waiting in a concurrent operating system?
- Explain difference between Yield and Sleep.
- What is the difference between locks and semaphores? (Hint: there are two main differences). What is a deadlock?
- What is the purpose of conditions? Explain how deadlock situations can be avoided with conditions.
Assignments in detail
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
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
In this part of the lab, you need to re-implement
If the thread calls
timer_sleep() then its execution is suspended for (at least)
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
or write your own list implementation.
Note, that the argument to
timer_sleep is provided in
ticks, not in milliseconds. The macro
how many ticks there are per second (defined in
In your implementation you may modify other functions or add your
own code in
timer.h files. Note, that
the functions similar to
timer_sleep(), therefore there is no need to modify them.
To test your implementation you may run make SIMULATOR=--qemu check from the
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.:
pintos --qemu -- run alarm-simultaneous
Note, that these tests will also pass at the very beginning because the current implementation of
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:
|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
Next Laboratory work
Page responsible: Mikael Asplund
Last updated: 2020-08-21