Skip to main content

操作系统设备管理 Device Management

Disk Structure​

  • Platter (盘面): One disk has several platters.
  • Track (磁道): A circular band on the surface of a disk. A disk surface can have multiple tracks.
  • Track Sector (扇区): An arc segment of a track. A track can have multiple sectors, and it is the smallest physical storage unit, commonly available in sizes of 512 bytes and 4 KB.
  • Head (磁头): Positioned very close to the disk surface, it converts the magnetic field on the disk surface into electrical signals (read) or converts electrical signals into the magnetic field on the disk surface (write).
  • Actuator arm (制动手臂): Moves the head between tracks.
  • Spindle (主轴): Rotates the entire disk surface.

image-20240521010305707

Disk Scheduling Algorithm​

The following are key factors to read/write a disk block.

  • Rotation Time. The time taken for the spindle to rotate the disk so that the magnetic head moves to the appropriate sector.
  • Seek Time. The time taken for the actuator arm to move the read/write head to the appropriate track.
  • Actual Data Transfer Time.

Among these, seek time is the longest. Therefore, the primary goal of disk scheduling is to minimize the average seek time.

There are many scheduling algorithms, we will discuss the important ones.

1. First Come First Served (FCFS)​

FCFS is the simplest soluttion.

The requests are processed based on the time they arrive in the disk time.

Pros:

  1. Fair for each requests.
  2. No indefinite delay

Cons:

  1. The average seek time is high because it does not try to optimize the seek time.

The following is an example.

  • The current position of head is: 50

  • Suppose the order of request is [82,170,43,140,24,16,190]

  • So, total overhead movement (total distance covered by the disk arm) = (82-50)+(170-82)+(170-43)+(140-43)+(140-24)+(24-16)+(190-16) = 642

First Come First Serve

2. Shortest Seek Time First (SSTF)​

Prioritize the request which is nearest to the current head.

Pros:

  1. The average seek time decreases.
  2. Throughput increases.

Cons:

  1. Overhead to calculate seek time in advance
  2. Not fair. Can cause starvation for a request with high seek time as compared to newly incoming requests.

In the following example:

  • The current position of head is: 50

  • Suppose the order of request is [82,170,43,140,24,16,190]

  • So, total overhead movement (total distance covered by the disk arm) = (50-43)+(43-24)+(24-16)+(82-16)+(140-82)+(170-140)+(190-170) = 208

Shortest Seek Time First

3. Elevator Algorithm (SCAN)​

The elevator always moves in the same direction, and changes the moving direction until there are no requests in the current direction.

Pros:

  1. Average response time
  2. High throughput
  3. Low variance of response time
  4. Resolve the starvation problem in the Shortest Seek Time First algorithm (SSTF)

Cons:

  1. Long waiting time for the requests with location which was just visited.

In the following example:

  • The current position of head is: 50

  • Suppose the order of request is [82,170,43,140,24,16,190]

  • So, total overhead movement (total distance covered by the disk arm) = (199-50) + (199-16) = 332

image-20240521014132591

Reference​

  1. Disk Scheudling Algorithm
  2. Device Management