Virtual Memory, Disk Scheduling and File System

• 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
• Given a 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, the total arm movement using FCFS is 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
• Given the same disk drive and queue as in FCFS, the total arm movement using SSTF is 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
• Given the same disk drive and queue as in FCFS, the total arm movement using SCAN is 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
• Given the same disk drive and queue as in FCFS, the total arm movement using C-SCAN is 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
• Given the same disk drive and queue as in FCFS, the total arm movement using LOOK is 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
• Given the same disk drive and queue as in FCFS, the total arm movement using C-LOOK is 140 cylinders
• Virtual memory


  A technique that allows the execution of processes that are not completely in memory
• Virtual memory is implemented through paging and segmentation
• Page


  A fixed-size contiguous block (consecutive or next to each other) of memory, typically 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 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
• 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


  • 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)
• Given the CPU generates the address for a, find its equivalent in the RAM
• Given the CPU generates the address for d, find its equivalent in the RAM using the Page Table
• File System


  A method used by computers and the OS to organize and store data on storage devices such as hard disk drives, solid-state drives, USB drives, and optical discs
• Types of File Systems

  • FAT (File Allocation Table)
  • Extensible FAT (exFAT)
  • Fourth Extended File System (EXT4)
  • NTFS (New Technology File System)
  • Resilient File System (ReFS)
  • APFS (Apple File System)
• FAT (File Allocation Table)


  A file system developed for hard drives by Microsoft, with 3 variants: FAT12, FAT16, FAT32

  
• NTFS (New Technology File System)


  A proprietary file system developed by Microsoft, offering features such as support for large file sizes, file compression, encryption, file and folder permissions, and journaling for improved reliability
• Resilient File System (ReFS)

  Microsoft's newest file system, designed to maximize data availability, scale efficiently to large data sets across diverse workloads, and provide data integrity with resiliency to corruption
• APFS (Apple File System)


  iOS uses the proprietary APFS, optimized for flash storage with encryption, space sharing, and enhanced performance