Operating Systems - Input/Output and Deadlocks

Input/Output Units

• Operating systems manage processes, address spaces, files, and I/O devices.
• The OS issues commands, catches interrupts, and handles errors for I/O devices.
• The OS provides a simple interface between devices and the system.

I/O Device Categories

• Block devices: Store information in fixed-size blocks with addresses.
  • Block sizes range from 512 bytes to 32,768 bytes.
  • Examples: Hard disks, CD-ROMs, USB sticks.
• Character devices: Deliver or accept streams of characters without block structure.
  • They are not addressable and lack seek operations.
  • Examples: Printers, mice, keyboards.

General Structure of I/O Devices

• I/O units have mechanical and electronic components.
• The electronic component is the device controller or adapter.

Hard Disks

• Hard disks consist of aluminum or glass platters.
• Each platter surface is divided into tracks; tracks are divided into sectors.
• Space in each sector is used for formatting.
• Heads read/write data from disks.

Disk Arm Scheduling

• Disk arm scheduling minimizes disk I/O time.
• Time is determined by:
  • Seek time: Time to move the arm to the track.
  • Rotational delay: Time for the sector to rotate under the head.
  • Block transfer time.
• When multiple I/O requests arrive, scheduling aims to:
  • Minimize average I/O time.
  • Ensure fairness.
  • Avoid starvation.

First-Come, First-Served (FCFS)

• FCFS handles requests in arrival order.
• Example:
  • Requests: 10, 25, 4, 18, 75, 9
  • Current head: 12
  • Total head movement: $|12-10| + |25-10| + |25-4| + |18-4| + |75-18| + |75-9| = 2 + 15 + 21 + 14 + 57 + 66 = 175$

Shortest Seek-Time First (SST)

• SST chooses the nearest track with a request.
• Goal: minimize seek time.
• Example:
  • Requests: 10, 25, 4, 18, 75, 9
  • Current head: 12
  • Nearest track to 12 is 10 (2 tracks movement)
  • Nearest track to 10 is 9 (1 track movement)
  • Nearest track to 9 is 4 (5 tracks movement)
  • Nearest track to 4 is 18 (14 tracks movement)
  • Nearest track to 18 is 25 (7 tracks movement)
  • Nearest track to 25 is 75 (50 tracks movement)
  • Total: $2 + 1 + 5 + 14 + 7 + 50 = 79$

Drawback of SST

• SST can suffer from starvation if continuous requests arrive for tracks near the current head position.
• Example: If after going to track 18, a request for track 8 arrives, it takes priority over 75. If more requests close to track 18 arrive, the request from track 75 will not be processed.

Elevator Algorithm

• Head moves from the first track to the last, processing requests along the way.
• Processes requests in the direction of head movement to avoid starvation.
• Example:
  • Requests: 10, 25, 4, 18, 75, 9
  • Current head: 1
  • Movement: 1 to 4, then 9, then 10, then 18, then 25, and finally 75.
  • Total tracks: 74

Deadlocks

• I/O devices are computer resources, and the OS optimizes their use.
• Resource utilization should be error-free; bad allocation can cause deadlocks.
• Processes may need exclusive access to resources.
• Deadlock occurs when a process holds a resource needed by another process, and waits for a resource held by that process, blocking both.
• Example: Two processes need bow and arrows exclusively; one holds the bow, waiting for arrows held by the other process holding arrows and waiting for bow.
• Example: One bank agent holds account A and waits for account B; the other agent holds account B and waits for account A.

Conditions for Deadlock

• Four conditions are necessary for deadlock:
  • Exclusive resource access: No simultaneous sharing.
  • Incremental allocation: Processes don't request all resources together (hold and wait).
  • Circular waiting for resources.
  • No resource preemption.
• If any of these conditions is missing, deadlock cannot occur.

Preventing Deadlocks

• The resource manager must prevent circular waiting.
• Before allocation, the manager should ensure that circular waiting will not be created.
• The manager should have the list of resources that each process will request.
• Allocation of exclusive access should avoid circular hold/wait conditions.

Resources and Deadlocks

• Deadlocks require exclusive resource use and circular waiting.
• Resources can be shared or used exclusively.

Resources

• A resource is anything required by a process.
• Operating systems function as resource managers.
• Resources can be sharable, serially reusable, and consumable.

Resource Management

• Resource management includes protection, economy, convenience, and fairness.
• Management should avoid deadlocks.

Resource Characteristics

• A resource’s characteristics determine how it’s managed.
• Main characteristics:
  • Resource durability: reusable vs. consumable.
  • Resource multiplicity: static vs. dynamic.
  • Resource sharing: sharable vs. sequentially reusable.

Sequentially Reusable Resources

• Can be used by at most one process at a time.
• Output devices tend to be serially reusable.
• Example: Printers (cannot interrupt a print task and switch to another).

Sharable Resources

• Can be used by multiple processes at the same time (by switching).
• Input devices tend to be sharable.
• Example: Multiple processes can read from a hard disk.
• CPU is sharable only if processes are preemptive.

Consumable Resources

• Disappear after being used.
• Network packets and IPC messages are consumable.

Static and Dynamic Resources

• Static resources have a fixed or slowly changing number of units (disks, CPUs). Reusable resources tend to be static.
• Dynamic resources have a varying number of units. Consumable resources are necessarily dynamic; they must be created and consumed.

Conclusion

• Operating Systems as resource managers optimize resource usage.
• Input/Output devices are important resources to be used optimally.
• Resource allocation should avoid deadlocks.
• Not all resource types may cause deadlocks.