ECE397A Operating Systems –Sample midterm and answers

 

 

(30 pts) Short Answers (be very short!)

1.     Which OS service is using the base and limit registers?

Memory protection

2.     What is the advantage of a Mikrokernel design compared to a layered OS design? Give examples.

Less overhead in Microkernel designs (going through layers in layered OS design is expensive), ease of extension, higher reliability. Ex: MACH vs WindowsNT

3.     What happens during a DMA operation?

Chunks of data transferred from/to device to/from memory, without CPU intervention.

4.     Why do we use prefetching?

To hide fetch latency (prefetching overlaps fetching and processing)

5.     What happens during a context switch?

Process state (registers: PC, SP, HP, etc..) is saved into a PCB, and the next process is started by retrieving information from its PCB

6.     Draw the process state diagram. 

See Fig 4.1 (page 89) in textbook or see lecture notes

7.     Why do we need the test-and-set or the swap instructions?

To provide hardware support for synchronization, otherwise it is very difficult to support synchronization

8.     Explain how the test-and-set instruction works, focus on the key insight.

Sets the new value to true, and returns the old value - ATOMICALLY

9.     What is the key difference between a Just-In-Time Java VM (JIT) and a Hotspot Java VM?

JIT JVM compiles the whole java file, Hotspot JVM compiles only the most frequently executed code

10. Which scheduling technique we studied optimizes waiting time?

Shortest Job First

 

 

(20 pts) CPU scheduling.

Given the following mix of job, job lengths, and arrival times, assume a time slice of 20 and compute the completion time of each job for the FIFO, RR, and SRTF algorithms. Assume that FIFO is non-preemptive, RR and SRTF are preemptive. Use the following format for the solution:

 

Parameters

Scheduling Algorithms

Job

Length

Arrival time

FIFO

RR

SRTF

0

70

0

70

170

110

1

40

10

110

100

60

2

60

20

170

160

170

 

 

Completion time

 

 

 

 

 

(40 pts) Threads, Processes. Consider the following program and its corresponding process representation in memory below.

 

    #include ...

 

    main() {

       int cid;

       ...

       cid = fork();

       if (cid == 0)...

    }

 

 

 

 

 

Figure 1: Representation of the parent process in memory before the fork() call.

(see lecture notes)

 

 

(a)  (10) Immediately after the call to the Unix system call cid = fork(), assume the child process’s pid (process ID)  is 123 and draw a picture of both processes (i.e., parent and child) and PCBs’ memory states.

 

PARENT:

PCB same as before

Memory state: cid = 123 and PC points to next instruction ( if(cid==……   )

 

CHILD:

PCB has pid=123

Memory state: cid = 0 and PC points to next instruction ( if(cid==……   )

 

(b) (10) If instead of cid = fork(), we have cid = threadFork(), where threadFork() is a call to a user level threads package that forks a thread, how would the memory state change?

 

New thread shares the same memory space and PCB… but has a different set of registers (HP, SP, PC, etc…)

 

(c)  (20) Write a small Java program with two classes, Test and MyThread. Test is the main class where you start the two threads, MyThread is the class that has the code for the threads. Assume that the threads add 100 to the same instance variable saldo.  Assume you can extend the Thread class. Identify the critical section and make sure you synchronize correctly. Use either the Java type of synchronization or semaphores. (If your code does not use synchronization but otherwise is correct, you get 15 credits.)

 

public class Test {

     public int saldo = 0;

     public synchronized add() {

              saldo += 100;

     }

     public static void main(String[] args) {

              Mythread T1, T2;

              T1 = new MyThread();

              T2 = new MyThread();

              T1.start();

              T2.start();

              T1.join();

              T2.join();

     }

}

 

public class MyThread extends Thread {

public void run() {

              Test.add();

}

}

 

 

(30 pts) Synchronization. The Sleeping-Barber Problem. A barbershop consists of a waiting room with N chairs, and a barber room with one chair.  Write a program to coordinate access to the barber using semaphores. When there are N customers waiting in the shop you should not allow more people to enter. You should also synchronize access to the barber’s chair. At any time you can have only one person sitting in that chair. Hint: you need to use both binary and counting semaphores.

 

Implement the class BarberRoom that has the critical section in SitInBarberChair (note that this method would need to implement synchronization in the waiting room and barber’s room). Assume that you have support for binary and counting semaphores in Java.

 

 

 

class BarberRoom{

 

// here you put the semaphore declarations and other variables you need

          BinarySemaphore barber;

          CountingSemaphore chairs;

 

BarberRoom(){ // constructor

               // initialize semaphores here

                   barber = new BinarySemaphore(true);

                   chairs = new CountingSemaphore(N);

}

 

public SitInBarberChair{ // entering the shop and waiting for getting access to the barber

// your code here

chairs.wait(); // wait until chairs>0, then decrement chairs

          barber.wait(); // wait until barber==true, set it to false

          chairs.signal(); // increment chairs

// assume here is when you sit in the barber’s chair

…..

//your code here

barber.signal(); // set barber to true

}

 

 

}