Operating Systems. Exercises 21

Operating Systems

Certificate Program in Software Development
CSE-TC and CSIM, AIT
September--November, 2003

Exercises 2

Due in: Monday, October 20th, 2:00pm, by e-mail to
Worth: 10% of final grade. Marked out of 60. Each question is worth 10 marks.

If there is a problem with e-mail then your answers should be printed out and handed into the CSE-TC main office by 3.00pm. Make sure that the office secretary writes the time on your answer paper.

Write in English. Include your name, student number, and “Operating Systems. Exercises 2” at the top of the answers. Do not write out the questions as part of your answers.

Late submissions will lose half marks immediately, and a further 10 marks for each hour after that. Cheating will result in 0 marks for all those involved.

If you have any questions, please send me e-mail. Good luck .
- Andrew Davison

  1. (Similar to Question 5.3, p.150, S&G, 5th ed.)

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

ProcessBurst TimesPriority
P13 4
P24 2
P35 3
P43 2
P52 1

The processes arrive in the order P1, P2, P3, P4, P5, all at time 0.

  1. Draw four Gantt charts illustrating the execution of these processes using FCFS, SJF, a nonpreemptive priority (a smaller priority number implies a higher priority), and RR (quantum = 1) scheduling.
  2. What is the turnaround time of each process for each of the scheduling algorithms in part (a)? Show all your working.
  3. What is the waiting time of each process for each of the scheduling algorithms in part (a)? Show all your working.
  4. Which of the schedules in part (a) results in the minimal average waiting time (over all processes)? Show all your working.

2. (Question 5.5, p.151, S&G, 5th ed.)

Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.

  1. What would be the effect of putting two pointers to the same process in the ready queue?
  2. What would be the major advantages and disadvantages of this scheme?
  3. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

3. (Similar to Question 7.9, p.233, S&G, 5th ed.)

Consider a system consisting of m resources of the same type, being shared by n processes. Resources can be requested and released by processes only one at a time. Show that the system is deadlock free if the following two conditions hold:

  1. The maximum demand of each process (Max[i]) is between 1 and m resources.
  2. The sum of all the maximum demands is less than m + n.
    (i.e.  Max[i] < m + n)

Note: remember that Need[i] = Max[i] – Allocation[i]

4. (Similar to Question 7.13, p.234, S&G, 5th ed.)

Consider the following snapshot of a system:

AllocationMaxAvailable
A B C DA B C DA B C D
P01 4 1 01 6 1 60 0 0 1
P10 2 1 31 3 2 3
P21 0 1 01 7 6 6
P31 7 0 11 7 0 1
P40 0 3 31 0 3 4

Answer the following questions using the banker’s algorithm:

  1. What is the content of the matrix Need?
  2. Is the system in a safe state? Explain your answer.
  3. If a request from process P2 arrives for (0,0,0,1), can the request be granted immediately? Explain your answer.

5. (Similar to Question 8.5, p.285, S&G, 5th ed.)

  1. Given memory partitions of 100K, 300K, 200K, 500K, and 600K (in order), how would each of the First-fit, Best-fit, and Worst-fit algorithms place processes of 405K, 372K, 199K, and 411K (in order)? Note: only one process can be assigned to a partition at a time. Explain any diagrams you use.
  2. Which algorithm makes the most efficient use of memory? Explain your choice.

6. (Similar to Question 8.10, p.285, S&G, 5th ed.)

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

  1. If a memory reference takes 96 nanoseconds, how long does a paged memory reference take? Show all your working.
  2. If we add associative registers, and 95 percent of all page-table references are found in the associative registers, what is the effective memory reference time? (Assume that finding a page-table entry in the associative registers takes zero time, if the entry is there.) Show all your working.

Note: complex diagrams are not needed in your answers to 6 (a) and (b).