Understanding Deadlock, Virtual Memory, and Disk Management

Posted on Feb 25, 2025 in Computers

Deadlock Characterization

  • Mutual Exclusion: Only one process at a time can use a resource.
  • Hold and Wait: A process holding at least one resource is waiting to acquire additional resources held by other processes.
  • No Preemption: A resource can be released only voluntarily by the process holding it, after that process has completed its task.
  • Circular Wait: There exists a set {P0, P1, …, Pn} of waiting processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2.

Deadlock Prevention

  • Mutual Exclusion: Not required for sharable resources (e.g., read-only files); must hold for non-sharable resources.
  • Hold and Wait: Must guarantee that whenever a process requests a resource, it does not hold any other resources.

Virtual Memory

Separation of user logical memory from physical memory:

  1. Only part of the program needs to be in memory for execution.
  2. Logical address space can therefore be much larger than physical address space.
  3. Allows address spaces to be shared by several processes.
  4. Allows for more efficient process creation.
  5. More programs running concurrently.
  6. Less I/O needed to load or swap processes.

Page Faults

  1. Operating system looks at another table to decide:
    • Invalid reference Þ abort
    • Just not in memory
  2. Find free frame.
  3. Swap page into frame via scheduled disk operation.
  4. Reset tables to indicate page now in memory. Set validation bit = v.
  5. Restart the instruction that caused the page fault.

Page Replacement

What Happens if There is no Free Frame:

  • Used up by process pages
  • Also in demand from the kernel, I/O buffers, etc.
  • How much to allocate to each?

Page replacement – find some page in memory, but not really in use, page it out.

  • Algorithm – terminate? swap out? replace the page?
  • Performance – want an algorithm which will result in minimum number of page faults.
  • Same page may be brought into memory several times.

Basic Page Replacement

  1. Find the location of the desired page on disk.
  2. Find a free frame:
    • If there is a free frame, use it
    • If there is no free frame, use a page replacement algorithm to select a victim frame
    • Write victim frame to disk if dirty.
  3. Bring the desired page into the (newly) free frame; update the page and frame tables.
  4. Continue the process by restarting the instruction that caused the trap.

Disk Scheduling

  1. The operating system is responsible for using hardware efficiently — for the disk drives, this means having a fast access time and disk bandwidth. Minimize seek time. Seek time » seek distance.
  2. There are many sources of disk I/O request
    • OS
    • System processes
    • Users processes
  3. I/O request includes input or output mode, disk address, memory address, number of sectors to transfer.
  4. OS maintains queue of requests, per disk or device.
  5. Idle disk can immediately work on I/O request, busy disk means work must queue.
  6. Optimization algorithms only make sense when a queue exists.

Disk Management

  1. Low-level formatting, or physical formatting — Dividing a disk into sectors that the disk controller can read and write.
  2. Each sector can hold header information, plus data, plus error correction code (ECC).
  3. Usually 512 bytes of data but can be selectable.
  4. To use a disk to hold files, the operating system still needs to record its own data structures on the disk.
  5. Partition the disk into one or more groups of cylinders, each treated as a logical disk.
  6. Logical formatting or “making a file system”.
  7. To increase efficiency most file systems group blocks into clusters
    • Disk I/O done in blocks
    • File I/O done in clusters

Stable-Storage Implementation

Write-ahead log scheme requires stable storage.

  1. Stable storage means data is never lost.
  2. Disk write has 1 of 3 outcomes:
    • Successful completion – The data were written correctly on disk
    • Partial failure – A failure occurred in the midst of transfer, so only some of the sectors were written with the new data, and the sector being written during the failure may have been corrupted
    • Total failure – The failure occurred before the disk write started, so the previous data values on the disk remain intact.