The following code outlines a simple timesharing scheduler:
struct MState {
int Regs[31]; /* saved state of user's registers */
} User;
int N = 42; /* number of processes to schedule */
int Cur = 0; /* number of "active" process */
struct PCB {
struct MState State; /* processor state */
Context PageMap; /* VM map for process */
int DPYNum; /* console/keyboard number */
} ProcTbl[N]; /* one per process */
Scheduler() {
ProcTbl[Cur].State = User; /* save current user state */
Cur = (Cur + 1)%N; /* increment modulo N */
User = ProcTbl[Cur].State; /* make another process the current one */
}
Suppose that each time the user hits a key on the keyboard, an interrupt
is generated and the interrupt handler copies the new character into a
kernel-resident input buffer. The operating system includes a ReadKey service
call (SVC) which can be invoked by the user to read the next character from
the input buffer. If the input buffer is empty,
the SVC should "hang" until a character is available.
The first draft of the ReadKey SVC handler is shown below. The SVC handler
routine saves the user's state in the User structure and then call ReadKey_h().
When ReadKey_h() returns, the SVC handler restores the user's state and then
does a JMP(XP) to restart the user's program.
ReadKey_h() {
int kdbnum = ProcTbl[Cur].DPYNum;
while (BufferEmpty(kdbnum)) {
/* busy wait loop */
}
User.Regs[0] = ReadInputBuffer(kdbnum);
}
After executing a ReadKey SVC, where will the user program
find the next character from the input buffer?
The SVC stores the character read from the input buffer in the
R0 slot of the user structures. This is loaded into the user's
R0 just before the kernel returns to user mode.
Explain what's wrong with this proposed implementation.
If the buffer is empty when the user makes the ReadCh supervisor
call, the handler loops in the kernel with interrupts disabled.
This prevents the buffer from being filled and so the code
enters an endless loop.
A second draft of the keyboard handler is shown below:
ReadKey_h() {
int kdbnum = ProcTbl[Cur].DPYNum;
if (BufferEmpty(kdbnum))
User.Regs[XP] = User.Regs[XP] - 4;
else
User.Regs[0] = ReadInputBuffer(kdbnum);
}
Explain how the modifications fix the problems of the initial implementation.
When the buffer is empty, this code returns to user mode and re-executes the SVC.
By returning to user mode, interrupts are enable (briefly!) so interrupts can
happen and the buffer will eventually be filled when a key is typed.
The designers notice that the process just wastes its time slice waiting for
someone to hit a key. So they propose the following modifications:
ReadKey_h() {
int kdbnum = ProcTbl[Cur].DPYNum;
if (BufferEmpty(kdbnum)) {
User.Regs[XP] = User.Regs[XP] - 4;
Scheduler();
} else
User.Regs[0] = ReadInputBuffer(kdbnum);
}
What would be the most likely effect of removing the line of
code where User.Regs[XP] is decremented by 4?
When next scheduled, the user program will not re-execute the SVC and
will proceed assuming that the next character is available in R0. In short,
it will process a "garbage" character, ie, use whatever happened to be in
R0 at the time of the original SVC.
Explain how this modification improves the overall performance of the
system (assume the decrement by 4 has not been removed).
Calling scheduler() permits other programs to run while waiting for the
next character to arrive.
This version of the handler still doesn't prevent the process from
being scheduled each quantum, even though it may just call Scheduler()
once again if no character has appeared in the input buffer. Explain
how the sleep(status) and wakeup(status) kernel routines described in
lecture can be used to make sure that processes are only scheduled when
there is something "useful" for them to do.
By calling sleep(status), the handler can notify the kernel when to
next schedule the user's process for execution (ie, after a character
has been typed). This avoids rescheduling the process for execution
when all it will do is discover that the buffer is still empty and
suspend itself.
If the keyboard handler calls wakeup(status), the kernel can locate
all processes that went to sleep waiting for an event that's related
to "status". It can then mark those processes as ready for execution once
again. Thus processes are only run when there's something good reason
for them to proceed.