Operating Systems--Spring 2011

Home | | Schedule | | Assignments | | Lecture Notes

Homework 2

Due: Thursday, March 24, in class

Question 1. Briefly define each of these terms (one or two sentences each):

1. time slice
2. thread
3. ready queue
4. CPU burst
5. turnaround time
6. throughput
7. aging
8. dispatching
9. CPU utilization
10. CPU efficiency
11. starvation (in relation to a CPU scheduling algorithm)

Question 2. Suppose that the OS needs to choose and dispatch another process to execute and that, at this time, there are processes in both the ready state and the ready-suspend state. Furthermore, suppose that at least one process in the ready-suspend state has higher scheduling priority than any of the processes in the ready state. Two extreme policies for deciding which process to execute are: (1) Always dispatch a process in the ready state. (2) Always dispatch the highest-priority process. What is a concern with each of these two policies? Is there an intermediate policy that tries to balance these concerns?

Question 3. Thread questions:

• a. List three reasons for wanting to use multiple threads in a process.

• b. If a process exits and there are still threads of that process executing, will they continue to execute? Explain.

• c. What is one advantage and one disadvantage of a process using user-level threads over a process using kernel-level threads?

• d. Suppose two processes are executing, both of which are using multiple kernel-level threads. Is a context switch between two threads within one processes less work than a context switch between two threads in different processes? Explain.

• e. Suppose two processes are executing, both of which are using multiple user-level threads. Is a context switch between two threads within one processes less work than a context switch between two threads in different processes? Explain.

Question 4. Suppose the following jobs are to be executed in a uniprocessor system.

Assume the overhead of context switching is one time unit. For each of the following scheduling methods, give (i) a timing chart (Gantt diagram) to illustrate the execution sequence, (ii) the average job turnaround time, (iii) the normalized turnaround time for each job, and (iv) the CPU efficiency.

1. FCFS (first-come-first-served)
2. SJF (shortest-job-first)
3. SRTN (shortest-remaining-time-next)
4. RR (round-robin), quantum = 3
5. Multilevel Feedback Queue with queues numbered 1-10, quantum = 2ⁱ, where i is the queue level number and processes are initially placed in the first queue (i.e., level 1). In this scheduling policy, each process executes at a particular level for one quantum and then moves down a level; processes never move up a level.

Question 5. What type of process is generally favored by a multilevel feedback queueing scheduler, a CPU-bound process or an I/O-bound process? Briefly explain why.

Question 6. Consider a variant of the RR scheduling algorithm where the entries in the ready queue are pointers to the PCBs.

1. What would be the effect of putting two pointers to the same process in the ready queue?
2. What would be the major advantage of this scheme?
3. How could you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

Question 7. What would happen if you executed the following piece of code:

main() 
{ 
     for(;;)
          fork();
}

Note: Don't try this on a real machine.

Completed homework:

• Turn in your typed answers to the homework questions (and drawn timing charts) by Thursday, March 24 in class.

Constance Royden--croyden@mathcs.holycross.edu
Computer Science 346--Operating Systems
Date Created: January 9, 2004
Last Modified: March 2, 2011
Page Expires: January 8, 2012