Computer Operating System Review Notes

I. Process Scheduling Algorithms

1. First-Come, First-Served (FCFS) Algorithm
   • Turnaround Time: Completion Time - Arrival Time
   • Average Turnaround Time: Sum of all processes’ turnaround times / Number of processes
   • Weighted Turnaround Time: Turnaround Time / Service Time
   • Average Weighted Turnaround Time: Sum of all processes’ weighted turnaround times / Number of processes
2. Shortest Job First (SJF) Algorithm
   • Selection Rule: Select the job (process) that has already arrived and has the shortest service time to execute
   • Turnaround Time: Completion Time - Arrival Time
   • Average Turnaround Time: Sum of all processes’ turnaround times / Number of processes
   • Weighted Turnaround Time: Turnaround Time / Service Time
   • Average Weighted Turnaround Time: Sum of all processes’ weighted turnaround times / Number of processes
3. Highest Response Ratio Next (HRRN) Algorithm
   • Waiting Time: Current system start time - Process arrival time
   • Response Ratio: (Waiting Time + Required Service Time) / Required Service Time
   • Selection Rule: Each time, select the job (process) with the highest response ratio to execute
   • Turnaround Time: Completion Time - Arrival Time
   • Average Turnaround Time: Sum of all processes’ turnaround times / Number of processes
   • Weighted Turnaround Time: Turnaround Time / Service Time
   • Average Weighted Turnaround Time: Sum of all processes’ weighted turnaround times / Number of processes
4. Round Robin (RR) Algorithm
   • Turnaround Time: Completion Time - Arrival Time
   • Average Turnaround Time: Sum of all processes’ turnaround times / Number of processes
   • Weighted Turnaround Time: Turnaround Time / Service Time
   • Average Weighted Turnaround Time: Sum of all processes’ weighted turnaround times / Number of processes
   • Execution Rule: Each process is allocated a time slice and the processes execute in turn; when the time slice is exhausted, regardless of whether the process has completed, the CPU switches to the next process

II. Page Replacement Algorithms

1. Optimal (OPT) Algorithm
   • It predicts the future usage of pages in advance, thereby selecting the page that will not be used for the longest time in the future to be replaced.
   • Number of Page Faults: Count the number of times the required page is not in memory and must be loaded from external storage
   • Page Fault Rate: Number of page faults / Length of the page reference sequence
   • Replacement Rule: Select the page that will not be accessed for the longest time in the future to be replaced (difficult to implement in practice; used for theoretical comparison)
2. First-In, First-Out (FIFO) Algorithm
   • The page that enters memory first is the first to be replaced.
   • Number of Page Faults: Count the number of times the required page is not in memory and must be loaded from external storage
   • Page Fault Rate: Number of page faults / Length of the page reference sequence
   • Replacement Rule: Select the page that entered memory first to be replaced
3. Least Recently Used (LRU) Algorithm
   • Eliminates the page that has been least recently used.
   • Number of Page Faults: Count the number of times the required page is not in memory and must be loaded from external storage
   • Page Fault Rate: Number of page faults / Length of the page reference sequence
   • Replacement Rule: Select the page that has not been used for the longest time to be replaced

III. Disk Scheduling Algorithms

1. First-Come, First-Served (FCFS) Algorithm
   • Seek Time: The time required for the head to move to a specified track, calculated based on the number of tracks the head moves
   • Total Seek Time: Sum of all seek times
   • Average Seek Length: Total seek length / Number of disk requests
   • Processing Rule: Process disk requests in the order they arrive
2. Shortest Seek Time First (SSTF) Algorithm
   • Seek Time: The time required for the head to move to a specified track, calculated based on the number of tracks the head moves
   • Total Seek Time: Sum of all seek times
   • Average Seek Length: Total seek length / Number of disk requests
   • Processing Rule: Select the track request closest to the current head position for processing
3. Scan (SCAN) Algorithm (Elevator Algorithm)
   • Seek Time: The time required for the head to move to a specified track, calculated based on the number of tracks the head moves
   • Total Seek Time: Sum of all seek times
   • Average Seek Length: Total seek length / Number of disk requests
   • Processing Rule: The head moves in one direction, processing disk requests along the way until it reaches one end, then changes direction and continues processing
4. Circular Scan (CSCAN) Algorithm
   • Seek Time: The time required for the head to move to a specified track, calculated based on the number of tracks the head moves
   • Total Seek Time: Sum of all seek times
   • Average Seek Length: Total seek length / Number of disk requests
   • Processing Rule: The head moves in one direction, processing disk requests along the way; upon reaching one end, it immediately returns to the starting end, and then continues processing in the same direction

IV. Cache-Related Topics

1. Cache Hit Rate Calculation: Number of cache hits / Total number of accesses
2. Average Access Time: Hit rate × Cache access time + (1 - Hit rate) × Main memory access time

V. Virtual Memory Topics (Using Paging as an Example)

1. Maximum Number of Pages for a User Job: Virtual address space size / Page size
2. Number of Blocks into Which Main Memory Is Divided: Main memory capacity / Page size
3. Page Number: INT (Logical address / Page size)
4. In-Page Address: Logical address MOD Page size
5. Physical Address: Block number × Page size + In-Page Address
6. Page offset: Logical address MOD Page size