The programming project is to implement timer, timer interrupts and interval timers in a multitasking system with concurrent executing tasks. The programming project consists of four steps. Step 1 provides the base code of a multitasking system for the reader to get started. Step 2 is to add timer and timer interrupts to the base system. Step 3 is to implement interval timers for tasks. Step 4 is to implement Critical Regions in the system and task scheduling by time-slice. The object of the project is for the reader to learn not only how to use timers but also how they are implemented in an OS kernel.
1. System Base Code
The base code of the multitasking system is essentially the same as the programming project on user- level threads of Chap. 4. For ease of reference and completeness, we repeat the same code here. The following lists the base code of a multitasking system. It consists of a ts.s file in 32-bit assembly and a t.c file in C.
#———— ts.s file ————–
.global tswitch, scheduler, running
tswitch:
SAVE: pushal
pushfl
movl running, %ebx
movl %esp, 4(%ebx)
FIND: call scheduler
RESUME: movl running, %ebx
movl 4(%ebx), %esp
popfl
popal
ret
/********* t.c file *********/
#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include <string.h>
#include <sys/time.h>
#define NPROC 9
#define SSIZE 1024
// PROC status
#define FREE 0
#define READY 1
#define SLEEP 2
#define BLOCK 3
#define PAUSE 4
#define ZOMBIE 5
typedef struct proc{
struct proc *next;
int ksp; // saved sp when NOT running
int pid; // task PID
int priority; // task priority
int status; // status=FREE|READY, etc.
int event; // sleep event
int exitStatus;
int joinPid;
struct proc joinPtr;
int time; // time slice in ticks
int pause; // pause time in seconds
int stack[SSIZE]; // per task stack
}PROC;
PROC proc[NPROC]; // task PROCs
PROC *freeList, *readyQueue, *running;
PROC *sleepList; // list of SLEEP tasks
PROC *pauseList; // list of PAUSE tasks
#include “queue.c” // same queue.c file as before
#include “wait.c” // tsleep, twakeup, texit, join functions
int menu() // command menu: to be expanded later
{
printf(“*********** menu ***********\n”);
printf(“* create switch exit ps *\n”);
printf(“***********************^****\n”);
}
int init()
{
int i, j;
PROC *p;
for (i=0; i<NPROC; i++){
p = &proc[i];
p->pid = i;
p->priority = 1;
p->status = FREE;
p->event = 0;
p->next = p+1;
}
proc[NPROC-1].next = 0;
freeList = &proc[0]; // all PROCs in freeList
readyQueue = 0;
sleepList = 0;
pauseList = 0;
// create P0 as initial running task
running = dequeue(&freeList);
running->status = READY;
running->priority =0; // P0 has lowest priority 0
printList(“freeList”, freeList);
printf(“init complete: P0 running\n”);
}
int do_exit() // task exit as FREE
{
printf(“task %d exit: “, running->pid);
running->status = FREE;
running->priority = 0;
enqueue(&freeList, running);
printList(“freeList”, freeList); tswitch();
}
int do_ps() // print task status
{
printf(“——– ps———- \n”);
printList(“readyQueue”, readyQueue);
printList(“sleepList “, sleepList);
printf(“———- \n”);
}
int create(void (f)(), void *parm) // create a new task
{
int i;
PROC *p = dequeue(&freeList); if (!p){
printf(“create failed\n”);
return -1;
}
p->ppid = running->pid;
p->status = READY;
p->priority = 1;
for (i=1; i<12; i++)
p->stack[SSIZE-i] = 0;
p->stack[SSIZE-1] = (int)parm;
p->stack[SSIZE-2] = (int)do_exit;
p->stack[SSIZE-3] = (int)f;
p->ksp = &p->stack[SSIZE-12];
enqueue(&readyQueue, p);
printf(“%d created a new task %d\n”, running->pid, p->pid);
return p->pid;
}
void func(void *parm) // task function
{
char line[64], cmd[16];
printf(“task %d start: parm = %d\n”, running->pid, parm);
while(1){
printf(“task %d running\n”, running->pid);
menu();
printf(“enter a command line: “);
fgets(line, 64, stdin);
line[strlen(line)-1] = 0; // kill \n at end of line
sscanf(line, “%s”, cmd);
if (strcmp(cmd, “create”)==0)
create((void *)func, 0);
else if (strcmp(cmd, “switch”)==0)
tswitch();
else if (strcmp(cmd, “exit”)==0)
do_exit();
else if (strcmp(cmd, “ps”)==0)
do_ps();
}
}
int main()
{
int i;
printf(“Welcome to the MT multitasking system\n”);
init();
for (i=1; i<5; i++) // create tasks
create(func, 0);
printf(“P0 switch to P1\n”);
while(1){
if (readyQueue)
tswitch();
}
}
int scheduler()
{
if (running->status == READY)
enqueue(&readyQueue, running);
running = dequeue(&readyQueue);
printf(“next running = %d\n”, running->pid);
}
Fig. 5.2 Sample outputs of the base MT system
The reader may consult Chap. 4 for the create() function, which creates a new task to execute a specified function. To compile and run the base system under Linux, enter
gcc -m32 t.c ts.s # assembly code ts.s is for 32-bit Linux
Then run a.out. When a task runs, it displays a command menu, where the commands are
create: create a new task
switch: switch task
exit : task exit
ps : show status of tasks
Figure 5.2 shows the sample outputs of running the base code of the multitasking system.
2. Timer Interrupts
Step 2 The entire base system runs on a virtual CPU, which is a Linux process. Timer generated signals to the Linux process can be regarded as interrupts to the virtual CPU of the base system. Create a REAL mode interval timer for the Linux process. Program the interval timer to generate a SIGALRM signal every 10 msec. Install a SIGALRM signal catcher as the timer interrupt handler of the virtual CPU. In the timer interrupt handler, keep track of the number of seconds, minutes and hours elapsed. The needed extension code segments are shown below.
void thandler(int sig)
{
// count the number of timer ticks; update ss, mm, hh
// print a message every second
}
signal(SIGALRM, thandler); // install SIGALRM catcher
struct itimerval t; // configure timer
t.it_value.tv_sec = 0;
t.it_value.tv_usec = 10000; // start in 10 msec
t.it_interval.tv_sec = 0;
t.it_interval.tv_usec = 10000; // period = 10 msec
setitimer(ITIMER_REAL, &t, NULL); // start REAL mode timer
The outputs of Step 2 should be similar to Fig. 5.2, except it displays a message on each second.
3. Timer Queue
Step 3 Add interval timer support for tasks in the base system. Add the commands
pause t: task pauses for t seconds
timer t: task sets an (REAL mode) interval timer of t seconds
The pause command causes a task to go to sleep for the specified number of seconds, which will be woken up when the pause time expires. After setting an interval timer, the task may continue, which will be notified by a signal when its timer expires. Since the MT system can not generate and send signals yet, we shall assume that the task will go to sleep after executing the timer command, which will be woken up when its timer expires.
As pointed out in Sect. 5.7, the system must use a timer queue to keep track of the status of REAL mode timers of tasks. The timer queue consists of TQE (Timer Queue Element) entries of the form
The TQEs may be allocated and deallocated from a pool of TQEs. Since each process can have only one REAL mode timer, the number of TQEs is at most equal to the number of PROCs. If desired, they can be included in the PROC structure. Here we assume that the TQEs are allocated/deallocated dynamically from a pool of free TQEs. When a process requests a REAL mode interval timer, a TQE is allocated to record the requesting process, the expiration time, and the action to take when the timer expires. Then it enters the TQE into the timerQueue. The simplest timerQueue is a link list ordered by non-decreasing expiration time. If there are many requests for REAL mode timers, such a timerQueue may look like the following diagram, in which the numbers represents the expiration time of the TQEs.
timerQueue = TQE1 ->TQE2 ->TQE3
2 7 15
At each second, the (hardware) timer interrupt handler decrements each and every TQE by 1. When a TQE’s time decrements to 0, it is removed from the timerQueue and the action function invoked. The default action is to generate a SIGALRM(14) signal to the process, but it may also be other kinds of actions. In general, a (hardware) interrupt handler should run to completion as quickly as possible. The drawback of the above timerQueue organization is that the timer interrupt handler must decrement each and every TQE by 1, which is time-consuming. A better way is to maintain the TQEs in a cumulative queue, in which the expiration time of each TQE is relative to the cumulative sum of all the expiration time of preceding TQEs. The following shows a cumulative timerQueue, which is equivalent to the original timerQueue.
timerQueue = TQE1 ->TQE2 ->TQE3
2 5 8
With this organization of the tiemrQueue, the timer interrupt handler only needs to decrement the first TQE and handle any TQE whose time has expired, which greatly speeds up the timer interrupt processing.
Step 3 of the project is to add a REAL mode interval timer for the Linux process and implement interval timers for tasks in the MT system.
Figure 5.3 shows the sample outputs of running such a system. As the figure shows, task1 requested a timer of 6 seconds. Task 2 requested a timer of 2 seconds, 4 seconds after that of task 1. At this moment, the cumulative timerQueue contents are shown as
timerQueue = [2, 2] =>[1, 2]
In each TQE, the first number is the task PID and the second number is the expiration time. At each second, the timer interrupt handler only decrements the first TQE of task 2. When the TQE of task 2 expires, it deletes the TQE from the timerQueue and wakes up task 2. After these, the TQE of task 1 will be the first one in the timerQueue. On the next second, it will decrement the TQE of task 1.Similarly, the pause command allows a task to pause for t seconds, which will be woken up when its pause time expires.
Fig. 5.3 Sample outputs of task interval timers
4. Critical Regions
In the base code system, there is only one kind of execution entities, namely tasks, which execute one at a time. A task keeps executing until is gets a switch command, goes to sleep or exits. Furthermore, task switch occurs only at the end of an operation, but never in the middle of any operation. Therefore, there are no competitions among tasks, hence no Critical Regions in the base code system. However, the situation changes once we introduce interrupts to the system. With interrupts, there are two kinds of execution entities, tasks and interrupt handler, which may compete for the same (shared) data objects in the system. For example, when a task requests an interval timer, it must enter the request as a TQE into the timerQueue. While a task is modifying the timerQueue, if a timer interrupt occurs, it would divert the task to execute the interrupt handler, which may modify the same timerQueue, resulting in a race condition. Thus, the timerQueue forms a Critical Region, which must be protected to ensure it can only be accessed by one execution entity at a time. Likewise, while a process is executing in the middle of the sleep() function, it may be diverted to execute the interrupt handler, which may execute wakeup(), trying to wake up the process before it has completed the sleep operation, resulting in yet another race condition. So the problem is how to prevent task and interrupt handler from interfering with each other.
Step 4: Implementation of Critical Regions
When an interrupt handler executes, the task is logically not executing, so tasks can not interfere with interrupt handler, but the reverse is not true. While a task executes, timer interrupts may occur, which divert the task to execute the interrupt handler, which may interfere with the task. In order to prevent this, it suffices for the executing task to mask out interrupts in Critical Regions. As pointed out before, the MT multitasking system runs on a virtual CPU, which is a Linux process. To the MT system, timer interrupts are SIGALRM signals to the Linux process. In Linux, signals other than SIGKILL(9) and SIGSTOP(19) can be blocked/unblocked by the following means.
- sigset_t sigmask, oldmask; // define signal mask sets
- sigemptyset(&sigmask); // initialize signal mask set to empty
- sigaddset(&sigmask, SIGALRM);// add signal numbers to the set
- To block signals specified in the mask set, issue the system call
sigprocmask(SIG_BLOCK, &sigmask, &oldmask);
- To unblock signals specified in the mask set, issue the system call
sigprocmask(SIG_UNBLOCK, &sigmask, &oldmask);
- For convenience, the reader may use the following functions to block/unblock
signals
int_off(){ sigprocmask(SIG_BLOCK, &sigmask, &oldmask);}
int_on(){ sigprocmask(SIG_UNBLOCK, &oldmask, &sigmask); }
Step 4 of the programming project is to use sigprocmask() of Linux to block/unblock timer interrupts in Critical Regions in the MT system to ensure no race conditions between tasks and the timer interrupt handler.
5. Advanced Topics
As a topic for advanced study, the reader may try to implement task scheduling by time-slice and discuss its implications. In time-slice based task scheduling, each task is given a fixed number of timer ticks, known as the time-slice, to run. While a task runs, its time-slice is decremented by the timer interrupt handler. When the time-slice of the running task decrements to 0, the system switches task to run another task. These sounds simple and easy but there are serious implications. The reader is encouraged to think of the problems and possible solutions.
Source: Wang K.C. (2018), Systems Programming in Unix/Linux, Springer; 1st ed. 2018 edition.