Tutorial Week 9

<li>  
Suppose a system  takes one unit of time to perform a context switch, and switching 
is done after each process either terminates or has run for 20 units. There 
are three tasks in the system, and the first will require 70 units of time 
to run, the second will require 25 units and the third 45. Usiing  round robin 
scheduler show which processes run and when. What percentage of time is spent 
in context switching? What is the average length of time for a process to complete 
execution?

Ans: 
        time    action
        0 P0 starts
        20  P0 is stopped, with 50 remaining
        21  P1 starts
        41  P1 is stopped with 5 remaining
        42  P2 starts
        62  P2 is stopped with 25 remaining
        63  P0 restarts
        83  P0 is stopped with 30 remaining
        84  P1 restarts
        89  P1 terminates
        90  P2 restarts
        110   P2 is stopped with 5 remaining
        111   P0 restarts
        131   P0 is stopped with 10 remaining
        132   P2 restarts
        137   P2 terminates
        138   P0 restarts
        148   P0 terminates
There are 8 context switches in 148 units. So the switching overhead is 8/148 
* 100% ~ 5%. The average to completion is (89 + 137 + 148)/3.

<li>  
In a priority scheduler, for each unit of time that a process runs its priority 
decreases by one. A running process is replaced when there is another process 
on the runnable list with a higher priority. The system starts with three processes 
of priority 15, 10 and 18 respectively. Show which processes run and when.

Ans: 
The sequence of running (with priorities is)
T3(18), T3(17), T3(16), T3(15), T3(14), T1(15), T1(14), T1(13), T3(13), T3(12), 
T1(12), T1(11), T3(11), T3(10), T1(10), T1(9), T2(9), T3(9), ... as in round 
robin

<li>   
In a two-level scheduler with swapping, the states that a process can be in 
are
       runnable, but swapped out
       runnable, in main memory
       blocked, and swapped out
       blocked, in main memory
       running, in main memory
Draw the state transition graph for this.

Ans: 

runnable
swapped
blocked
swapped
running
runnable
memory
blocked
memory



<li>   
Starvation occurs when a process never gets a chance to run. Can starvation 
occur with round robin? with a shortest-first scheduler? with a priority scheduler?

Ans: 
Round robin: starvation cannot occur because a process will eventually reach 
the fornmt of the queue; shortest-first: a long process couyld be starved if 
shorter ones can be continually added; priority: yes, if higher priority jobs 
keep getting added that run for short enough that their priority never falls 
low enough. 

<li>   
Suppose processes can share pages (eg both using the same library code). How 
can the process manager tell that a page is no longer required by any process?

Ans: 
A refernence count should be used for each piece of memory. When a new process 
starts using a piece of memory the count is increased, and decreased on termination. 
When the count is zero, it can be removed.

<li>   
How do Terminate and Stay Resident processes in MSDOS work?

Ans: 
A TSR is loaded in the normal way. Upon exit, its memory space is not recalimed 
but is left there (stay resident). When first loaded a TSR replaces the code 
for some interrupt so taht the TSR is trigered when the interrupt occurs instead 
of the original code. It should do its work then call the original interrupt 
code itself. Note that TSRs have much potential to ``misbehave''. They should 
allocate all required data space on startup, not throw away original interrupt 
code, etc. In terms of process models, the process that called the interrupt 
is ``suspended'' while the TSR executes.

Laboratory Week 9

<li>  
Write your own version of the call ``system'' using ``fork'' and ``wait''. 
What is the return value of the Unix call? How can ``wait'' determine the exit 
value of a child?

Ans: 

if ((pid = fork()) == 0) {
  execlp(command);
} else {
  while (wait(&status) != pid)
    ;
   return WEXITSTATUS(status);

<li>  
Create a child that keeps looping forever printing a message. Pause it by sending 
it the SIGSTOP signal. Resume it by sending SIGCONT, and then finally kill 
it.

Ans: 

if ((pid = fork()) == 0 {
  while (1)
    printf("Running forever\n");
} else {
  sleep(5);
  kill(pid, SIGSTOP);
  sleep(5);
  kill(pid, SIGCONT);
  sleep(5);
  kill(pid, SIGINT);
}