CSC141

• Disk scheduling is an operation performed by operating systems to manage and schedule input/output (I/O) requests directed to the disk
• Disk scheduling


  • The goal is to minimize the seek time and maximize overall disk performance
• Access time = seek time + rotational latency
• Seek Time


  The time taken by the disk's read/write head to move to the desired track of the requested data
• Access Time


  Seek Time + Rotational Latency
• Rotational Latency


  The time it takes for the desired sector to rotate under the read/write head
• Data Transfer Time


  The actual time it takes to transfer the requested data between the disk and the RAM
• Disk scheduling algorithms


  • First Come, First Served (FCFS)
  • Shortest Seek Time First (SSTF)
  • SCAN (Elevator)
  • C-SCAN
  • LOOK
  • C-LOOK
• First Come, First Served (FCFS)


  1. Requests are handled in the order they arrive in a queue

  2. While fair, it might not be optimal if requests are scattered across the disk surface
• First Come, First Served (FCFS)


  • Disk drive with 200 cylinders, numbered 0 to 199, having a queue with I/O requests to blocks on cylinders at positions 90, 25, 150, 100, 175, and 10, and the disk head initially at cylinder 50
• Total Head/Arm Movement for FCFS = |50-90|+|90-25|+|25-150|+ |150-100|+ |100-175|+ |175-10| = 40+65+125+50+75+165 = 520 cylinders
• Shortest Seek Time First (SSTF)


  1. This algorithm prioritizes the request that requires the shortest seek time

  2. It minimizes seek time but might "starve" requests further away
• Shortest Seek Time First (SSTF)

  • Disk drive with 200 cylinders, numbered 0 to 199, having a queue with I/O requests to blocks on cylinders at positions 90, 25, 150, 100, 175, and 10, and the disk head initially at cylinder 50
• Total Head/Arm Movement for SSTF = |50-25|+|25-10|+|10-90|+ |90-100|+ |100-150|+ |150-175| = 25+15+50+80+10+25 = 205 cylinders
• SCAN (Elevator)


  1. The disk's read/write head moves in one direction across the disk, servicing requests as it encounters them

  2. Once it reaches the end of the disk, it reverses direction

  3. This algorithm balances seek times but may result in longer wait times for requests at the ends of the disk
• SCAN (Elevator)


  • Disk drive with 200 cylinders, numbered 0 to 199, having a queue with I/O requests to blocks on cylinders at positions 90, 25, 150, 100, 175, and 10, and the disk head initially at cylinder 50
• Total Head/Arm Movement for SCAN = |50-199|+|199-10| = 149+189 = 338 cylinders
• Circular SCAN (C-SCAN)


  1. Similar to SCAN, but the disk's read/write head only moves in one direction

  2. Once it reaches the end of the disk, it immediately returns to the beginning

  3. This algorithm reduces variance in service times compared to SCAN
• Circular SCAN (C-SCAN)


  • Disk drive with 200 cylinders, numbered 0 to 199, having a queue with I/O requests to blocks on cylinders at positions 90, 25, 150, 100, 175, and 10, and the disk head initially at cylinder 50

  
• Total Head/Arm Movement for C-SCAN = |50-199|+|0-25| = 149+25 = 174 cylinders
• LOOK


  1. Similar to SCAN, but it only scans until it encounters the last request in one direction before reversing

  2. This reduces unnecessary head movement compared to SCAN
• LOOK


  • Disk drive with 200 cylinders, numbered 0 to 199, having a queue with I/O requests to blocks on cylinders at positions 90, 25, 150, 100, 175, and 10, and the disk head initially at cylinder 50

  
• Total Head/Arm Movement for LOOK = |50-175|+|175-10| = 125+165 = 290 cylinders
• Circular LOOK (C-LOOK)


  1. Similar to C-SCAN, but it behaves like LOOK, scanning only until the last request in one direction before reversing

  2. This reduces variance in service times compared to C-SCAN
• Circular LOOK (C-LOOK)


  • Disk drive with 200 cylinders, numbered 0 to 199, having a queue with I/O requests to blocks on cylinders at positions 90, 25, 150, 100, 175, and 10, and the disk head initially at cylinder 50

  
• Total Head/Arm Movement for C-LOOK = |50-175|+|10-25| = 125+15 = 140 cylinders
• Virtual memory


  A technique that allows the execution of processes that are not completely in memory
• Computers have finite amount of Physical Memory (RAM), so memory can run out especially when running multiple processes at the same time
• Paging file/swap space


  A portion of the hard drive designated by the OS to serve as Virtual Memory

  
• When a program requires more memory than is available in the RAM, the OS uses a process called paging to transfer unused portions of the RAM to disk storage, freeing up space in RAM for other processes
• Page


  A fixed-size contiguous block (consecutive or next to each other) of memory, typically small, ranging from a few kilobytes to a few megabytes in size

  
• Paging


  A memory management technique that allows the physical location (known as physical address space) of a process to be non-contiguous
• Paging allows processes to be retrieved from the secondary storage into the main memory in the form of pages
• Paging file


  Swap space
• Virtual Memory


  When a program requires more memory than is available in the RAM, the OS uses a process called paging to transfer unused portions of the RAM to disk storage, freeing up space in RAM for other processes
• Virtual Memory implementation


  1. Paging

  2. Segmentation
• Paging


  • Allows the physical location (known as physical address space) of a process to be non-contiguous
  • Allows processes to be retrieved from the secondary storage into the main memory in the form of pages
• Virtual Memory Through Paging

  1. Divide RAM and Process: RAM and the process are divided into equal fixed-size blocks called frames and pages, respectively

  2. Load Process: Pages are loaded into RAM only when needed, and unloaded out when they are not needed

  3. Storage of Pages: Pages can be stored in any available frame in RAM, aiming for contiguous allocation when possible

  4. Address Translation and Lookup: The page table translates virtual addresses used by the program into physical RAM addresses. If the page is in the RAM, the page table provides the physical address. Otherwise, a page fault occurs

  5. Page Fault & Swapping: If a page fault happens, the OS fetches the needed page from disk (swap space) and potentially swaps out another page from RAM to make room
• Logical/Virtual Address


  Consists of two parts: the page number and the page offset. The page number servers as an index in the process's page table. The page offset indicates the distance between the memory location and the start of the page
• Physical Address


  Consists of two parts: the frame number and the frame offset (which is the same as the page offset)