Assignment 6: Chapter 4 and 5

Please make sure that you're using the same edition of the book. There is no guarantee that older editions use the same numbering for problems. Please submit a single tar file.

1. Derive and intuitively motivate Little's Law for the number of customers (jobs) in the system. (In class, we had looked at the number of customers waiting for service.)
2. You are given a choice between two processors, each running at 1 GHz, or one processor, running at 2 GHz. Assuming that the CPU speed is indicative of the number of instructions per second, which choice would you prefer and why? Justify your answer with a queueing performance argument. (You can assume that each CPU has its own job queue and that the system is of type M/M/1.) The average number of customers in the system for M/M/1 is given by where ρ is the load, computed as arrival rate over service rate, or ρ = λ / μ.
3. You are given the choice of having one job queue for two processors, or having each processor with its own queue. Does it matter? Justify your answer intuitively by comparing the behavior under different scenarios.
4. Which of the following components of program state are shared across threads in a multithreaded process?
   1. Register values
   2. Heap memory
   3. Global variables
   4. Stack memory
5. In this exercise, you'll be writing a C/C++ pthread program to build a simplified multi-threaded web server. Your program should have one thread that waits for incoming TCP connections, and then create a thread for each request, reading the file and returning the content. You only need to parse HTTP GET requests and can ignore all but the first line of the request. You only need to support a single directory, i.e., only URLs such as example.html, not nested/dir/example.html. You should be able to retrieve two large files from two web browsers simultaneously. RFC 2616 describes HTTP/1.1, but you'll only need a tiny fraction of that document.
6. 5.4: Consider the following set of processes, with the length of the CPU-burst time given in milliseconds:

   Process	Burst Time	Priority
   P1	10	3
   P2	1	1
   P3	2	3
   P4	1	4
   P5	5	2

   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 pro- cesses 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?
   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 minimal average waiting time (over all processes)?
7. 5.5: Which of the following scheduling algorithms could result in starvation?
   1. First-come, first-served
   2. Shortest job first
   3. Round robin
   4. Priority
8. 5.7: Consider a system running ten I/O-bound tasks and one CPU-bound task. Assume that each of the I/O-bound tasks issue an I/O operation once for every millisecond of CPU computing and that each I/O operation takes 10 milliseconds to complete. Also assume that the context switching overhead is 0.1 millisecond and that all processes are long-running tasks. What is the CPU utilization for a round-robin scheduler when:
   1. The time quantum is 1 millisecond
   2. The time quantum is 10 milliseconds
9. Create a program with two threads, both of which are CPU-bound. For example, they might compute Fibonacci numbers, prime numbers or digits of pi. Using the pthread scheduling configuration interface, assign different priorities to the threads. Measure the relative progress of the two threads, i.e., the ratio of the CPU time they receive as expressed in the number of results computed, as you change their relative priorities. Are you observing starvation or are threads receiving CPU times corresponding to the priority ratio?