CSE logo University of Washington Computer Science & Engineering
 CSE 410 Computer Systems - Homework 7 - Spring 2009
  CSE Home   About Us    Search    Contact Info 

Due: Thursday, May 28, at 11 pm.

In this assignment we explore some issues with scheduling and synchronization.

  1. (Silberschatz 3.6 [8th] / 3.1 [7th]) Describe the differences among short-term, medium-term, and long-term scheduling.

  2. Consider the following threads with the specified starting times, total running times, and priority values, where 1 is lowest priority and 5 is highest. Assume that these threads are executed on a single processor. Starting at time 0, and continuing until all threads terminate, draw a time diagram showing how each scheduling method listed below allocates the processor. Show where each thread is executed and for how long. (Hint: more than one diagram is possible for some scheduling methods; you only need to give one possible diagram for each method.)

    Scheduling methods:
    1. First come first served
    2. Round robin, with 30 ms. quantum
    3. Highest priority first (1=lowest, 5=highest)
    4. Shortest job first

    Threads:
     
    T1
    T2
    T3
    T4
    T5
    T6
    start time
    0
    0
    40
    40
    70
    100
    running time
    50
    80
    50
    30
    40
    30
    priority
    1
    2
    5
    1
    3
    4

    Example timing diagram format (you can draw the diagram however you wish as long as it is clear which thread is running when)
    0 ms: T1 15 ms: T4 40 ms: T8 65 ms: T2


  3. Starvation is the situation in which a process waits forever to be scheduled for execution. Which of the scheduling methods in the previous problem can allow starvation? Describe a scenario for each of these methods where starvation takes place. (You should assume that the scheduling algorithm is naive and does not attempt to detect starvation or compensate for it. You also may assume the arrival of as many threads as you wish. Obviously if there is a finite number of threads, all of them will eventually execute.)

  4. (Silberschatz 6.11 [8th] / 6.3 [7th]) What is the meaning of the term busy waiting? What other kinds of waiting are there in an operating system? Can busy waiting be avoided altogether? Give a brief explanation for your answers.

  5. (Silberschatz 6.12 [8th] / 6.4 [7th]) Explain why spinlocks are not appropriate for single-processor systems, yet are often used in multiprocessor systems.

  6. (Silberschatz 6.13 [8th] / 6.5 [7th]) Explain why implementing synchronization primitives by disabling interrupts is not appropriate in a single-processor system if the synchronization primitives are to be used in user-level programs.

Turn-in Instructions: Use the turn-in drop box link on the main course web page to submit a file containing your solutions. You can use any common file format, including plain text, word, or pdf. If you wish, you could also scan in a hand-written solution and submit that, but if you do that, please be sure your handwriting is neat and legible. Please be sure to include your name at the top of your answers.

CSE logo Computer Science & Engineering
University of Washington
Box 352350
Seattle, WA  98195-2350
(206) 543-1695 voice, (206) 543-2969 FAX
[comments to Hal Perkins]