Problem Set #1: Virtual Timers

Objective

One of the important functions of an operating system is to virtualize resources in order to simplify their sharing among multiple users/processes. Virtualization involves simulating multiple abstract instances of a resource on a single underlying instance. The users are unaware that they are sharing a single resource; each process "sees" its own private copy.

The purpose of this assignment is for you to consider how virtualization is achieved using the mechanisms available to a modern OS. You are to design data structures and algorithms to implement virtual timers based on a single underlying hardware timer. Your design could become the component of a real operating system.

The Hardware Timer

Suppose the hardware of a computer system includes a single timer. The timer can be set to expire after a specified number of "ticks." When the timer expires, an interrupt is generated to transfer control to the address of the timer interrupt service routine.

The operation of the timer is controlled by two privileged instructions. READTMR reads the current value of the timer; SETTMR loads the timer with a given value. Whenever the timer contains a non-zero value, it is automatically (by the hardware) decremented at each tick. If the timer is decremented to zero an interrupt is generated, and the timer stops. The timer generates no other signals of any kind. The value of the timer can be reset while the timer is running (with SETTMR). It can even be set to zero, which stops the timer but does not generate an interrupt.

The Virtual Timers

The OS provides a virtual timer to any process that requests it. A process can execute a system call set_timer(number_of_ticks) where number_of_ticks specifies the number of ticks that are to pass before the process is notified that its timer has expired. Once a process calls set_timer, it may not call set_timer again until the (virtual) timer has expired. That is, a process has no way to cancel its timer once it has been set. There is no limit on the number of processes and therefore no upper bound on the number of virtual timers that may be in use at any given instant.

The Assignment

Explain how the operating system can use the single hardware timer to implement multiple virtual timers. Your solution to the problem should include the following:

1. a description of the data structure(s) used.
2. pseudo-code for the set_timer system call.
3. pseudo-code for the interrupt service routine that receives control when the hardware timer expires.
4. a basic analysis of the time complexity of your routines. You should strive for efficiency in both execution time and storage requirements. Interrupt handlers, particularly, must be fast.

You do not need to explain how interrupts work or what processes will do with their virtual timers. Your solution should have enough detail to convince me that you could do a complete implementation, or better yet, that someone else could implement your design while you are away on vacation. You can assume that the person doing the implementing understands various common data structures and their implementation. You can also ignore any other operating system tasks that might actually have to use the hardware timer (such as process scheduling). This assingment is just about virtualizing one simple resource to make it available to many processes.

Bonus Assignment

If you think you have found an efficient solution to the basic assingment, consider the slightly more advanced problem of allowing a process to change its timer midstream. That is, it can turn it off by calling set_timer(0), or simply change the amount of time by supplying a new positive value.