Fall 2011 COMP 3511 Homework Assignment #2
Handout Date: Oct. 13, 2011 Due Date: Oct. 27, 2011
Name: ______________ ID: ___________________ E-Mail: _____________ COMP 3511 L __

Please read the following instructions carefully before answering the questions:  You should finish the homework assignment individually.  There are a total of 4 questions.  When you write your answers, please try to be precise and concise.  Fill in your name, student ID, email and Section number at the top of each page. Submissions without this information will be discarded.  Please fill in your answers in the space provided, or you can type your answers in the MS Word file.  Homework Collection: the hardcopy is required and the homework is collected at the collection box (near CSE office 4205, #6 and #7).

1. (30 points) Please answer the following question briefly (1) (5 points) What are the three conditions that a solution to Critical Section problem must guarantee? Answer: A solution to the critical section problem must guarantee three conditions: mutual exclusion, progress and bounded waiting.

(2) (10 points)? Scheduling criteria are often conflicting with each other. Please describe the conflict in the following two scheduling pairs: average waiting time vs. maximum waiting time, I/O device utilization vs. CPU utilization. Answer: Average waiting time and maximum waiting time: Average waiting time is minimized by executing the shortest tasks first. Such a scheduling policy could however starve long-running tasks and thereby increase their waiting time. I/O device utilization and CPU utilization: CPU utilization is maximized by running long-running CPU-bound tasks without performing context switches. I/O device utilization is maximized by scheduling I/O-bound jobs as soon as they become ready to run, thereby incurring the overheads of context switches.

(3) (5 points) What is the difference between a non-preemptive scheduling algorithm and a preemptive scheduling algorithm. Answer: Non-preemptive scheduling occurs only when the current process running on the CPU gives up the CPU voluntarily. Otherwise, the scheduling is preemptive in nature, in which scheduling might also occur when a new process joins the ready queue.

(4) (6 points) What is the similarity between FCFS and RR scheduling algorithms? What are their differences? Under what condition, a RR is the same as FCFS? Answer: Both of them serve the processes according to FCFS order, but RR limits each process to a prior-determined quantum. When the quantum is set to be equaled or bigger than the maximum CPU burst time, RR becomes FCFS.

(5) (4 points) What is the fundamental problem in FCFS scheduling? Answer: A short process might get stuck behind a long process. This is referred as the convoy effect. This usually results in excessive long average waiting time.

2. (15 points) Please expand the exponential averaging algorithm on Slide 5.17, and demonstrate why this is called "exponential average". Given the initial estimated value and alpha on Slide 5.18, please re-calculate the estimate values (time slots 1-7). Please show all the steps. Answer: Expansion: n+1 =  tn+(1 ‐ ) tn‐1 + … +(1 ‐  )j  tn‐j + … +(1 ‐  )n +1 0. Because the weight of term decreases exponentially of  (0