Disk Head Scheduling

126 views 11:23 am 0 Comments June 27, 2023

Lab 10 (Week 13)

Disk Head Scheduling

Purpose

After completing the exercises in this week (Lab 10), you will gain a better understanding through visual representation of several disk head scheduling algorithms including:

First-Come First-Served (FCFS)

Shortest-Seek-Time-First (SSTF)

SCAN (SCAN, C-SCAN)

LOOK, C-LOOK

Prerequisites

Before starting this exercise, you should have covered Chapter 11 (Mass Storage Structure) of the text. In particular, the disk head scheduling algorithms covered in Section 11.4 must be covered including FCFS, SSTF, SCAN, LOOK as well as the variations of these algorithms. It is especially important to understand the concept about the metric seek time — the time for the disk arm to move the heads to the cylinder containing the desired sector.

It is also useful to discuss the merits of each algorithm — Section 11.4.6 presents an overview of such a discussion.

Overview

In this lab, you will explore a simulation software (created by Steve Robbins) named “Disk Head Scheduling simulator”. This simulator provides you with a visual representation of process scheduling for the FCFS, SSTF, SCAN, C-SCAN, LOOK, and C-LOOK disk head scheduling algorithms.

There are two primary output mechanisms to demonstrate how the different algorithms schedule under different scenarios. The first is an output table illustrating the time required to move the disk head to the correct cylinder. This is known as seek time. In addition, each run of a scheduling algorithm can be illustrated with a graph illustrating the head movement of each algorithm. These graphs appear similar to Figures 11.4-11.8 in the text.

It is important to understand that the requests for disk blocks are generated dynamically for this simulator — similar to what happens in a real operating system. Section 12.4 of the text illustrates the various disk head scheduling algorithms with a static list of blocks on the cylinders {98, 183, 37, 122, 14, 124, 65, 67}. This strategy assumes no other requests arrive while these blocks are being serviced. This simulator is presented differently where the requests are generated dynamically.

You are strongly encouraged to explore this simulator and examine the various graphs that can be produced. The “live” graphs that you generate for yourselves are quite useful for your overall understanding of various disk head scheduling algorithms that are made available to contemporary operating systems.

The exercises in this lab consist of two parts:

In Part I you will explore various features of the simulator and generate a log file of your activity. You will also be asked to answer a few questions about the basic operational behavior of the simulator.

In Part II you will experiment with the simulator by changing various scheduling parameters as well as process characteristics and then complete a series of multiple choice and short answer questions.

Starting the Simulator

Download the Disk Head Scheduling simulator (disk.zip) from LearnJCU and extract the zip file. This produces a folder named disk.

The user manual for this simulator, disk_doc.html, is included in this folder. It is strongly suggested that you read through this documentation describing how the simulator operates prior to beginning the following exercises.

Exercise Tasks – Part I.

Perform the following steps using the disk head scheduling simulator

In the disk directory, execute ./rundisk (UNIX, Linux, Mac OS X) or rundisk.bat (Windows.) This will start the disk head scheduling simulator.

Click on the green button labeled Run Experiment in the right-hand side of the Disk Head Simulation window. This will start the simulation which involves servicing 24 disk head requests using the FCFS, SSTF, and C-LOOK disk head scheduling algorithms.

Terminate the simulator using the pink Quit button in the upper right-hand corner of the main window.

In the disk directory you will find the file diskheadconfig. This is the configuration file for the disk head scheduling simulator. The first line in this configuration file begins with user; edit the configuration file to change the value of user from New User to your name. Save and close the configuration file.

Execute the simulator again (as in Step 1).

Click the Open Log button in the left column of the main window to open a log file. After you have pushed this button, its name will change to Close Log.

Click the Run Experiment button again.

Click the Show Table Data button in the center column of the main window. A pop-up window illustrating a table of statistics should appear.

Return to the Disk Head Simulation window and click the button labeled Log Table Data in the left column. The table of statistics is now sent to the log file.

Click on the Show Run Data Graph button in the center column of the main window. This opens a pop-up window allowing you to draw a graph illustrating the head movement for the FCFS, SSTF, or C-LOOK algorithms; it also provides an option to choose all runs which displays the graph for all three algorithms.

Choose the all runs option and you will see three graphs, one illustrating the disk head movements for each of the three disk head scheduling algorithms. These graphs illustrate the same properties as the graphs in Figures 12.4 – 12.8 of your text.

Click the Log Image button at the bottom of each graph window. This sends the output of each graph to your log file. You may close each window after clicking its Log Image button.

Click on the Show Run Data Table button in the center column of the main window. This opens a pop-up window allowing you to draw a table for each of the three disk head scheduling algorithms.

Choose FCFS and a new window illustrating the various timing parameters for each block will appear.

Click the Log button in the upper right-hand corner of the Run Data Frame window to send this data to the log file, then close the window.

Repeat Steps 13-15 for the SSTF and C-LOOK options.

Click the Close Log button and then terminate the simulator. You have created a file called logfile.html in the disk directory.

Submit your log file — logfile.html — to your instructor per his or her instructions.

———————————————————————————————–

Questions – Part I.

Answer the following questions after completing Steps 1-18 above.

Examining the table generated in Step 8, which algorithm had the greatest total seek time?

a) FCFS
b) SSTF
c) C-LOOK

Examining the table generated in Step 8, which algorithm had the smallest total seek time?

a) FCFS
b) SSTF
c) C-LOOK

Examining the table generated in Step 8, which algorithm had the greatest mean seek movement?

a) FCFS
b) SSTF
c) C-LOOK

Examining the table generated in Step 8, which algorithm had the smallest mean seek request turnaround time?

a) FCFS
b) SSTF
c) C-LOOK

Examining the table in Step 13 for FCFS, which request had the longest turnaround time?

a) 4 to 36
b) 175 to 40
c) 191 to 39
d) 36 to 117

Examining the table in Step 13 for FCFS, which request had the shortest turnaround time?

a) 4 to 36
b) 39 to 35
c) 38 to 36
d) 40 to 39

Examining the table in Step 16 for SSTF, what is the shortest turnaround time?

a) 2.1
b) 0.0
c) 0.5
d) 0.8

Examining the table in Step 16 for C-LOOK, which request had the shortest turnaround time?

a) 4 to 36
b) 36 to 37
c) 31 to 31
d) 30 to 30

In the table in Step 16 for SSTF, which of the following explains why going from block 30 to block 30 requires a seek time of zero, yet a turnaround time > 0.

It still takes time to transfer the block.

There was a queue of pending requests.

The request for block 30 arrived at time 34.23, yet  didn’t start until time 36.223.

None of the above

Exercise Tasks – Part II.

In this section you will run the simulator for the six disk head scheduling algorithms presented in Section 11.4 of the text.

In the disk directory, there are two files:

myrun.run (the run file) – This run file specifies various parameters such as the number of disk block requests, inter-arrival times, and the numeric range of disk blocks requested

myexp.exp (the experiment file.) – The experiment file specifies the number of experiments that are to be run using the run file.

Each experiment in the experiment file runs the scheduler according to the parameters specifies in the run file. For example, if the experiment file myexp.exp contains the following:

name myexp
comment Six runs with different algorithms
run myrun key “FCFS” head FCFS
run myrun key “SSTF” head SSTF
run myrun key “LOOK” head LOOK
run myrun key “C-LOOK” head CLOOK
run myrun key “SCAN” head SCAN 200
run myrun key “C-SCAN” head CSCAN 200


this means the experiment specifies six runs will be performed, one for each of the six disk head scheduling algorithms presented in Section 11.4. The number following the SCAN and CSCAN algorithms specifies the last cylinder number for the disk.

If the run file myrun.run contains:

name myrun
comment This is myrun
start 4
movement linear 0.5  0.10
layout uniform 2
head clook
interArrival constant 2
nextBlock uniform 10 40
firstArrival 2.23
blockAbsolute
numBlocks 50
interArrival uniform 1 3
nextBlock uniform 100 200
firstArrival 3.123
numBlocks 50

this means each of the six experiments will first run with 50 disk block requests uniformly distributed between cylinders 10 and 40. It will then service another 50 disk block requests, this time uniformly distributed between cylinders 100 and 200. The disk head starts at the block on cylinder 4.

The user manual for this simulator, disk_doc.html, fully explains the parameters for the experiment and run files. It is strongly suggested that you read through this manual before proceeding, as well as keep it open while performing the following exercises.

Perform the following steps using the disk head scheduling simulator.

Using a text editor, replace the contents of myexp.exp and myrun.run with the experiment and run files shown above.

In the disk directory, execute ./rundisk (UNIX, Linux, Mac OS X) or rundisk.bat (Windows.) This will start the disk head scheduling simulator.

Click the Run Experiment button to start the experiment.

Click the Show Table Data and Show Run Data Table buttons.

———————————————————————————————–

Questions – Part II.

Answer the following questions after completing Steps 1-4 above.

Which algorithm had the greatest total seek time?

a) FCFS
b) SSTF
c) LOOK
d) SCAN

Which algorithm had the smallest total seek time?

a) SCAN
b) C-SCAN
c) LOOK
d) C-LOOK

Which algorithm had the greatest mean seek movement?

a) FCFS
b) SSTF
c) LOOK
d) SCAN

Which algorithm had the smallest mean seek request turnaround time?

a) SCAN
b) C-SCAN
c) LOOK
d) C-LOOK

What algorithm had the shortest maximum seek movement?

a) SCAN
b) C-SCAN
c) LOOK
d) C-LOOK

Click the Show Run Data Table for both the SCAN and C-SCAN algorithms. Initially the two algorithms service the same blocks.

After which block request do the two algorithms diverge?

a) 4 to 127
b) 198 to 200
c) 200 to 136
d) 0 to 13

Click the Show Run Data Table button for both the SCAN and LOOK algorithms. Initially, the two algorithms operate similarly. However, the 26th request for SCAN goes from 0 to 11, the 24th request for LOOK goes from 13 to 37 (bypassing the request for block 11 and only servicing the request for 11 much later.)


Which of the following explains why SCAN initially services the request for block 11 and LOOK services the request much later?

LOOK decided to turn around after servicing block 13.

SCAN always goes to the ends of the disk.

They are different algorithms with different requests.

The request for block 11 had not yet arrived when LOOK finished servicing block 13.

——————————————————————————————-

Assessment

1%

~ This is the End of Lab 10 ~

Tags: , , , , , , , , , , ,