COMP2006 - Operating Systems 1/5 1st Semester 2022
CRICOS Number: 00301J
COMP2006 - Operating Systems
CURTIN UNIVERSITY
Discipline of Computing
Disk Scheduling Simulator
Due Date: 4PM, Monday 9 May, 2022
The objective of this programming assignment is to give you some experiences in using
multiple threads and their inter-thread communications, in addition to implementing some
disk scheduling algorithms. You will learn how to create threads and solve the critical section
problems to complete the assignment. Note that the details of disk scheduling algorithms are
discussed in Lecture 9; however, you should be able to complete the assignment by following
the information in this assignment specification. You may also read the slides for Lecture 1
and Lecture 9 (materials on disk scheduling) when needed.
As discussed in Lecture 1, disk access time has two major components: (i) seek time - the
time for the disk arm to move its read/write heads to the cylinder containing the desired
sector, and (ii) rotational latency - the time for the disk to rotate such that the disk head is in
position to access the desired sector. A disk scheduling algorithm aims to minimize the seek
time.
A. Background
Consider a disk that contains n cylinders, where cylinder numbers start from 0, i.e., number 0,
1, 2, 3, … 199 for a disk with n=200 cylinders. The following shows an example of an input
file used in your assignment for a set of disk sector requests for n=100. Notice that each
number in the file is separated by a space.
200 53 65 98 183 37 122 14 124 65 67
The first number in the file represents total cylinders n of the disk i.e., n=200 cylinders. The
second number represents current position of the disk’s read/write head, i.e., it is currently at
cylinder 53. The third number represents the previous disk request, i.e., 65. Thus, from the
information of previous disk request (65) and current position (53), we know the direction of
the head’s movement, i.e., from 65 to 53, i.e., the head moves towards smaller cylinder
numbers. Note that if the current position is 65, and previous request is 53, the head goes
towards larger cylinder numbers. Each of the remaining numbers in the file represents
cylinder number, i.e., a set of disk requests for sectors located in cylinders 98, 183, 37, 122,
14, 124, 65, and 67. Here, we assume that all disk requests come at the same time, and there is
no further request. The simulator aims to generate a schedule to serve the requests that
minimizes the movement of the disk’s read/write head, i.e., the seek time.
There are several disk scheduling algorithms, e.g., First Come First Serve (FCFS), Shortest
Seek Time First (SSTF), SCAN, LOOK, circular SCAN (C-SCAN), and circular LOOK
(C-LOOK). Lecture 9 discusses the merits of the algorithms.
--------------------------------------------------------------------------------------------------------------------------------------
COMP2006 - Operating Systems 2/5 1st Semester 2022
CRICOS Number: 00301J
• FCFS algorithm considers the disk requests in a first in first out (FIFO) queue. Thus, using
FCFS scheduler, the head firstly moves from current position 53 to cylinder 98 that
requires 98 – 53 = 45 movements. Next, it serves the request at cylinder 183 (183 – 98 =
85 movements), followed by the requests at cylinders 37 (183 – 37 = 146), 122 (122 – 37 =
85), 14 (122 – 14 = 108), 124 (124 – 14 = 110), 65 (124 – 65 = 59), and 67 (67 – 65 = 2).
Thus, using FCFS schedule, the total cylinder movement is 45 + 85 + 146 + 85 + 108 +
110 + 59 + 2 = 640.
• SSTF selects the request with the minimum seek time from the current head position. For
the example, SSTF firstly serves the request at cylinder 65 because it is the closest from
the current position 53, i.e., 65 – 53 = 12. Then, it will serve the request at cylinder 67 (67
– 65 = 2), followed by the request, in order, at cylinders 37, 14, 98, 122, 124, 183. Thus,
the complete schedule is 53 à 65 à 67 à 37 à 14 à 98 à 122 à 124 à 183 with a
total seek time of 12 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 236.
• In SCAN, the disk arm starts at one end of the disk, and moves toward the other end,
servicing requests until it gets to the other end of the disk, where the head movement is
reversed, and servicing continues. For the example, the schedule following SCAN is 53 à
37 à 14 à 0 à 65 à 67 à 98 à 122 à 124 à 183 with a total cylinder movement of
16 (= 53 – 37) + 23 (= 37 – 14) + 14 + 65 + 2 + 31 + 24 + 2 + 59 = 236. Notice the
following: (i) SCAN firstly serves the request at cylinder 37 because the head moves
towards the smaller number, i.e., the current position is at 53, and the previous position is
at 65; (ii) it moves from 14 to 0 because SCAN moves the head from one end to the other
end of the cylinders.
• C-SCAN is like SCAN. However, in C-SCAN, (i) the head moves from one end of the
disk to the other, servicing requests as it goes, and (ii) when it reaches one end, it
immediately returns to the other end of the disk, without servicing any requests on the
return trip. For the example, the schedule following C-SCAN is 53 à 37 à 14 à 0 à
199 à 183 à 124 à 122 à 98 à 67 à 65 with a total cylinder movement of 16 (= 53 –
37) + 23 (= 37 – 14) + 14 + 199 (= 199 – 0) + 16 + 59 + 2 + 24 + 31 + 2 = 386. Notice the
following: (i) SCAN firstly serves the request at cylinder 37 because the head moves
towards the smaller number, i.e., the current position is at 53, and the previous position is
at 65; (ii) it moves from 14 to 0 because C-SCAN moves the head from one end to the
other end of the cylinders; (iii) it moves from 0 to 199 because C-SCAN treats the
cylinders as a circular list that wraps around from one end of the cylinder to the other end.
• LOOK is like SCAN. However, in LOOK, the disk arm only goes as far as the last request
in each direction, then reverses direction immediately, without going all the way to the end
of the disk. For the example, the schedule following LOOK is 53 à 37 à 14 à 65 à 67
à 98 à 122 à 124 à 183 with a total cylinder movement of 16 (= 53 – 37) + 23 (= 37 –
14) + 51 (= 65-14) + 2 + 31 + 24 + 2 + 59 = 208.
• C-LOOK is like LOOK. However, like in C-SCAN, in C-LOOK, when the disk arm
reaches one end of the disk, it immediately returns to the other end of the disk, without
servicing any requests on the return trip. Like in LOOK, the disk arm only goes as far as
the last request in each direction, then reverses direction immediately, without going all the
way to the end of the disk. For the example, the schedule following C-LOOK is 53 à 37
--------------------------------------------------------------------------------------------------------------------------------------
COMP2006 - Operating Systems 3/5 1st Semester 2022
CRICOS Number: 00301J
à 14 à 183 à 124 à 122 à 98 à 67 à 65 with a total cylinder movement of 16 (= 53
– 37) + 23 (= 37 – 14) + 169 + 59 + 2 + 24 + 31 + 2 = 326.
B. Assignment Requirements
1) (Total: 40 marks). Write a program in C language, called scheduler.c, that includes six
functions to implement the six disk scheduling algorithms, i.e.,
a) (5 marks). First Come First Serve (FCFS).
b) (5 marks). Shortest Seek Time First (SSTF).
c) (5 marks). SCAN.
d) (5 marks). C-SCAN.
e) (5 marks). LOOK.
f) (5 marks). C-LOOK.
(10 marks). The program waits for an input file, e.g., input1, from the user that contains:
(i) total number of cylinders, (ii) current position of read/write head, (iii) previous
position of the head, and (iv) a list of disk requests; see the format of input file in the
example. While waiting for the input, the program should show a user prompt “Disk
Scheduler Simulation:”. Assume the input file name is no longer than 10 characters, e.g.,
input1, request_list, etc.
The program should print the seek time (i.e., the total number of head movements) for
each of the six schedulers, and then wait for another user input. The program terminates if
the user gives “QUIT” as input. The format of the output is as follows.
For input1:
FCFS: 640.
SSTF: 236.
SCAN: 236.
C-SCAN: 386.
LOOK: 222.
C-LOOK: 326.
2) (Total: 40 marks). Write a program in C language, called simulator.c that does the
following.
a) (10 marks). The parent thread creates six child threads, i.e., thread A, B, C, D, E,
and F that respectively runs the FCFS, SSTF program, SCAN, C-SCAN, LOOK, and
C-LOOK disk schedulers. Threads A, B, C, D, E, and F block while waiting for input
from the parent thread.
b) (5 marks). The parent thread waits for an input from the user. The input can be
either a file name, e.g., input1, or “QUIT”. When the parent thread receives “QUIT”
--------------------------------------------------------------------------------------------------------------------------------------
COMP2006 - Operating Systems 4/5 1st Semester 2022
CRICOS Number: 00301J
as input, it tells threads A, B, C, D, E, and F to terminate, and terminates itself. Each
child thread should print the following message (Thread_ID is the ID of the thread):
Thread_ID has terminated
c) For each file name, e.g., input1, the program does the following:
• (10 marks). The parent thread stores the contents of the input, e.g., input1, in a
buffer, called buffer1, and signals thread A, B, C, D, E, and F to read buffer1.
The parent thread then blocks while waiting for results from threads A, B, C, D,
E, and F, i.e., the seek time. Notice that the parent thread acts as a producer and
threads A, B, C, D, E, and F as the consumers for buffer1 of size n+3; buffer1
stores only the content of input file that has n disk requests and three other
information; see the format of input. The simulator must solve any possible
synchronization/critical section issues among the threads. You must describe the
possible issues and how you solve the issues. Use pthread_create(),
pthread_mutex_lock(), pthread_mutex_unlock(), pthread_cond_wait(), and
pthread_cond_signal() in your program.
• (10 marks). Each child thread that has computed the seek time writes the result in
another buffer, called buffer2, and signals the parent thread to read the result.
Then the child thread blocks waiting for another input from the parent thread. For
this case, the parent thread acts as a consumer and threads A, B, C, D, E, and F as
the producers for a bounded buffer of size 1, i.e., buffer2 can store only one seek
time at a time. The simulator must solve any possible synchronization/critical
section issues among the threads. You must describe the possible issues and how
you solve the issues. Use pthread_create(), pthread_mutex_lock(),
pthread_mutex_unlock(), pthread_cond_wait(), and pthread_cond_signal() in your
program.
• (5 marks). After the parent thread receives the results from the six threads, it
should print the results, e.g.,
For input1:
FCFS: 640.
SSTF: 236.
SCAN: 236.
C-SCAN: 386.
LOOK: 222.
C-LOOK: 326.
g) You MAY make your own assumptions/requirements other than those already given.
However, YOU HAVE TO DOCUMENT ANY ADDITIONAL
ASSUMPTIONS/LIMITATIONS FOR YOUR IMPLEMENTATIONS.
--------------------------------------------------------------------------------------------------------------------------------------
COMP2006 - Operating Systems 5/5 1st Semester 2022
CRICOS Number: 00301J
Instruction for submission
1. Assignment submission is compulsory. Students will be penalized by a deduction of 10%
per calendar day for a late submission. An assessment more than seven calendar days
overdue will not be marked and will receive a mark of 0.
2. You must (i) submit the soft copy of the report to the unit Blackboard (in one zip file),
and (ii) put your program files i.e., scheduler.c, simulator.c, and other files, e.g., makefile,
sim_input and sim_out, in your home directory named OS/assignment.
3. Your assignment report should include:
• A signed cover page that explicitly states the submitted assignment is your own work.
The cover includes the words “Operating Systems Assignment”, and your name in the
form: family, other names. Your name should be as recorded in the student database.
• Software solution of your assignment that includes (i) all source code for the
programs with proper in-line and header documentation. Use proper indentation so
that your code can be easily read. Make sure that you use meaningful variable names
and delete all unnecessary comments that you created while debugging your program;
and (ii) readme file that, among others, explains how to compile your program and
how to run the program.
• Detailed discussion on how any mutual exclusion is achieved and what processes /
threads access the shared resources.
• Description of any cases for which your program is not working correctly or how you
test your program that make you believe it works perfectly.
• Sample inputs and outputs from your running programs. Explain if the outputs are
correct / incorrect.
Your report will be assessed (worth 20% of the overall assignment mark).
Failure to meet these requirements may result in the assignment not being marked.