CSC256, CSC456 Midterm Exam 3/15/98

Results indicated good understanding of the material to date, but that the exam was quite long for a single class period. Despite that, there were perfect scores by both CSC256 and CSC456 students. After some analysis, I simply added full credit for one problem into each of your scores (this was more generous than dropping the lowest problem). I saw a few fairly serious misconceptions, so please make sure that you understand the solutions thoroughly, and obtain help from me during office hours if needed.

Of 12 problems, CSC456 students are to work any 10 and CSC256 students must work 8. Please clearly designate the problems you want credit for. This exam is closed book, closed notes. You may use a calculator -- but not a computer with significant memory. Please write clearly, label answers (2c etc.), and show all work. I'll try to be as unambiguous as possible in the questions; in the event that you need to make an assumption to proceed WRITE IT DOWN. In the interest of fairness, I will be highly resistant to answering questions during the exam. If you would not mind my disclosing your answer as the correct solution, please indicate so.

1. What resources are used when a thread is created? How do they differ from those used when a process is created? Describe the actions taken by the NachOS kernel to switch between a) threads, and b) processes.

Most people did fine on this. I wanted to see that a thread gets a register set, including pc and stack pointer, and memory for a stack. A process gets a full address space including code, initialized data, uninitialized data (heap), and a thread's stuff. In NachOS, switching differs only in the need to swap address space for processes (by changing the page table register or flushing the TLB if used). Steps include disable interrupts, save current thread state, place thread in ready queue (if not waiting for io), select next thread, determine if process switch is necessary and switch (optimization -- no process switch if next thread is from same process), restore its state, begin executing it.

2. Consider the following set of processes, with the length of the CPU burst time given in milliseconds:

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5 all at time 0.

  1. Draw four Gantt charts illustrating the execution of these processes using first-come-first-server, shortest-job-first, a non-preemptive priority (smaller priority number implies higher priority), and round-robin (quantum = 1) scheduling.
  2. Algorithm

    a) Process Order

    b) Wait Time

    Average

    P1

    P2

    P3

    P4

    P5

    FCFS

    12345

    0

    10

    11

    13

    14

    9.6

    SJF

    24351

    9

    0

    2

    1

    4

    3.2

    42351

    9

    1

    2

    0

    4

    3.2

    Non-preemptive priority

    25134 

    0

    16

    18

    1

    8.2

    25314

    8

    0

    6

    18

    1

    6.6

    RR

    12345 135 15 15 15 1 1 1 1 1 

    0+4+2+1+1 +1 =9

    1

    2+3=5

    3

    4+2+1+1+1=9

    5.4

  3. What is the waiting time of each process for each of the scheduling algorithms in part a?
  4. Which of the schedules in part a results in the minimum average waiting time (over all processes)?

Clearly SJF -- some of you remembered that SJF is provably optimal for minimizing waiting time.

3. Consider a variant of the round-robin scheduling algorithm where the entries in the ready queue are pointers to process-control-blocks.

  1. What would be the effect of putting two pointers to the same process in the ready queue?
  2. Doubling the time given that process.

  3. What would be the major advantages and disadvantages of this scheme?
  4. Simple scheme which would provide some priority work with minimal modification to scheduler. But, overhead for managing pointers is a nuisance -- what if the process is io waiting or done? Have to remove BOTH pointers from ready queue, etc. Also may increase overhead if same process runs back-to-back -- it was not necessary to switch contexts. (Practically speaking, I'd always check to see if a context switch were necessary before doing one.)

  5. How would you modify the basic round-robin algorithm to achieve the same effect without duplicate pointers?

Add a simple quantum indicator to PCB.

4. Demonstrate that monitors and semaphores are all equivalent, insofar as the same types of synchronization problems can be implemented with them.

This problem seemed to confuse many of you, and most of you stayed away from it. If I can implement semaphores using monitors and also implement monitors using semaphores, we have shown that they resolve the same class of synchronization problems.

// Semaphore using monitor

monitor {

int count;

condition waiting;

function init( initial_count ) {

count = initial_count;

}

function P() {

while (count < 0) waiting.wait();

count = count - 1;

}

function V() {

count = count + 1;

waiting.release();

}

}

// Monitor using semaphores

semaphore mutex :=1 , waiting := 0;

int count := 0;

For each invocation of a monitor function do { mutex.P(); function; mutex.V() }. For each use of a condition variable.wait() do { waiting.P(), count = count+1}. For each use of a condition variable.signal() do { waiting.V(), count = count-1}. For each use of a condition variable.broadcast() do { while( count0) { waiting.V(); count = count-1;}}

 

I expected rather better results on this one, since you did the second part in assignment one, and I did the first part in class. Don't be surprised if it recurs in some variant on the final.

 

 

5. Write a bounded-buffer monitor in which the buffers (of pointers) are embedded within the monitor itself.

Numerous good solutions to this.

Monitor {

Condition full, empty;

Queue q;

BbInsert( item ) {

while ( queue.isFull() ) full.wait();

q.insert(item);

empty.release();

}

item BbRemove() {

while ( queue.isEmpty() ) empty.wait();

result = q.remove();

full.release();

return result;

}

}

 

 

6. Consider the following snapshot of a system:
Answer the following questions using the banker's algorithm to prevent deadlock:

  1. Is the system in a safe state? If so, give a sequence of processes that will allow all processes to complete. If not, identify a process which could be terminated to put the system into a safe state.
  2. Yes it is safe, P0, P2, P3, P1, P4 is one of many sequences which work.

  3. If a request from P1 arrives for (0 2 4 0) can the request be granted immediately?

No, there are not enough C's to insure deadlock avoidance at this time.

 

7. Explain the difference between internal and external fragmentation. Explain the following allocation algorithms: first-fit, best-fit, worst-fit. Given discontiguous memory partitions of 100k, 500k, 200k, 300k, and 600k in order, how would each of the first-fit, best-fit, worst-fit algorithms place processes of 212k, 417k, 112k, and 426k (in order)? Which algorithm makes the most efficient use of memory?

There were a few common mistakes here -- most related to forgetting to divide the block that a process was assigned to.
 

Original block

First-fit

Best-fit

Worst-fit

100k

 

 

 

500k

212k / 112k

417k

417k

200k

 

112k

 

300k

 

212k

 

600k

417k

426k

212k / 112k

Won't fit now

426k

 

426k

Clearly Best-fit pays off in this example.

8. Consider a paging system with the page table stored in memory.

  1. If a memory reference takes 200 nanoseconds, how long does a paged memory  reference take when the page is in memory?
  2. 200ns page table ref + 200 ns memory ref = 400 ns

  3. If we add associative registers, and 75% of all page table references are found in the associative registers, what is the effective memory access time? (Assume that finding a page table entry in the associative registers requires zero time, if the entry is there.)
  4. (0 ns TLB + 200ns memory ref) *.75 + (200ns page table ref + 200 ns memory ref) * .25 = 250 ns

  5. Suppose we have a demand paged memory. The page table is held in registers.  It takes 8 ms to service a page fault if an empty page is available or the replaced page is not modified, and 20 ms if the replaced page is modified.  Memory access time is 100 ns. Assume that the page to be replaced is modified 70% of the time. What is the maximum acceptable page fault rate for an effective access time of no more than 200 ns?

Let p be probability of a page fault. Worst case:

200ns = ( 100 ns ) (1-p) + (p)(100ns + (20 * 106 ns * .7 + 8 * 106 ns * .3 ))

p = 1/164000 =~ .0000061 Hence, 1 page fault in 164,000 memory reference DOUBLES the effective access time of physical memory.

 

9. Consider the following segment table:
What are the physical addresses for the following logical addresses?
a) 0, 430
b) 1, 10
c) 2, 500
d) 3, 400
e) 4, 112

This was a freebie -- no one got it wrong. C and E are invalid references, the others are a) 649, b) 2310, d) 1727.

10. A certain computer provides its users with a virtual memory space of 232 bytes.  The computer has 218 bytes of physical memory, and a TLB.  The virtual memory is  implemented by paging, and the page size is 4096 bytes.  A user process generates the virtual address 1112345616.  Explain how the system establishes the corresponding physical location. Distinguish between hardware and software operations.

The hardware separates the address into the page address 1112316 and offset 45616. The TLB attempts to translate the address -- if found, the TLB's page frame address is added to 456 and is the physical address. If the address was not found in the TLB, either hardware or software (the TLB trap handler) then maps the page 11123 through the page table. If valid, the TLB is updated and the original instruction is restarted. Many of you confused a TLB miss with a page fault; TLB's are usually much smaller than a page table, so TLB misses are common, even for loaded pages. If the page table indicated the entry was invalid then a page fault occurs. Software operations follow: At this point the page must be retrieved, loaded into a page frame, added to the page table, added to the TLB, and then the original instruction can be restarted.

 

11. Using the page reference sequence 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 determine the number of page faults which will occur for FIFO, Optimal, and LRU page replacement algorithms. How well does LRU approximate Optimal? Why? Which of these algorithms will not exhibit Belady's anomaly? Why not?
 

 

P f

1

2

3

4

1

2

5

1

2

3

4

5

Page faults

FIFO

A

1

 

 

4

 

 

5

 

 

 

 

 

9

B

 

2

 

 

1

 

 

.

 

3

 

 

C

 

 

3

 

 

2

 

 

.

 

4

 

Opt

A

1

 

 

 

 .

 

 

 

3

 

 

7

B

 

2

 

 

 

 .

 

 

.

 

4

 

C

 

 

3

4

 

 

5

 

 

 

 

 

LRU

A

1

 

 

4

 

 

5

 

 

3

 

 

10

B

 

2

 

 

1

 

 

 .

 

 

4

 

C

 

 

3

 

 

2

 

 

.

 

 

5

LRU does not approximate Opt very well in this example since there are so few page frames that seldom does a page get to be in memory long enough to be referenced twice (we're definitely thrashing here). Hence the limited time period past is not a good approximation to the unlimited time period (in the future) used by Belady's optimal algorithm. It would improve dramatically with a few more frames and a longer reference sequence, since the effective reference time window increases with number of frames.

Neither LRU nor opt will exhibit Belady's anomaly, since they are "stack" algorithms, which insure that larger numbers of page frames store a superset of the frames stored in the original case. Note that this has significant implications for the local vs. global allocation schemes.

 

 

 

P f

1

2

3

4

1

2

5

1

2

3

4

5

Page faults

FIFO

A

1

 

 

 

.

 

5

 

 

 

4

 

10

B

 

2

 

 

 

.

 

1

 

 

 

5

C

 

 

3

 

 

 

 

 

2

 

 

 

D

 

 

 

4

 

 

 

 

 

3

 

 

Opt

A

1

 

 

 

.

 

 

.

 

 

4

 

6

B

 

2

 

 

 

.

 

 

.

 

 

 

C

 

 

3

 

 

 

 

 

 

.

 

 

D

 

 

 

4

 

 

5

 

 

 

 

.

LRU

A

1

 

 

 

.

 

 

.

 

 

 

 

8

B

 

2

 

 

 

.

 

 

.

 

 

 

C

 

 

3

 

 

 

5

 

 

 

4

 

D

 

 

 

4

 

 

 

 

 

3

 

5

 

12. Consider a demand paging system with a paging disk that has an average access and transfer time of 20 ms.  Addresses are translated through a page table in main memory, with an access time of 1 us per memory access. Thus, each memory reference through the page table takes two accesses.  To improve this time, we have added an associative memory that reduces access time to one memory reference, if the page table entry is in the associative memory.  Assume that 80 percent of the accesses are in the associative memory, and that, of the remaining, 10% (or 2% of the total) cause page faults.  What is the effective access time?

Eatclean = 1us * .8 + (1us + 1us) * (.2*.9) + (20,000 us) * (.2*.1) = 401.16

Eatdirty = 1us * .8 + (1us + 1us) * (.2*.9) + (20,000 us *2) * (.2*.1) = 801.16