CS444 Previous Midterm Exam,  for practice, F06 Solutions

Open books, notes, handouts.

Write on these pages, using the backs if need be (I hope not.)

Each problem is worth 20 points.

 

  1. Consider the system calls implemented in hw2, using “int $0x80” as the system call instruction.
  1. How is the system call number specified?

in eax

  1. What is saved on the stack by this system call instruction?

      EIP (also known as PC), EFLAGS. (also CS, the code segment descriptor, but we ignore segment registers in this class)

 

  1. What is specified by the 0x80 number, i.e., what would we have to change in tunix.c if we switched to “int $0x90” as the system call instruction?

This is the index in the IDT of the trap vector.  We would have to change set_trap_gate’s first argument in tunix.c

 

Continue to consider hw2’s system, in execution.  Suppose the UART transmitter becomes ready to accept another byte while the user program is running.

  1. Is IF=0 or IF=1 at this moment?

IF = 1 in user code, always

  1. After the interrupt happens in the CPU, what software function (assembler or C) first executes?  Which one last executes, just before the user program resumes execution?

 

         the assembler interrupt handler, irq3inthand, first and last.

 

  1. A major goal of modern operating systems is user-kernel separation.
  1. Why is this important?

It is crucial for systems security.  No user code can harm the kernel image or even read it.

 

  1. Compare the hw2 system with Solaris or Windows 2000, both of which have very good user-kernel separation: what do we have in hw2 in this direction and what is missing in our setup?

 

Both hw2 and Solaris/Windows2000 use system call instructions to control the user-kernel transition. 

In hw2, we don’t run the user code at user mode in the CPU as is done in the real OS’s, so the user code could do privileged instructions in hw2.

 

  1. We have seen the need for mutual exclusion (mutex) even in hw1, a single-program system. 
  1. Explain this need—what could happen, and by what execution scenarios?

 

The input and output buffers/queues of the tty driver are shared between ttyread/ttywrite and the corresponding input and output interrupt handlers.

With no mutex, an interrupt could occur half way through an enqueue in ttywrite and do a dequeue on the same data structure, breaking it.

(or half way though a dequeue in ttyread, an input interrupt handler execution could enqueue on the same queue, breaking it.)

 

 

  1. Explain how we provided mutex.

 

By turning off the interrupt system, cli(), to set the mutex, and turning it back on to release the mutex.

 

  1. Note: we haven’t covered deadlocks yet, so ignore this problem for now. A system has two processes, A and B, and three identical resources.  Each process needs a maximum of two resources.  Show that deadlock is impossible.  One way: let x be the number of resources A has and y the number for B.  What does the hold condition tell us?  The waits-for condition?  Then show an unwinding for the only possibility.

   

            The hold condition requires x >= 1, y >= 1.

            The waits-for conditions requires x < 2, y < 2, so they don’t yet have everything they want.

             Thus   x = y = 1.

             Unwinding.   There is one unit available.  Assign it to A, finish A, free both.  Then there are two units available, and B can easily finish.

 

 

  1. Consider the multi-threaded Web server described in Tanenbaum on pg. 88, and assume kernel-supported threads are in use.  Suppose there are 5 worker threads.

 

  1. How many stacks are there in the user process image?   6
  2. Find the points at which a worker could block, and similarly, where the dispatcher could block (which lines of code?  mark them below)
  3. Where must there be an action that does an unblock (there’s only one spot in this code that has to have an unblock action.)  Again, mark that line in the code.
  4. Why is a pointer (&buf) sufficient as communication between the dispatcher and the worker—why can they use the same pointer value to access the buffer?

 

Pointer values are memory addresses in the user image, and all threads operate in the same process image, so have access to the same user addresses.

 

 

/* dispatcher */

while (TRUE) {

   get_next_request(&buf);  ß can block

   handoff_work(&buf);  ß unblocks worker

}

 

/* worker */

while (TRUE) {

   wait_for_work(&buf);   ß can block

   look_for_page_in_cache(&buf, &page);

   if (page_not_in_cache(&page))

      read_page_from_disk(&buf, &page);  ß can block

   return_page(&page);

}