Operating Systems: Processes, Memory, Scheduling & More
Operating System Services
Operating Systems (OS) provide various services to ensure effective and efficient use of system resources. Key services include:
1. Process Management
The OS handles the creation, scheduling, and termination of processes. It manages process synchronization, inter-process communication, and deadlock handling, ensuring that multiple processes can execute concurrently without conflict.
2. Memory Management
The OS manages the system’s memory, including RAM. It keeps track of each byte in a computer’s memory, determining how much memory each process requires and allocating/deallocating memory space as needed by various programs.
Types of Memory
- Physical Memory: Physical memory refers to the actual RAM (Random Access Memory) installed in a computer system. It is the hardware that stores data and machine code currently being used by the computer. Physical memory is limited by the size of the RAM modules installed on the system.
- Virtual Memory: Virtual memory is a memory management capability of an OS that allows a computer to compensate for physical memory shortages by temporarily transferring data from RAM to disk storage. It creates an illusion of a large main memory by using secondary storage (like a hard disk) for additional space. Virtual memory enables a system to run larger applications or multiple applications simultaneously even if physical memory is limited.
Memory Management Techniques
- Paging: Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory. The process’s logical memory is divided into fixed-sized blocks called pages, while physical memory is divided into blocks of the same size called frames. When a program is executed, its pages are loaded into any available memory frames. This allows for efficient use of memory and helps in avoiding fragmentation.
- Swapping: Swapping is a process management technique where an entire process is temporarily moved out of the main memory to a backing store (usually a hard disk) and later brought back into memory for continued execution. This allows the system to manage multiple processes with limited physical memory, as it can “swap” inactive processes out of memory to make room for active ones.
3. File System Management
The OS manages files on different storage devices, ensuring that files are stored and retrieved securely and efficiently. It provides file creation, deletion, reading, writing, and manipulation functionalities.
4. Security and Protection
The OS ensures that unauthorized users do not access the system’s resources. It also protects against malicious software and provides user authentication, maintaining the integrity of the system.
5. Communication
The OS facilitates inter-process communication (IPC) between processes running on the same or different systems. It supports message passing, shared memory, and socket communication for networked systems.
Types of Inter-Process Communication
- Direct Communication: In direct communication, processes must explicitly name each other to send or receive messages. The sending process specifies the receiving process’s name, and the receiving process specifies the sending process’s name. This type of communication is straightforward but less flexible, as it requires processes to know each other’s identities in advance. For example:
send(P, message)– Process A sends a message to Process P.receive(A, message)– Process P receives a message from Process A.
- Indirect Communication: In indirect communication, processes use mailboxes (or ports) as intermediaries to send or receive messages. Processes do not need to know each other’s identities; instead, they send messages to a mailbox, and the receiving process retrieves messages from the mailbox. This method decouples processes and provides more flexibility. For example:
send(mailbox1, message)– Process A sends a message to mailbox1.receive(mailbox1, message)– Process B receives a message from mailbox1.
6. Error Detection
The OS constantly monitors the system for errors, such as hardware failures, software bugs, and security breaches. It provides mechanisms for error detection, reporting, and recovery to maintain system integrity and reliability.
7. User Interface
The OS provides a user interface, such as Command-Line Interface (CLI) or Graphical User Interface (GUI), to allow users to interact with the system.
Process Synchronization
Critical Section Problem
The critical section problem arises when multiple processes need to access shared resources. To prevent race conditions and ensure data consistency, processes must synchronize their access to the critical section (the code that accesses shared resources).
Conditions for a Solution to the Critical Section Problem
- Mutual Exclusion: Only one process can execute in the critical section at a time. If a process is executing in its critical section, no other process should be allowed to enter its critical section.
- Progress: If no process is in the critical section and some processes wish to enter it, then the selection of the process that will enter the critical section next cannot be postponed indefinitely. The decision should involve only those processes that are not in their remainder sections.
- Bounded Waiting: There must be a limit on the number of times other processes can enter their critical sections after a process has requested to enter its critical section and before that request is granted. This ensures that no process waits indefinitely to enter the critical section.
Producer-Consumer Problem
The producer-consumer problem is a classic synchronization problem where two processes, the producer and the consumer, share a common, fixed-size buffer. The producer generates data and places it in the buffer, while the consumer removes data from the buffer.
Solution Using Semaphores
Semaphores Used:
empty: Counts the number of empty slots in the buffer (initialized to buffer size).full: Counts the number of filled slots in the buffer (initialized to 0).mutex: Ensures mutual exclusion when accessing the buffer (binary semaphore initialized to 1).
Producer Process:
- The producer waits until there is an empty slot in the buffer (
wait(empty)), then waits for mutual exclusion (wait(mutex)) to add an item to the buffer. After adding, it signals the mutex (signal(mutex)) and increments the full semaphore (signal(full)).
Code:
wait(empty);
wait(mutex);
// Add item to buffer;
signal(mutex);
signal(full);
Consumer Process:
- The consumer waits until there is a full slot in the buffer (
wait(full)), then waits for mutual exclusion (wait(mutex)) to remove an item from the buffer. After removing, it signals the mutex (signal(mutex)) and increments the empty semaphore (signal(empty)).
Code:
wait(full);
wait(mutex);
// Remove item from buffer
signal(mutex);
signal(empty);
This solution ensures that the producer does not add to a full buffer and the consumer does not remove from an empty buffer, thereby synchronizing the operations.
CPU Scheduling
Scheduling refers to the process of deciding which process should be executed by the CPU at any given point in time. It is a fundamental concept in operating systems that ensures that CPU resources are utilized efficiently. The goal is to allocate CPU time to processes in a way that balances system performance, fairness, and resource utilization.
Types of Schedulers
1. Short-term Scheduler (CPU Scheduler)
- Function: Decides which of the ready, in-memory processes is to be executed by the CPU.
- Frequency: Executes very frequently (milliseconds) since a process may only execute for a few milliseconds.
- Decision Making: It selects from among the processes that are ready to execute and allocates the CPU to one of them.
- Speed: It must be fast and efficient because it makes decisions very often.
- Criteria: It uses criteria like priority, time-sharing, and shortest remaining time to decide which process to schedule next.
2. Medium-term Scheduler
- Function: Manages the degree of multiprogramming (the number of processes in memory).
- Frequency: Executes less frequently compared to the short-term scheduler.
- Decision Making: It may decide to temporarily remove a process from memory (swap out) to reduce the degree of multiprogramming and then bring it back (swap in) when memory is available.
- Use: It is used for implementing memory management techniques such as swapping and is important for managing the state of processes that are waiting for I/O operations.
3. Long-term Scheduler (Job Scheduler)
- Function: Decides which jobs or processes should be brought into the ready queue.
- Frequency: Executes much less frequently compared to short-term and medium-term schedulers.
- Decision Making: It determines which processes are to be admitted to the system for processing. Once admitted, they become ready processes and are sent to the short-term scheduler.
- Criteria: It controls the degree of multiprogramming and decides the mix of I/O-bound and CPU-bound processes.
- Purpose: It ensures a balanced load of processes, maintaining a mix that keeps the system running efficiently.
Mutual Exclusion Violation
Mutual Exclusion is a fundamental principle in concurrent programming, ensuring that multiple processes or threads do not simultaneously access shared resources, which can lead to inconsistent or erroneous states.
Consider two processes, P1 and P2, that need to access a shared resource protected by a semaphore S initialized to 1. The pseudocode for accessing the critical section would typically be:
Process P1:
wait(S); // Decrement semaphore
// Critical section
signal(S); // Increment semaphore
Process P2:
wait(S); // Decrement semaphore
// Critical section
signal(S); // Increment semaphore
Scenario where Mutual Exclusion is Violated:
- Suppose P1 executes the
wait(S)operation but is preempted by the OS just before decrementing the semaphore. - P2 now also executes the
wait(S)operation. Since the semaphore was not yet decremented by P1, P2 sees the semaphore value as 1 and decrements it to 0. - Now, both P1 and P2 believe they have exclusive access to the critical section and can enter it simultaneously, violating mutual exclusion.
This scenario shows that if the wait and signal operations are not executed atomically, multiple processes may enter the critical section at the same time, leading to race conditions and inconsistent states. Atomicity is crucial to ensure that mutual exclusion is maintained. The wait and signal operations must be executed as indivisible units to prevent other processes from interfering during their execution.
Process Control Block (PCB)
Process Control Block (PCB) is a data structure in the operating system that contains information about a specific process. It is essential for process management in a multitasking environment.
Contents of PCB
- Process ID (PID): A unique identifier assigned to each process.
- Process State: The current state of the process, such as new, ready, running, waiting, or terminated.
- Program Counter: The address of the next instruction to be executed for the process.
- CPU Registers: Contents of all the CPU registers that the process is using. This information is necessary for context switching.
- Memory Management Information: Information about memory allocation to the process, such as base and limit registers, page tables, or segment tables.
- Scheduling Information: Information used by the scheduler, such as process priority, scheduling queue pointers, and other scheduling parameters.
- Accounting Information: Information for accounting purposes, such as the amount of CPU time used, time limits, job or process numbers, and so on.
- I/O Status Information: Information about I/O devices allocated to the process, a list of open files, and so on.
- List of Open Files: A list of files opened by the process.
Usage of PCB
- The PCB is used by the operating system to keep track of all processes in the system.
- During context switching, the OS saves the current state of the running process in its PCB and loads the state of the new process from its PCB.
- The PCB allows the operating system to restore the process’s execution state, facilitating multitasking and process management.
Scheduling Algorithms and Calculations
Calculations:
- Turnaround Time (TAT):
TAT = Completion Time - Arrival Time - Waiting Time (WT):
WT = TAT - Burst Time
First-Come, First-Served (FCFS) Scheduling
Gantt Chart:
P1 | P2 | P3 | P4
- Timeline: 0 7 11 12 16
- Completion Times: P1 = 7, P2 = 11, P3 = 12, P4 = 16
- Turnaround Times: P1 = 7, P2 = 9, P3 = 8, P4 = 11
- Waiting Times: P1 = 0, P2 = 7, P3 = 7, P4 = 7
Shortest Job First (SJF) – Non-Preemptive
Gantt Chart:
P1 | P3 | P2 | P4
- Timeline: 0 7 8 12 16
- Completion Times: P1 = 7, P2 = 12, P3 = 8, P4 = 16
- Turnaround Times: P1 = 7, P2 = 10, P3 = 4, P4 = 11
- Waiting Times: P1 = 0, P2 = 6, P3 = 3, P4 = 7
Shortest Job First (SJF) – Preemptive
Gantt Chart:
P1 | P2 | P3 | P4
- Timeline: 0 7 10 11 16
- Completion Times: P1 = 7, P2 = 10, P3 = 11, P4 = 16
- Turnaround Times: P1 = 7, P2 = 8, P3 = 7, P4 = 11
- Waiting Times: P1 = 0, P2 = 6, P3 = 7, P4 = 7
Round Robin (RR) – Time Slice = 2
Gantt Chart:
P1 | P2 | P3 | P4 | P1 | P2 | P4 | P1
- Timeline: 0 2 4 6 8 10 12 16
- Completion Times: P1 = 16, P2 = 12, P3 = 6, P4 = 16
- Turnaround Times: P1 = 16, P2 = 10, P3 = 2, P4 = 11
- Waiting Times: P1 = 9, P2 = 6, P3 = 2, P4 = 7