Operating Systems: Memory Management and CPU Scheduling Comprehensive Study Guide

Introduction to Operating Systems (OS)

• Definition of an Operating System:

  • An operating system is a specific category of software that serves two primary roles:

    • User Interface: It provides the environment for humans to interact with computer hardware and allows the execution of application software.

    • Resource Management: It acts as a manager for the computer's physical and logical resources, including Memory, the Central Processing Unit (CPU), and Input/Output (I/O) devices.

• Fundamentals of Resource Management:

  • Memory Management: The process of maintaining multiple programs in the computer's memory simultaneously while they await CPU time. This involves tracking where programs are located and ensuring they have sufficient space.

  • CPU Scheduling: The decision-making process used to determine which specific process currently in memory will be executed by the CPU at any given moment.

Memory Management Techniques and Partitioning

• Memory Partitions:

  • Computer memory is often divided into sections called partitions (e.g., Partition A, Partition B, Partition C, etc.). These partitions house individual programs (e.g., Program 1, Program 2, Program 3).

• Partition Selection Algorithms:

  • First Fit: The OS allocates a process to the very first partition in the memory list that is large enough to contain it.

  • Best Fit: The OS searches the entire list of partitions and allocates the process to the smallest available partition that is still large enough to hold it. This aims to minimize wasted space within the partition.

  • Worst Fit: The OS allocates the process to the largest available partition in the memory. This logic is sometimes used to leave behind the largest possible remaining fragments of memory.

• Fixed Partition Comparison Exercise 1:

  • Given Partitions: $A = 500\,\text{MB}$, $B = 400\,\text{MB}$, $C = 700\,\text{MB}$, $D = 450\,\text{MB}$.

  • Program Load Order: $350\,\text{MB}$, $450\,\text{MB}$, $425\,\text{MB}$, $500\,\text{MB}$.

  • Observed assignment results:

    • First Fit Strategy: A, C, D, E.

    • Best Fit Strategy: B, D, A, E.

    • Worst Fit Strategy: C, E, A, NONE.

• Fixed Partition Comparison Exercise 2:

  • Available Partitions:

    1. $A: 1000\,\text{MB}$

    2. $B: 700\,\text{MB}$

    3. $C: 750\,\text{MB}$

    4. $D: 1500\,\text{MB}$

    5. $E: 300\,\text{MB}$

    6. $F: 350\,\text{MB}$

  • Program Request Order: $1000\,\text{MB}$, $25\,\text{MB}$, $780\,\text{MB}$, $1600\,\text{MB}$, $325\,\text{MB}$.

  • Results by Algorithm:

    • First-fit: $A, B, D, \text{NONE}, C$

    • Best-fit: $A, E, D, \text{NONE}, F$

    • Worst-fit: $D, A, \text{NONE}, \text{NONE}, C$

CPU Scheduling Strategies

• Core Objective: To determine which process moves from the Ready State (waiting for CPU) to the Running State (currently executing).

• Common Scheduling Algorithms:

  • First-Come, First-Served (FCFS): Processes are moved to the CPU strictly in the order they arrive in the ready state.

  • Shortest Job Next (SJN): The OS looks at all processes in the ready state and selects the one with the shortest estimated running time to enter the running state next.

  • Round Robin (RR): Each process is permitted to run for a specific duration called a Time Slice. If the process is not finished when the slice expires, it is moved back to the ready state to wait for its next turn.

Scheduling Examples and Turnaround Time Calculations

• Turnaround Time Definition: The total time taken from the arrival of a process to its completion.

• Case Study Data:

  • Processes $P1$ through $P5$ arrive at the same time with the following estimated run times:

    • $P1: 140$

    • $P2: 75$

    • $P3: 320$

    • $P4: 280$

    • $P5: 125$

• Algorithm 1: First-Come, First-Served (FCFS)

  • Arrival/Execution Order: $P1, P2, P3, P4, P5$

  • Completion Times: $140, 215, 535, 815, 940$

  • Average Turnaround Time Calculation:         $\frac{140 + 215 + 535 + 815 + 940}{5} = 529$

• Algorithm 2: Shortest Job Next (SJN)

  • Execution Order (based on length): $P2(75), P5(125), P1(140), P4(280), P3(320)$

  • Completion Times: $75, 200, 340, 620, 940$

  • Average Turnaround Time Calculation:         $\frac{75 + 200 + 340 + 620 + 940}{5} = 435$

• Algorithm 3: Round Robin (Time Slice = 100)

  • Detailed Timeline:

    1. $P1$ runs $0-100$

    2. $P2$ runs $100-175$ (Finished at $175$)

    3. $P3$ runs $175-275$

    4. $P4$ runs $275-375$

    5. $P5$ runs $375-475$

    6. $P1$ runs $475-515$ (Finished at $515$)

    7. $P3$ runs $515-615$

    8. $P4$ runs $615-715$

    9. $P5$ runs $715-740$ (Finished at $740$)

    10. $P3$ runs $740-840$

    11. $P4$ runs $840-920$ (Finished at $920$)

    12. $P3$ runs $920-940$ (Finished at $940$)

  • Average Turnaround Time Calculation:         $\frac{515 + 175 + 940 + 920 + 740}{5} = 658$

• Algorithm 4: Round Robin Exercise (Time Slice = 50)

  • Using the same processes ($P1-P5$):

  • Completion times identified: $P1=515, P2=325, P3=940, P4=920, P5=640$

  • Average Turnaround Time Calculation:         $\frac{515 + 325 + 940 + 920 + 640}{5} = 668$

Works Cited

• Dale, Neil and John Lewis. Computer Science Illuminated. 7th ed., Jones & Bartlett Learning, 2019.