2 Exercise ProcessManagement

CPU Scheduling
Practice Exercises
2.1:
A CPU-scheduling algorithm determines an order for the execution of its
scheduled processes. Given n processes to be scheduled on one processor, how
many different schedules are possible? Give a formula in terms of n.
2.2:
Explain the difference between preemptive and nonpreemptive
scheduling?
2.3:
Suppose that the following processes arrive for execution at the times
indicated. Each process will run for the amount of time listed. In answering the
questions, use nonpreemptive scheduling, and base all decisions on the
information you have at the time the decision must be made.
Process Arrival Time Burst Time

P1 0.0 8
P2 0.4 4
P3 1.0 1
a. What is the average turnaround time for these processes with the
FCFS scheduling algorithm?
b. What is the average turnaround time for these processes with the
SJF scheduling algorithm?
c. The SJF algorithm is supposed to improve performance, but notice that
we chose to run process P1 at time 0 because we did not know that two
shorter processes would arrive soon. Compute what the average
turnaround time will be if the CPU is left idle for the first 1 unit and
then SJF scheduling is used. Remember that processes P1 and P2 are
waiting during this idle time, so their waiting time may increase. This
algorithm could be known as future-knowledge scheduling.
2.4:
Consider the following set of processes, with the length of the
CPU burst time given in milliseconds:
Process Burst Time Priority

P1 2 2
P2 1 1
P3 8 4
P4 4 2
P5 5 3
The processes are assumed to have arrived in the order P1, P2, P3,
P4, P5, all at time 0.
a. Draw four Gantt charts that illustrate the execution of these pro-
cesses using the following scheduling algorithms: FCFS, SJF,
nonpreemptive priority (a larger priority number implies a
higher priority), and RR (quantum = 2).
b. What is the turnaround time of each process for each of the
scheduling algorithms in part a?
c. What is the waiting time of each process for each of these
scheduling algorithms?
d. Which of the algorithms results in the minimum average waiting
time (over all processes)?
2.5:
The following processes are being scheduled using a preemptive, round-
robin scheduling algorithm.
Process Priorit Burs Arrival
P1 40 20 0
P2 30 25 25
P3 30 25 30
P4 35 15 60
P5 5 10 100
P6 10 10 105
Each process is assigned a numerical priority, with a higher number indi-

cating a higher relative priority. In addition to the processes listed above, the
system also has an idle task (which consumes no CPU resources and is
identified as Pidle). This task has priority 0 and is scheduled when ever the
system has no other available processes to run. The length of a time quantum
is 10 units. If a process is preempted by a higher priority process, the
preempted process is placed at the end of the queue.
a. Show the scheduling order of the processes using a Gantt chart.
b. What is the turnaround time for each process?
c. What is the waiting time for each process?
d. What is the CPU utilization rate?
2.6:
What advantage is there in having different time-quantum sizes at
different levels of a multilevel queueing system?
2.7:
Many CPU-scheduling algorithms are parameterized. For example, the
RR algorithm requires a parameter to indicate the time slice. Multilevel
feedback queues require parameters to define the number of queues, the
scheduling algorithms for each queue, the criteria used to move processes
between queues, and so on.
These algorithms are thus really sets of algorithms (for example, the set
of RR algorithms for all time slices, and so on). One set of algorithms may
include another (for example, the FCFS algorithm is the RR algorithm with an
infinite time quantum). What (if any) relation holds between the following
pairs of algorithm sets?
a. Priority and SJF
b. Multilevel feedback queues and FCFS
c. Priority and FCFS
d. RR and SJF
2.8:
Suppose that a CPU scheduling algorithm favors those processes that
have used the least processor time in the recent past. Why will this
algorithm favor I/O-bound programs and yet not permanently starve CPU-
bound programs?
2.9:
Distinguish between PCS and SCS scheduling?
2.10:
The traditional UNIX scheduler enforces an inverse relationship between
priority numbers and priorities: the higher the number, the lower the priority.
The scheduler recalculates process priorities once per second using the
following function:
Priority = (recent CPU usage / 2) + base
where base = 60 and recent CPU usage refers to a value indicating how often a
process has used the CPU since priorities were last recalculated. Assume that
recent CPU usage for process P1 is 40, for process P2 is 18, and for process P3
is 10. What will be the new priorities for these three processes when priorities
are recalculated? Based on this information, does the traditional UNIX
scheduler raise or lower the relative priority of a CPU-bound process?

2 Exercise ProcessManagement

Uploaded by

Copyright:

Available Formats

2 Exercise ProcessManagement

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

2 Exercise ProcessManagement

Uploaded by

Copyright:

Available Formats

CPU Scheduling

Process Arrival Time Burst Time

Process Burst Time Priority

Each process is assigned a numerical priority, with a higher number indi-

You might also like