Operating Systems: Processes, Scheduling, Deadlocks, and Memory Management

Windows Operating System Kernel Objects

In the Windows operating system architecture, kernel objects represent various system resources that provide a unified way for applications and the system to interact with hardware and software entities. Identifying valid subsets of these objects is crucial for understanding system internals. Valid Windows kernel objects include events, mutexes, files, semaphores, profiles, timers, threads, and processes. It is important to distinguish these from other system mechanisms; for example, while interrupts are vital for hardware-software communication, they are not classified as kernel objects in the same manner as a process or a thread.

CPU Scheduling Principles and Metrics

Process and thread scheduling are governed by various algorithms and performance metrics that determine how resources are allocated to active tasks. These principles include:

• Turnaround Time (Cycle Time): This refers to the total time spent from the submission of a process to its completion. It is the sum of the time spent waiting to get into memory, waiting in the ready queue, executing on the CPU, and doing I/O.
• Optimal Scheduling (SJF): The Shortest Job First ($SJF$) algorithm is considered optimal for minimizing the average waiting time for a specific set of processes. Because it prioritizes the process with the smallest CPU burst, it effectively moves shorter tasks through the system faster, reducing the overall wait time accumulation.
• Throughput: This metric defines system efficiency as the number of processes that are completed per unit of time (e.g., processes per second).
• FCFS and the Convoy Effect: The First-Come, First-Served ($FCFS$) algorithm, despite its simplicity, is susceptible to the "convoy effect." This occurs when a single CPU-heavy process blocks a long line of shorter processes, leading to significant delays and poor CPU utilization.

Deadlock Analysis and the Banker's Algorithm

To manage resource allocation and prevent deadlocks, systems must evaluate whether they are in a "safe state." Consider a system with three types of resources, $R1$, $R2$, and $R3$, and three processes, $P1$, $P2$, and $P3$. The current status of the system is defined by the following parameters:

Maximum Demand:

• $P1: [1, 2, 3]$
• $P2: [5, 4, 3]$
• $P3: [3, 2, 4]$

Current Allocation:

• $P1: [0, 1, 2]$
• $P2: [2, 3, 2]$
• $P3: [3, 2, 2]$

Free Resources (Available):

• $[1, 1, 1]$

System State Analysis:

1. Current Safety: The system is currently in a safe state because there is an execution sequence ($P1 \rightarrow P3 \rightarrow P2$) that allows all processes to finish. $P1$ needs $[1, 1, 1]$, which is exactly what is available. Once $P1$ releases its resources, the available pool grows, allowing the others to complete.
2. Resource Requests: If search process $P3$ requested additional resources of $[0, 0, 1]$ at this moment, the system would transition into an unsafe state. Granting this would leave zero units of $R3$ available ($1 - 1 = 0$), while $P1$ still needs at least one unit of $R3$ to finish.
3. Alternative Requests: Conversely, if process $P1$ were to request and receive $[1, 1, 1]$, the system would still be able to find a safe sequence because $P1$ would finish immediately and release all its resources back into the pool.

Synchronization Mechanisms and Semaphores

Synchronizing access to shared resources is performed using semaphores, which can be implemented using "active waiting" (busy-wait). The correct operations for a semaphore $s$ in an active waiting environment are defined as:

• Wait (czekaj):$\text{while } (s == 0) \text{ do nothing; } s--$     The process continuously checks the value of $s$. If $s$ is greater than zero, it decrements the value and proceeds. If $s$ is zero, it spins in a loop.
• Signal (sygnalizuj):$s++$     This operation increments the semaphore value, potentially allowing a waiting process to exit its loop.

Important considerations for synchronization include:

• Monitors: These can be used to synchronize access to critical sections within a programmatic structure.
• Semafor Utility: Semaphores are perfectly suited for determining the execution order in a group of concurrent processes.
• Active Waiting Efficiency: A primary advantage of active waiting is that it avoids the computational overhead of switching the processor into a privileged (system) mode to block and unblock threads.

Advanced CPU Scheduling Case Study: SJF1 and SJF2

Consider four processes with the following characteristics:

• $P1$: Arrival $0$, Burst $6$
• $P2$: Arrival $1$, Burst $4$
• $P3$: Arrival $3$, Burst $3$
• $P4$: Arrival $5$, Burst $2$

Calculating metrics for SJF (Shortest Job First) in different modes:

Preemptive SJF (SJF2 / SRTF):

1. At time $0$, $P1$ starts.
2. At time $1$, $P2$ (burst 4) arrives. Since its remaining time is shorter than $P1$'s remaining $5$, it preempts $P1$.
3. At time $3$, $P3$ (burst 3) arrives. $P2$ has $2$ remaining. $P2$ continues.
4. At time $5$, $P2$ finishes. $P4$ (burst 2) arrives. Among the ready processes ($P1$: 5, $P3$: 3, $P4$: 2), $P4$ is the shortest.
5. At time $7$, $P4$ finishes. $P3$ is next.
6. At time $10$, $P3$ finishes. $P1$ finishes the remaining $5$.
7. At time $15$, $P1$ completes.

Calculated values for SJF2:

• P4 Turnaround Time: $7 - 5 = 2$.
• P1 Waiting Time: P1 ran from $0-1$, then waited from $1$ until $10$. Total waiting time: $10 - 1 = 9$.

Deadlock Conditions and Resource Allocation Graphs

A deadlock in a system occurs only if specific conditions are met simultaneously. A key condition is the existence of non-preemptible resources. Other foundational knowledge includes:

• Resource Allocation Graphs (RAG): The presence of a cycle in the RAG is a necessary condition for deadlock, but it does not guarantee a deadlock exists unless there is only one instance of each resource type.
• RAG Edges: Request edges are directed from the process node to the resource type node, while assignment edges are directed from the resource type node to the process node.
• Safe States: A system state is safe if there exists a sequence of processes such that for every process, the resources it can still request can be satisfied by the currently available resources plus the resources held by all processes that preceded it in the sequence.

Roles and Architecture of Operating Systems

The operating system (OS) serves multiple fundamental roles:

1. Resource Manager: The OS acts as a manager that distributes resources to users, controls access, and prevents chaos or conflicts between competing programs and users.
2. Extended Machine (Virtual Machine): The OS provides an abstraction layer that presents the user with an "extended machine" or virtual machine that is significantly easier to program and interact with than the raw hardware.
3. Process Control: The OS maintains a Process Control Block (PCB) for every process. The PCB includes process state information, program counters, and memory table information (like page or segment tables). It notably does not include the actual interrupt handling procedures or a list of system function addresses, as these are part of the kernel infrastructure.

Memory Management: Paging and Page Replacement

Paging is a memory management scheme that eliminates the need for contiguous allocation of physical memory.

Addressing in Paging:

• Logical Address: Composed of a Page Number and an Offset (displacement) within that page.
• Physical Address: Composed of a Frame Number and an Offset within that frame.

Page Replacement Algorithms:

• Optimal Algorithm: Replaces the page that will not be used for the longest period of time in the future. This provides the lowest possible page-fault rate.
• LRU (Least Recently Used): Replaces the page that has not been used for the longest time. It is categorized as a "stack algorithm."
• FIFO (First-In, First-Out): Replaces the oldest page. This algorithm is susceptible to Belady's Anomaly, where increasing the number of available page frames results in an increase in the number of page faults.
• Anomalies: While FIFO is burdened by Belady's Anomaly, the LRU algorithm is not.

File System Structures: The I-node

In many modern file systems, the i-node (index node) is a data structure used to represent a file system object, such as a file or a directory. Each i-node stores essential metadata and information about the file, such as ownership, permissions, and the physical location of the file's data blocks on the storage device.