Homework 2, version 2.0.0.1, released on Sep 15, 2000. Due in class Sept 26, 2000

Please hand in your answers as follows: not handwritten, 11-pt typefont, min of .5" margins. Each problem must be answered on sperate sheets of paper. Your name and id should be written seperately on each sheet of paper you submit. Please write the question number in the top of the sheet in bold. Every item is worth 5 points, unless otherwise marked.

  1. 10pts Consider a multithreaded operating system, running on a loosely connected cluster of computers, where each operating system is not aware of the availability of other processors. How can we take advantage of the threads, given that there are several CPUs available to the OS with 4GB of shared memory? You will need to answer this question in less than 8 lines, and address the following points:
    - will a ULT or KLT be more advantageous in this context?
    - consider the blocking problem of ULTs, in single processor

    2.  

  2. In typical OS designs, the PCB and other related structures belong in the operating systems. In 2-3 lines, answer the following questions:
    1. Why should these structures be in the OS? What are the security/protection concerns?
    2. Imagine a system that is completely cooperative, and users are completely trustworthy (with respect to writing correct programs). Would you design your new OS any differently with respect to these structures,if this were the case?
    3. 0pts What language/system would this resemble?
  3. Scheduling: In class, we have proven the SJF is the optimal scheduling discipline for non-preemptive jobs when the metric is turnaround time (also called response time, defined as the time from submission of a job to the system to the time the job completes).
    1. If the metric were number of completion times within specific deadlines, what would be the scheduling discipline used (assume that all jobs can actually finish within the deadlines)? Give 2-3 examples of tasks and why they would not violate the deadlines of any job?
    2. How would a job be specified (i.e., what would be the characteristics of the job in a real-time system)? Hint: Recall that in a SJF scheduling algorithm, the job is specified so that one can minimize the average completion time.
    3. Bonus question: prove that the policy you suggested above is indeed the optimal discipline (still assuming that all tasks can meet their deadlines).

     

  4. Let there be a set of tasks in a preemptive computer system. Jobs need to be scheduled to minimize the average completion time.
    1. Can you suggest a scheduling discipline that would do that? Justify your choice. Hint: recall that SJF is the optimal algorithm for non-preemtive systems.
    2. Now consider the case that each job starts producing results after 1 time unit of processing. Take the book’s definition of response time (the time between a job is submitted until the first result is produced). How (if at all) would you change the scheduling discipline?
    3. Open question (this is a very difficult question that is worth 0 points; we will not discuss this question, but it is a good thinking exercise for anyone having spare time): Would the same answer work, if there are two processors in the system? If yes, justify your answer, if no, give a counter-example of why it doesn’t work.