CS460 Takehome Midterm Exam #4 DUE:9/28/2023 Submit a ZIP file with mk 2. Timer Service With a hardware timer, e.g. timer0, the OS kernel can provide each process with a virtual timer. A process may request an interval timer of t seconds by the command 't', which asks for a time value in t seconds. The 't' command causes the process to sleep for t seconds. When its requested time expires, the timer interrupt handler wakes up the process, making it ready to run again. The timer requests of processes are maintained in a timer queue containing Time Queue Elements (TQEs), which looks like the following: tq -> tqe -> tqe -> tqe -> NULL ------ ------ ------ | 5 | | 8 | | 17 | (time in seconds to expire) | *2 | | *1 | | *3 | (*pid means &proc[pid]) ------ ------ ------ At each second, the timer interrupt handler decrements the time field of each TQE by 1. When a TQE's time decrements to 0, the interrupt handler deletes its TQE from tq and wakes up the process. For example, after 5 seconds, it deletes the tqe of PROC2 and wakes up process P2. In the above timer queue, the time field of each TQE contains the exact time remaining. The disadvantage of this scheme is that the interrupt handler must decrement the time field of each and every TQE. In general, an interrupt handler should complete an interrupt processing as quickly as possible. This is especially important for timer interrupt handler. Otherwise, it may loss ticks or even never finish. In contrast, when a process enters a timer request, it also manipulates the timer queue but the process does not have the same kind of critical time constraints. We can speed up the timer interrupt handler by modifying the timer queue as follows. tq -> tqe -> tqe -> tqe -> NULL ------ ------ ------ | 5 | | 3 | | 9 | (relative time) | *2 | | *1 | | *3 | (pointer to proc[pid]) ------ ------ ------ In the modified timer queue, the time field of each TQE is relative to the cummulative time of all the preceeding TQEs. At each second, the timer interrupt handler only needs to decrement the time of the first TQE and process any TQE whose time has expired. With this setup, insertion/deletion of a TQE must be done carefully. REQUIREMENT: Implement a timer queue to support interval timer requests of processes. When a process runs, ask for a time value, e.g. proc 1 running, enter a timer value : (enter 20) enter a TQE into the timer queue with 20 seconds; process goes to sleep (e.g. on address of its proc or TQE) Modify the timer interrupt handler to: dispaly a wall clock AND the current timer queue every second; handle TQEs and wake up any process whose time has expired; When the system starts, kfork serveral processes, e.g. P1, P2, P3, P4, P5. Then switch to P1. For each process, enter a timer request, e.g. P1: 30 // P1 sleep, switch to P2 P2: 20 // P2 sleep, switch to P3 P3: 5 // P3 sleep, switch to P4 P4: 10 // P4 sleep, switch to P5 Display timerQueue each second, and wakeup proc whose time has expired. SAMPE solution: samples/MID4/mid4.bin