Assignment 6: Chapter 4 and 5
This assignment is to be completed individually, not as a group.
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.
- 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.)
- 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
ρ = λ / μ.
- 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
- Which of the following components of program state are shared across
threads in a multithreaded process?
- Register values
- Heap memory
- Global variables
- Stack memory
- 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
- 5.4: Consider the following set of processes, with the length of the
CPU-burst time given in milliseconds:
The processes are assumed to have arrived in the order P1 , P2 , P3 , P4, P5 , all at time 0.
|Process ||Burst Time ||Priority |
|P1 ||10 ||3
|P2 ||1 ||1
|P3 ||2 ||3
|P4 ||1 ||4
|P5 ||5 ||2
- 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.
- What is the turnaround time of each process for each of the
scheduling algorithms in part a?
- What is the waiting time of each process for each of the scheduling
algorithms in part a?
- Which of the schedules in part a results in the minimal average
waiting time (over all processes)?
- 5.5: Which of the following scheduling algorithms could result in
- First-come, first-served
- Shortest job first
- Round robin
- 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
- The time quantum is 1 millisecond
- The time quantum is 10 milliseconds
- 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?
by Henning Schulzrinne