Skip to content

Disk Management

Disk organization and management

Disks are high-speed, large-capacity storage devices commonly used in modern computer systems. The following are the key points of disk organization and management:

Disk structure

  • Disks are composed of multiple platters, each platter has multiple surfaces, and each surface has multiple tracks. Tracks are further divided into sectors.
  • The address of disk space is determined by three parameters: cylinder number, head number, and sector number, indicating a specific physical location.
  • Calculation formula:
  • Block number \( b = k + s \times (j + i \times t) \)
  • Where \( k \) is the sector number, \( s \) is the number of sectors per track, \( j \) is the head number, \( i \) is the cylinder number, and \( t \) is the number of tracks per cylinder.

Disk space management

  • Free block table method: record the addresses of all free blocks.
  • Free Block Chain Method: Use a linked list to connect all free blocks.
  • Bitmap Method: Use a bitmap to indicate disk usage, with a bit value of 0 indicating free and 1 indicating occupied.
  • Group Link Method: Link free blocks in groups, suitable for large-capacity disks.

Disk Scheduling Algorithm

Disk scheduling algorithms are used to optimize disk access time and reduce seek time. Common scheduling algorithms include:

First Come First Served (FCFS)

  • Process requests in the order they arrive, the algorithm is simple and fair.
  • Disadvantages: Seek time may be longer, suitable for occasions with a small number of requests.

Shortest Seek Time First (SSTF)

  • Give priority to requests closest to the current head.
  • Advantages: Reduce total seek time and improve efficiency.
  • Disadvantages: May cause requests far away to not be processed for a long time, resulting in "hunger" phenomenon.

Elevator Scheduling Algorithm (SCAN)

  • Similar to the operation mode of an elevator, the head moves back and forth in two directions to process requests along the way.
  • Advantages: Reduces the number of times the head moves back and forth, avoiding starvation.
  • Variants:
  • One-way scanning (LOOK): Scans only the last request in one direction, and does not process requests when returning.
  • Two-way scanning (C-SCAN): Starts a new round of scanning from the other end at the end of the scan, avoiding long waiting time in one direction.

Cyclic scanning (C-LOOK)

  • Optimized on the basis of one-way scanning, only scans the farthest request, and then restarts from the starting position to reduce invalid scanning.

Ideas for the implementation of virtual devices

Virtual device technology simulates multiple physical devices through software, making shared devices look like multiple exclusive devices to improve device utilization and system parallel processing capabilities.

Implementation of virtual devices

  • Implementation method: Abstract the device through the device management program (such as device driver) so that it appears as an independent logical device in the operating system.
  • Application scenarios: Printer sharing, disk partitioning, virtual memory, etc.

Spooling technology (SPOOLing)

SPOOLing (Simultaneous Peripheral Operations On-Line, Spooling) system is a technology that simulates exclusive devices to serve multiple users. Its core is to use the disk as an intermediate buffer to solve the problem of concurrent use of exclusive devices in a multi-user environment. The SPOOLing system is mainly composed of the following three parts:

Input Spooler

  • Function:
  • Responsible for reading the data of input devices (such as keyboards, terminals, etc.) from external devices and storing them in the input buffer of the disk.
  • In a multi-user system, each user's input request is redirected to the input area of ​​the disk through the pre-input program, avoiding the resource competition problem of directly accessing the actual input device.
  • Workflow:
  • After receiving the data request from the user, the pre-input program writes the data to the input buffer (called "well") of the disk.
  • Queue the input data and wait for the subsequent "well management" program to process.

Well Management Program

  • Function:
  • As the core part of the SPOOLing system, it is responsible for managing the data stored in the disk buffer (well).
  • Handle the organization, sorting and scheduling of input data, and decide which data should be passed to the processing program and when to execute.
  • Workflow:
  • Extract the data in the input buffer from the well according to the priority or arrival order.
  • Schedule and allocate data processing tasks, and pass the user input data to the corresponding processing program for execution.
  • Handle the processed output data to the "spooled output" program for processing.

Output Spooler

  • Function:
  • Responsible for temporarily storing the output data generated by the processing program in the output buffer of the disk, and transferring these data to the actual output device (such as printer, display, etc.) when the device is idle.
  • The buffered output program can effectively reduce the user's waiting time and improve the utilization of the device.
  • Workflow:
  • Write the output results of the user processing program to the output buffer of the disk.
  • Determine when to transfer the data from the buffer to the actual device according to the status of the output device (such as idle or busy).
  • Send the output data to the device in sequence to complete the output operation.

The workflow of the SPOOLing system

  1. Pre-input stage: The user's input request is stored in the input buffer of the disk through the "pre-input" program.
  2. Well management stage: The system takes out the request from the input buffer for processing according to the scheduling strategy, and puts the result into the output buffer after completion.
  3. Buffered output stage: When the output device is idle, the "buffered output" program outputs the data in the buffer to the actual device in sequence.

Advantages of the SPOOLing system

  • Device sharing: Multiple users can use exclusive devices (such as printers) at the same time to improve device utilization.
  • Parallel processing: Using the disk as an intermediary, input and output requests can be processed in parallel, reducing device waiting time.
  • Reduced blocking: Users can continue working without waiting for the device to complete the current task, improving the system response speed.

Application scenarios

  • Print service: In a printer sharing environment, the user's print request is first stored in the disk buffer, and then uniformly scheduled by the SPOOLing system and sent to the printer one by one for output.
  • Input/output device management: Applicable to scenarios where the speed mismatch between input/output devices and CPU needs to be alleviated, improving the overall throughput of the system.

Summary

  • Disk management achieves efficient use of disks through structured organization and efficient space management strategies.
  • Disk scheduling algorithm reduces disk seek time and improves system performance through different scheduling strategies.
  • Virtual devices and SPOOLing technology enable exclusive devices to be used concurrently by multiple processes, improving the resource utilization and processing efficiency of the system.