CSC 110: Lab Activity #5

CSC 110 Lab 5
Operating Systems

Names: __________________________________________

Overview

In this lab you will study various algorithms that are used by operating systems for resource management.

CPU Scheduling

The operating system is responsible for scheduling use of the computer's CPU. There are many different algorithms that can be used. In this part of the lab, you will run a simple applet that illustrates how some of these algorithms work. Before doing so, give a short description of how each of the following scheduling algorithms decides which process to execute:

First-Come, First-Served

Shortest Job First

Shortest Job First with Preemption

Round Robin

Scheduling Algorithms
Now open the CPU Scheduling applet and see if your descriptions are accurate.

With the "Setup" tab open, choose First-Come First-Served of the algorithms for the Left CPU. Choose the same algorithm for the Right CPU and leave the rest of the settings as is.

Click on the "Run" tab and notice how the processes are executed on the CPU. The three columns on each CPU represent:

ProcId - This is the process identifier, which is a unique ID for each process. On the Setup screen, the default number of processes was 10, so you will see numbers from 0 to 9 under this column.
Length - This is the length of time (in milliseconds) that the process will need to run on the CPU.
Time Remaining - This represents the amount of time the specific process has left to execute. Notice that as the applet progresses, this time passes for the "executing process" (The one highlighted in yellow).

Notice how the chosen scheduling algorithm decides which process to execute next, and compare this with the description that you wrote above.

Do this for each of the four algorithms available in the applet.

Following your observations of each algorithm, make any corrections to the descriptions that you wrote of the algorithms above.

Comparing Algorithms

Use the applet to compare the performance of the FCFS with SJF algorithms.

Run it a couple of times to see if there is a general observation you can make about which algorithm finishes first. (You may need to use the step through button to see this) What do you notice?

Under what circumstances would you expect these algorithms to behave exactly the same?

Now compare SJF with preemptive SJF. What do you notice about the difference between these two algorithms?

Recall that a context switch is required when the CPU switches from executing one process to executing another. This takes some amount of time in a real system. The default in the applet setup is a 0ms context switch. See what happens when you increase the context switch time when comparing SJF with preemptive SJF. Describe what you observe, and explain why.

Have your instructor or TA initial your sheet here: _____________.

Evaluating Scheduling Performance

There are various ways to measure the performance of a scheduling algorithm. Here are a few:

CPU Utilization:
Throughput: Number of processes completed per unit time.
Turnaround Time: Mean time from submission to completion of process. So this is computed as an average over all processes.
Waiting Time: Amount of time spent ready to run but not running. This is computed for each process.

Let's look at FCFS scheduling. Consider the performance of the FCFS algorithm for three processes:

P1 (takes 24 seconds)
P2 (takes 3 seconds)
P3 (takes 3 seconds)

If arrive in order P1, P2, P3, compute the following:

Waiting Time?
Turnaround Time?
Throughput?

What about if processes come in order P2, P3, P1? Compute the following:

Waiting Time?
Turnaround Time?
Throughput?

Have your instructor or TA initial your sheet here: _____________.

Deadlock Management

The Dining Philosophers problem is a metaphor for a resource management problem in operating systems. The chopsticks represent shared resources, and the philosophers represent processes that sometimes need the resources.

Use this Dining Philosophers Applet to do the following:

Hit the Start button to begin watching the philosophers eat and think. (You may want to turn off the Audio from the Options menu, unless you don't mind the sound of munching philosophers).

Notice the color coded numbers above the heads of all of the philosophers. What do the different colors represent?

The Options menu allows you to change the execution of the applet. The default Solution to the deadlock problem is "Resource hierarchy." Explain what this means and how it works to prevent deadlock.

Hit the Suspend button and change the solution to "None (no deadlock prevention)". Make changes to the other settings to see if you can cause the philosophers to deadlock, and hit the Restart button. What changes did you make and why did it cause deadlock to occur?

Have your TA or instructor initial your sheet here: _____________.

Challenge Problems:

The Hierarchical Algorithm (with waiting) is a deadlock prevention algorithm that works as follows:

Given a request from process P for resource R, the resource manager follows these rules:

if the resource R does not exist, then
refuse the request
else
if process P is holding a resource R' with higher priority than resource R, then
refuse the request
else
let process P wait for the resource (in a queue)
and when the process reaches the front of the
queue, grant process P exclusive access to resource R
end if
end if

Here is a simple example of how this might work:

Suppose that a person needs both a knife and fork to eat.
Knife is given priority 2 and fork priority 1, assuming that zero is the highest priority.
Person P1 needs knife and fork and person P2 needs knife and fork.
Person P1 requests knife first because it is lower priority and then fork.
Person P2 also requests knife and then fork.
Only one of P1 or P2 will be granted the knife. Suppose it is P1.
Person P2 will wait for the knife to be free.
Then only P1 will request the fork.
The request will be granted.
Person P1 will use the knife and fork until finished.
Person P1 will release the knife and fork.
Then the pending request for the knife by person P2 will be granted.
Then Person P2 will immediately request the fork and this request will be granted.
Person P2 will use the knife and fork until finished.
Person P2 will release the knife and fork.

Question:

In the hierarchical algorithm for preventing deadlock, each resource type is assigned a unique integer as a priority, with 2 as lowest priority and 0 as highest priority. Suppose we have the following:

resource R1 has priority 2,
resource R2 has priority 1,
resource R3 has priority 0.

Given this sequence of requests and frees:

P1 requests R1,
P3 requests R3,
P1 requests R2,
P1 frees R2,
P2 requests R2,
P2 frees R2,
P3 requests R2,
P3 frees R2

Which of the above REQUESTS will be REFUSED by the hierarchical algorithm, and which will be GRANTED?

Have your TA or instructor initial your sheet here: _____________.