Sstf Disk Algorithm Coding

Jul 06, 2019 Disk scheduling is done by operating systems to schedule I/O requests arriving for the disk and the algorithm used for the disk scheduling is called Disk Scheduling Algorithm. In this post, we will discuss the Shortest Seek Time First Disk Scheduling Algorithm. As the name suggests, the I/O requests are addressed in the order where the distance between the head and the I/O request is least. SCAN Scheduling algorithm – The disk arm starts at one end of the disk, and moves toward the other end, servicing requests as it reaches each cylinder, until it gets to the other end of the disk. At the other end, the direction of head movement is reversed, and servicing continues. The head continuously scans back and forth across the disk. Switching the direction of head frequently slows down the algorithm. PRACTICE PROBLEMS BASED ON SSTF DISK SCHEDULING ALGORITHM- Problem-01: Consider a disk queue with requests for I/O to blocks on cylinders 98, 183, 41, 122, 14, 124, 65, 67. The SSTF scheduling algorithm is used.

A disk is both an input device and an output device. Output device is a component of human-computer interaction, which is used for data output. Input device: a device that inputs data and information to a computer.

So, using a disk is roughly the same as using a monitor and keyboard

A disk is a three-dimensional structure composed of disks. The upper and lower sides of a disk are readable and writable

The magnetic disk uses the magnetic effect of current to magnetize some electrical signals and store them in the disk to represent some information.

The hard disk is divided into Heads, cylinders and sectors
Heads: there is a head on the front and back sides of each disk, and one head corresponds to one side of a magnetic sheet. The number of magnetic heads can be used to indicate which magnetic surface the data is on

Cylinder: concentric tracks with the same radius in all disk surfaces form a 'cylinder'. This series of tracks are stacked vertically to form a cylindrical shape

Sector: the track is divided into several small sections, i.e. sectors. The capacity of each sector is 512 bytes. In essence, the size is a compromise between the transmission time of disk data and the waste of disk fragments

Hard disk capacity = number of heads × Cylinders × sector number × 512 bytes

Structure overview:

1.IO process introduction

Disk I/O process: controller – > seek – > rotate – > transfer

1. Move the head to the corresponding track
2. The track starts to rotate and goes to the corresponding sector
3. At this time, when it turns again, the magnetic generates electricity, the magnetic signal becomes an electrical signal, and then the data is read
4. Read the memory buffer and modify the memory buffer by one byte
5. Then continue to turn inside again. At this time, electromagnetism is generated and bytes are written to the track

Move the magnetic head to the corresponding track, then rotate the track and move to the corresponding sector. While rotating, conduct magnetoelectricity, electro magnetism, and interactive reading and writing of data with the memory buffer

2. Use disk directly

Just write cylinder, head, sector and cache location to the controller
If you want to write a byte to a sector of the disk, you need to know which head in the cylinder corresponding to this sector sends these parameters to the disk controller, and then the disk controller drives the disk to write data according to these parameters

(1) Disk read / write request function do_hd_request()

(2) Disk drive core code hd_out()

The above methods require too many parameters to be passed, which is not convenient enough

3. Disk block number read / write disk (layer 1 abstraction)

Pack the cylinder, head and sector into a disk block
The disk drive is responsible for calculating cyl, head, sec(CHS) from the block
Suppose that the addressing of the sector is as follows, (the adjacent disk blocks of the block can be read out quickly)
Sector 1 is the next sector in the rotation direction of sector 0. Assuming that there are six sectors on a disk, sector 0-5 is on the first disk, and sector 6 is under the vertical direction of sector 0
Calculation formula: block = c * (heads * sectors) + h*heads * sectors + s

Sectors is the number of sectors per disk, and Heads is the number of Heads of the disk

Sector number = cylinder number × (how many sectors does a cylinder have) + disk number × (how many sectors are there on a disk) + sector code

C, H and S are calculated according to the sector number sector

S = sector%Sectors

Establishing a mapping from C, H and S sector addresses to sector numbers through addressing is the central task of the first layer abstraction of the file system. Multiple sectors with consecutive sector numbers are a disk block

Disk access time
Disk access time = write controller time + seek time + rotation time + transfer time
(it mainly refers to the seek time, long rotation time, and the adjacent disc blocks shall be able to read quickly)

Read / write disk by disk number

With a disk block, the disk read / write request sent by the user is the disk block number blocknr. Since the disk block is a continuous number of sectors, the sector number can be easily calculated, that is, sector = blocknr × Block size (block size describes the size of the disk block)

4. Queue read / write disk (layer 2 abstraction)

There are usually multiple processes in the operating system, and each process will make disk block access requests, so it is necessary to use queues to manage access requests, which is the second layer of abstraction of the operating system for disk management

Multiple disk access requests appear in the request queue and need to be scheduled

Scheduling objective: small average delay
Scheduling algorithm:

(1)FCFS disk scheduling algorithm

The most intuitive and fair scheduling

(2)SSTF disk scheduling

Process the past requests during the movement (shortest seek time first)

(3)SCAN disk scheduling

SSTF + does not turn back halfway: every request has a processing opportunity

(4)C-SCAN disk scheduling (elevator algorithm)

SCAN + moves directly to the other end: requests from both ends can be processed quickly
This is based on the elevator model in life. There are two situations when the elevator rises and falls. When the elevator rises, the end point of this rise is the highest request floor; When the elevator descends, the end point of this descent is the lowest requested floor

IN_ORDER()

I see_ The function of order() can analyze the elevator algorithm

Tip: here is a summary of the article:

Summary: raw disk write process

Webeduclick.comComputer Science Tutorials

Disk Scheduling Algorithms:

Disk scheduling algorithms are the algorithms that are used for scheduling a disk. There are five types of Disk Scheduling Algorithms are available:
1. FCFS Scheduling
2. SSTF Scheduling
3. SCAN Scheduling
4. C-scan Scheduling
5. Look Scheduling

FCFS Scheduling:

The expansion of FCFS is First-Come, First-Served. It is the simplest disk scheduling algorithm of all. But it does not provide faster service.
Example: Consider a disk queue with requests for I/O to block cylinders.

87, 160, 40, 140, 36, 72, 66, 15
In that order, if the disk head is initially at cylinder 60. Then the total head movement of is
=(60 to 87)+(87 to 160)+(160 to 40)+(40 to 140)+(140 to 36)+(36 to 72)+(72 to 66)+(66 to 15)
= (27+83+130+110+114+36+6+51)
= 557 cylinders
∴ The average head movements are= 557/8 = 69.6 cylinders

SSTF Scheduling:

The expansion of SSTF is shortest seek time first. This algorithm selects the request with the minimum to seek time from the current head position.
Example: Consider the previous disk queue with requests for I/O to block cylinders.

87, 160, 40, 140, 36, 72, 66, 15  The total head movements of this algorithm is
=(60 to 66)+(66 to 72)+(72 to 87)+(87 to 40)+(40 to 36)+(36 to 15)+(15 to 140)+(140 to 160)
= (6+6+15+37+4+21+135+20)
= 244 cylinders ∴ The average head movements are = 244/8 = 30.5 cylinders

SCAN Scheduling:

Sstf Disk Algorithm Coding Pdf

The SCAN algorithm is called ‘Elevator algorithm‘. In this, the disk arm starts at one end of the disk and moves towards the other end, while in the means time all request is serving until it gets other ends of the disk. At the other end, the direction of the head movement is reversed, and servicing is continuous. That’s why is this algorithm is called an elevator algorithm.

C-scan Scheduling:

Sstf Disk Algorithm Coding Questions

The main drawback in SCAN scheduling is the waiting time isn’t uniformly. Some requests are waiting much time, some requests are servicing immediately, we can overcome this drawback with the C-Scan algorithm. It is designed to provide a more uniform wait time. This algorithm moves the head from one end to the other ends of the disk, servicing the request along the way. When the head reaches the other end, it immediately returns to the beginning of the disk, without servicing any requests on the return trip.

Look Scheduling:

Sstf Disk Algorithm Coding Pdf

In Look Scheduling, the arm goes only as far as the final request in each direction. Then it reverses the direction immediately, without reach the end of the disk.