联系方式

  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-21:00
  • 微信:codinghelp

您当前位置:首页 >> Python编程Python编程

日期:2022-04-21 08:21

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.


版权所有:编程辅导网 2021 All Rights Reserved 联系方式:QQ:99515681 微信:codinghelp 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。 站长地图

python代写
微信客服:codinghelp