Computer Science 15-412 Operating Systems

Homework #1
Handed out: January 28, 2000
Due: February 4, 2000 at the end of class

 

 

 

 

• Please use a separate page to answer each question and stable the pages. 
• Please also place your name on every page.

 

 

 

 

 

 

 

---

1. [5 points]

 

Distinguish between traditional interrupt-based I/O and DMA-based I/O.

 

 

---

2. [5 points]

 

Explain the mechanisms by which a modern system can shift between system and user mode, without compromising the integrity or functionality of either.

 

 

---

3. [20 points]

 

Given the following execution profiles, fill in the CPU occupancy chart on the next page.

 

Process X:        CPU 5ms, Disk 10ms, CPU 5ms, Printer 15ms, CPU 5ms,

Printer 15ms, CPU 5ms, Disk 15ms, CPU 5ms, Printer 20ms

Process Y:        CPU 15ms, Disk 10ms, CPU 30ms, Disk 15ms, CPU 25ms,

Printer 20ms

 

Process Y is admitted 1 ms after process X.

 

 

For the time that a process runs on the CPU create a box and shade it completely in. For the times that there is a disk event create a box grayed in. While there is a print job occurring create a box and do not fill it in.

 

• Run Until Completion
• Round Robin (10ms quantum)
• Shortest Job first (SJF)

 

Use the sheet on the next page to do your work. Turn that sheet in (an extra copy is included for scratch work). The beginning of ``Run until Completion'' is done for you.

 

Assume that the disk and printer cannot be preempted, so each bursts of I/O should be carried out contiguously.

 

      

      

     

---

4. [15 points]

 

For each of operations below, please identify whether or not any PCBs are allocated or freed by the kernel.  Please clearly identify which processes are involved and the reason for the allocation or deallocation.

 

For each movement of a PCB among the queues, please identify the purpose of the queues involved and the reason(s) for the movement.

 

If no queues or PCBs are affected, please state this and explain your reasoning.

 

(a)  A DMA-based network-transfer is initiated by the currently running process

(b)  An execve() call.

(c)  An exit() call

(d)  A fork() call.

(e)  A waitpid() call

 

 

---

5. [15 points]

 

Consider the implementation of a highly concurrent, I/O intensive mission-critical software system.

 

The platform is a multiprocessor computer with a modern operating system that supports multiprogramming and kernel threads. A user-level threads package is available for this platform.

 

Would you select to implement your software system using multiple processes, user threads, kernel threads, or some combination?  Please be certain to discuss the important characteristic of each paradigm.

 

---

6. [20 points]

 

Consider an operating system that processes input from the network by reading the the next packet from the network interface each time it receives an interrupt indicating that another packet has arrived. When an interrupt is received, the current context of the CPU is saved to the stack and the interrupt handling routine is invoked. The interrupt handling routine then copies the packet from the network interface into kernel memory. During the return it restores the saved context so that the interrupted program can continue executing.

 

Suppose that saving and restoring the CPU take 10μs and that copying the 1K packet from the interface takes 80μs.

 

Also suppose that the network interface is a 10baseT Ethernet, and that the interface is receiving data in 1KB packets at the rate of 5Mbps (mega-bits per second.) What percentage of the CPU time is spent servicing these network interrupts? Show your work.

 

 

---

7. [20 points]

The following is a potential solution to the critical section problem (Nutt, 2000). Argue for its correctness or provide an execution sequence that demonstrates a failure.

 

/*

 * Shared information

 */

int turn; /* Turn is initially 0 */

boolean flag[2]; /* Both are initially false */

 

/*

 * Consider 2 processes, pid=0 and pid=1

 */

process (int pid)

{

      while (1)

      {

            NonCriticalCode();

           

            flag[i] = TRUE;

           

            turn = (i+1) mod 2;

 

            while ((flag[(i + 1) mod 2]) && (turn == (i+1) mod 2));

 

            CriticalSection()

 

            flag[i] = FALSE;

      }

}