Computer Science Chapter Exercises

3.8 Describe the differences among short-term, medium-term, and long term scheduling.

Short term chooses the next process from the ready processes while the medium term scheduler chooses processes currently in memory and swaps them out to disk, which later on get swapped back. Short term processes select new processes often. Long term schedulers choose from a pool currently waiting on disk and must wait a while before selecting the next process.

3.9 Describe the actions taken by a kernel to context-switch between processes.

When an interrupt occurs the operating system saves the PC and user stack pointer for current processes and gives control to kernel. Then, the clock interrupt handler saves the remaining registers and machine states in the PCB. The OS asks the scheduler what the next process to execute is and then the OS retrieves the state of that process and restores the registers. At this point, we’re back to where we started.

4.6 Provide two programming examples in which multithreading does not provide better performance than a single-threaded solution.

A shell program like C-shell has to closely monitor its own workspace, so multithreading is not better here. Also a sequential program like one that calculates tax returns.

4.14 A system with two dual-core processors has four processors available for scheduling. A CPU-intensive application is running on this system. All input is performed at program start-up, when a single file must be opened. Similarly, all output is performed just before the program terminates, when the program results must be written to a single file. Between startup and termination, the program is entirely CPU bound. Your task is to improve the performance of this application by multithreading it. The application runs on a system that uses the one-to-one threading model (each user thread maps to a kernel thread).

• How many threads will you create to perform the input and output? Explain.

Create enough threads to block system calls and no more to save efficiency – one thread for input and one for output.

• How many threads will you create for the CPU-intensive portion of the application? Explain.

Four because there should be as many threads as cores – any less is a waste of resources and more than that would not be able to run.

4.18 Consider a multicore system and a multithreaded program written using the many-to-many threading model. Let the number of user-level threads in the program be greater than the number of processing cores in the system. Discuss the performance implications of the following scenarios.

1. The number of kernel threads allocated to the program is less than the number of processing cores.

Some processes will be idle because the scheduler can only map kernel threads to processors – not user level threads.

1. The number of kernel threads allocated to the program is equal to the number of processing cores.

All processors may be used at the same time but a kernel thread blocking inside the kernel could cause a processor to be idle.

1. The number of kernel threads allocated to the program is greater than the number of processing cores but less than the number of user-level threads.

A blocked kernel thread here can be swapped for another that is available and ready

6.16 Consider the following set of processes, with the length of the CPU burst given in milliseconds:

The processes are assumed to have arrived in the order P1, P2, P3, P4, P5, all at time 0.

1. Draw four Gantt charts that illustrate the execution of these processes using the following scheduling algorithms: FCFS, SJF, nonpreemptive priority (a larger priority number implies a higher priority), and RR (quantum = 2).

FCFS

RR

SJF

Priority

1. What is the turnaround time of each process for each of the scheduling algorithms in part a?

1. What is the waiting time of each process for each of these scheduling algorithms?

1. Which of the algorithms results in the minimum average waiting time (over all processes)?

Shortest job first

6.20 Consider a variant of the RR scheduling algorithm in which 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?

Essentially increasing the priority of the process by giving it more attention

1. What would be two major advantages and two disadvantages of this scheme?

Advantages – more important jobs are given higher priority and it prevents starvation of lower priority ones
Disadvantages – context switching has greater effects and it is more difficult to remove running processes.

1. How would you modify the basic RR algorithm to achieve the same effect without the duplicate pointers?

Have two or more quantums possible to give more time to processes that should get higher priority.

6.24 Explain the differences in how much the following scheduling algorithms discriminate in favor of short processes:

1. FCFS

Discriminates short jobs because after longer jobs they have had a long wait time.

1. RR

All jobs are treated equal so short jobs leave sooner because they finish first.

1. Multilevel feedback queues

Like RR, they discriminate in favor of short jobs.