Introduction to Operating Systems

OS Structure and Strategies

Definition: An operating system is the software that manages hardware resources and provides services for applications.
Core Components:
- Kernel: The central component that manages memory, processes, and hardware
- Device drivers: Interface between hardware and the OS
- File system: Organizes and manages data storage
- Shell/User interface: Allows users to interact with the system
Common OS Structures:
- Monolithic: All OS services operate in kernel space
  - Example: Traditional Unix, Linux kernel
  - Advantage: Efficient direct communication between components
  - Disadvantage: Poor isolation, bugs can crash entire system
- Microkernel: Minimal kernel with services in user space
  - Example: MINIX, QNX
  - Advantage: Better reliability and security through isolation
  - Disadvantage: Performance overhead from inter-process communication
- Layered: System divided into hierarchical layers
  - Example: THE operating system (historically)
  - Advantage: Well-defined interfaces between layers
  - Disadvantage: Rigid structure can limit performance
- Hybrid: Combines aspects of multiple approaches
  - Example: Windows NT kernel, macOS (XNU kernel)
  - Advantage: Balances performance and modularity
  - Disadvantage: Added complexity
Protection Rings: Hierarchical privilege levels
- Ring 0: Kernel mode (highest privilege)
- Ring 3: User mode (limited privileges)
- Example: x86 architecture supports rings 0-3, though most OSes only use rings 0 and 3

Process Concepts

Definition: A process is a program in execution, representing the dynamic state of a running program.
Process Components:
- Program code: The executable instructions
- Process Control Block (PCB): Data structure containing process details
  - Process ID, state, program counter, CPU registers
  - Memory limits, list of open files, scheduling information
- Stack: Contains temporary data (function parameters, return addresses, local variables)
- Heap: Dynamically allocated memory during runtime
- Data section: Global and static variables
Process States:
- New: Process is being created
- Ready: Process is waiting to be assigned to a processor
- Running: Instructions are being executed
- Blocked/Waiting: Process is waiting for some event (I/O completion, resource availability)
- Terminated: Process has finished execution
Example state transition: A process calculating large dataset (Running) → Needs to read from disk (Blocked) → Data available (Ready) → Gets CPU again (Running)
Process Creation Mechanisms:
- fork(): Creates child process (UNIX/Linux)
```
pid_t pid = fork();if (pid == 0) {    // Child process code} else if (pid > 0) {    // Parent process code} else {    // Error handling}
```
- exec(): Replaces current process image with new one
- CreateProcess(): Windows API for process creation
Process Termination:
- Normal completion
- Critical error
- User termination
- Parent termination (may cascade to children)
- Resource limits exceeded

Threads

Definition: A thread is a basic unit of CPU utilization; lightweight processes within a process.
Thread Components:
- Thread ID
- Program counter
- Register set
- Stack
Shared Resources Between Threads:
- Code section
- Data section
- OS resources (open files, signals)
- Heap memory
Thread Types:
- User-level threads: Managed by user-level thread library
  - Examples: POSIX Threads (Pthreads), Java threads
  - Advantage: Fast thread switching, customizable scheduling
  - Disadvantage: Entire process blocks if one thread makes a blocking system call
- Kernel-level threads: Managed by the operating system
  - Examples: Windows threads, Linux native threads
  - Advantage: Can take advantage of multiprocessing, one thread blocking doesn’t block others
  - Disadvantage: Higher overhead for thread operations
Threading Models:
- Many-to-One: Many user-level threads mapped to one kernel thread
- One-to-One: Each user thread mapped to a kernel thread
- Many-to-Many: Multiplexes many user-level threads to a smaller or equal number of kernel threads

Thread Implementation Example (POSIX Threads):

#include <pthread.h>
 
void *thread_function(void *arg) {
    // Thread code here
    return NULL;
}
 
int main() {
    pthread_t thread_id;
    pthread_create(&thread_id, NULL, thread_function, NULL);
    pthread_join(thread_id, NULL);
    return 0;
}

Threading Benefits:
- Responsiveness: Application remains responsive while processing
- Resource sharing: Threads share process resources
- Economy: Less overhead than creating new processes
- Scalability: Threads can run in parallel on multiprocessor systems

Inter-Process Communication (IPC)

Definition: Mechanisms that allow processes to communicate and synchronize their actions.

Shared Memory:

Fastest IPC method
Region of memory shared between processes

Example (POSIX):

// Process 1: Create shared memoryint shm_id = shmget(KEY, SIZE, IPC_CREAT | 0666);char *shared_memory = shmat(shm_id, NULL, 0);strcpy(shared_memory, "Hello from Process 1");// Process 2: Access shared memoryint shm_id = shmget(KEY, SIZE, 0666);char *shared_memory = shmat(shm_id, NULL, 0);printf("Message: %s\n", shared_memory);

Challenge: Need synchronization to prevent race conditions

Message Passing:

Processes exchange messages through OS kernel
Direct or indirect communication
Operations: send(message), receive(message)

Example (Message Queues):

// Process 1: Send messageint msgid = msgget(KEY, IPC_CREAT | 0666);msgsnd(msgid, &message, sizeof(message), 0);// Process 2: Receive messageint msgid = msgget(KEY, 0666);msgrcv(msgid, &message, sizeof(message), 0, 0);

Pipes:

Unidirectional communication channel

Example (Unnamed pipes between parent-child):

int pipefd[2];pipe(pipefd);if (fork() == 0) {    // Child process: Write to pipe    close(pipefd[0]);  // Close read end    write(pipefd[1], "message", 7);} else {    // Parent process: Read from pipe    close(pipefd[1]);  // Close write end    char buffer[100];    read(pipefd[0], buffer, sizeof(buffer));}

Named Pipes (FIFOs):

Exist as files in the filesystem
Allow unrelated processes to communicate

Example:

// Process 1: Write to FIFOmkfifo("/tmp/myfifo", 0666);int fd = open("/tmp/myfifo", O_WRONLY);write(fd, "Hello", 5);// Process 2: Read from FIFOint fd = open("/tmp/myfifo", O_RDONLY);char buffer[100];read(fd, buffer, sizeof(buffer));

Sockets:

Used for network and interprocess communication

Example (UNIX domain sockets):

// Serverint server_fd = socket(AF_UNIX, SOCK_STREAM, 0);bind(server_fd, &address, sizeof(address));listen(server_fd, 5);accept(server_fd, NULL, NULL);// Clientint client_fd = socket(AF_UNIX, SOCK_STREAM, 0);connect(client_fd, &address, sizeof(address));

Remote Procedure Calls (RPC):
- Extends procedure calls across networks
- Example frameworks: gRPC, XML-RPC, SOAP
- Handles marshalling/unmarshalling of parameters

CPU Scheduling Algorithms

Definition: Algorithms that determine which process runs when and for how long.
Scheduling Criteria:
- CPU utilization: Keep CPU as busy as possible
- Throughput: Number of processes completed per time unit
- Turnaround time: Time from submission to completion
- Waiting time: Total time spent in ready queue
- Response time: Time from submission until first response
First-Come, First-Served (FCFS):
- Simplest scheduling algorithm
- Non-preemptive
- Example:
  - Process P1 (burst time: 24 ms)
  - Process P2 (burst time: 3 ms)
  - Process P3 (burst time: 3 ms)
  - Execution order: P1 → P2 → P3
  - Average waiting time: (0 + 24 + 27)/3 = 17 ms
- Disadvantage: “Convoy effect” - short processes wait for long ones
Shortest Job First (SJF):
- Schedules process with shortest execution time first
- Can be preemptive or non-preemptive
- Example (non-preemptive):
  - Process P1 (arrival: 0, burst: 7)
  - Process P2 (arrival: 2, burst: 4)
  - Process P3 (arrival: 4, burst: 1)
  - Process P4 (arrival: 5, burst: 4)
  - Execution order: P1 → P3 → P2 → P4
  - Average waiting time: (0 + 4 + 7 + 8)/4 = 4.75 ms
- Challenge: Difficult to predict execution time
Priority Scheduling:
- Assigns priority to each process
- Higher priority processes run first
- Example:
  - Process P1 (priority: 3, burst: 10)
  - Process P2 (priority: 1, burst: 1)
  - Process P3 (priority: 4, burst: 2)
  - Process P4 (priority: 2, burst: 1)
  - Execution order (highest priority first): P2 → P4 → P1 → P3
- Issue: Starvation of low-priority processes
- Solution: Aging (gradually increase priority of waiting processes)
Round Robin (RR):
- Time-slicing approach
- Preemptive
- Example (time quantum = 4ms):
  - Process P1 (burst: 20)
  - Process P2 (burst: 3)
  - Process P3 (burst: 4)
  - Execution order: P1(4ms) → P2(3ms) → P3(4ms) → P1(4ms) → P1(4ms) → P1(4ms) → P1(4ms)
  - Average waiting time: ((10-4) + (4-3) + (7-4))/3 = 3.33 ms
- Performance depends on time quantum size
Multilevel Queue:
- Processes assigned to different queues based on properties
- Each queue has its own scheduling algorithm
- Example:
  - Foreground queue (interactive): Round Robin
  - Background queue (batch): FCFS
- Usually with priority between queues (e.g., foreground > background)
Multilevel Feedback Queue:
- Processes can move between queues
- Example:
  - New processes enter highest priority queue
  - If a process uses its full time quantum, it moves to a lower priority queue
  - If a process doesn’t use its full time quantum, it stays at same level
- Adapts to process behavior
- Used in many modern systems including Windows and Unix variants

Process Synchronization

Definition: Mechanisms to coordinate the execution of cooperating processes to maintain data consistency.

Race Condition:

Multiple processes access and manipulate shared data concurrently
Final value depends on order of execution

Example:

// Initial value: counter = 5// Process 1counter = counter + 1;  // Read 5, add 1, write 6// Process 2 (concurrent)counter = counter + 1;  // Read 5, add 1, write 6// Final value: counter = 6 (instead of expected 7)

Atomic Operations:
- Operations that complete in a single step relative to other processes
- Example: Test-and-Set instruction
```
boolean TestAndSet(boolean *target) {    boolean rv = *target;    *target = true;    return rv;}
```

Critical Section Problem

Definition: Problem of designing protocols for processes to cooperate without interfering with each other.
Critical Section: Part of a program where shared resources are accessed.
Requirements for Solution:
- Mutual Exclusion: Only one process can execute in the critical section at a time
- Progress: If no process is in the critical section, a process wanting to enter must be able to (eventually)
- Bounded Waiting: There must be a limit on how many times other processes can enter their critical sections after a process has requested entry

Peterson’s Solution (for two processes):

// Shared variables
int turn;
boolean flag[2] = {false, false};
 
// Process i
flag[i] = true;
turn = j;  // j is the other process
while (flag[j] && turn == j);
// Critical section
flag[i] = false;

Hardware-Based Solutions:

Test-and-Set Lock:

do {
    while (TestAndSet(&lock));
    // Critical section
    lock = false;
    // Remainder section
} while (true);

Compare-and-Swap:

do {
    while (CompareAndSwap(&lock, 0, 1) != 0);
    // Critical section
    lock = 0;
    // Remainder section
} while (true);

Semaphores

Definition: A synchronization tool that uses a counter to control access to shared resources.
Types of Semaphores:
- Binary Semaphore: Can only have values 0 or 1
- Counting Semaphore: Can have arbitrary non-negative values

Operations:

wait(S) or P(S):
```
while (S <= 0); // busy waiting
S--;
```
signal(S) or V(S):
```
S++;
```

Implementation:

typedef struct {
    int value;
    struct process *list;
} semaphore;
 
void wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        // Add this process to S->list
        block();
    }
}
 
void signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        // Remove a process P from S->list
        wakeup(P);
    }
}

Semaphore Applications:

Mutual Exclusion:

semaphore mutex = 1;
 
wait(mutex);
// Critical section
signal(mutex);

Producer-Consumer Problem:

semaphore mutex = 1;
semaphore empty = n;  // Initially all slots are empty
semaphore full = 0;   // Initially no slots are full
 
// Producer
wait(empty);
wait(mutex);
// Add item to buffer
signal(mutex);
signal(full);
 
// Consumer
wait(full);
wait(mutex);
// Remove item from buffer
signal(mutex);
signal(empty);

Readers-Writers Problem:

semaphore mutex = 1;      // Controls access to readcount
semaphore wrt = 1;        // Controls access to the resource
int readcount = 0;        // Number of readers accessing resource
 
// Writer
wait(wrt);
// Write data
signal(wrt);
 
// Reader
wait(mutex);
readcount++;
if (readcount == 1)
    wait(wrt);  // First reader blocks writers
signal(mutex);
 
// Read data
 
wait(mutex);
readcount--;
if (readcount == 0)
    signal(wrt);  // Last reader allows writers
signal(mutex);

Deadlock and Starvation:
- Deadlock: Two or more processes are waiting indefinitely for an event that can only be caused by one of the waiting processes
  - Example:
```
Process 1: wait(S), wait(Q)Process 2: wait(Q), wait(S)
```
- Starvation: Indefinite blocking of a process from accessing a resource
  - Example: In readers-writers, writers may starve if readers keep arriving

Monitors

Definition: A high-level synchronization construct that encapsulates both data and procedures in a module.
Components:
- Mutex (automatic, implicit): Only one process can be active within the monitor at a time
- Condition variables: Allow processes to wait for certain conditions
Operations on Condition Variables:
- wait(): Process is suspended until another process signals
- signal(): Resumes one waiting process
- broadcast(): Resumes all waiting processes

Monitor Example (Java-like syntax):

monitor BoundedBuffer {
    final int N = 10;
    int count = 0;
    Object buffer[N];
    int in = 0, out = 0;
    
    condition not_full, not_empty;
    
    void deposit(Object item) {
        if (count == N)
            not_full.wait();
            
        buffer[in] = item;
        in = (in + 1) % N;
        count++;
        
        not_empty.signal();
    }
    
    Object fetch() {
        if (count == 0)
            not_empty.wait();
            
        Object item = buffer[out];
        out = (out + 1) % N;
        count--;
        
        not_full.signal();
        return item;
    }
}

Implementation Considerations:
- Signal and Continue: After signaling, the signaling process continues execution
- Signal and Wait: After signaling, the signaling process waits and the signaled process executes
- Different languages implement monitors differently (e.g., Java synchronized methods/blocks, C# lock statement)
Differences from Semaphores:
- Monitors provide mutual exclusion automatically
- Monitors are higher-level abstractions, easier to use correctly
- Condition variables in monitors are more structured than semaphores for complex synchronization

Monitor Usage in Modern Languages:

Java:

public class SharedResource {
    private int count = 0;
    
    public synchronized void increment() {
        count++;
        notifyAll();  // Similar to condition.signal()
    }
    
    public synchronized void waitForCount(int value) throws InterruptedException {
        while (count < value)
            wait();  // Similar to condition.wait()
    }
}

C#:

class SharedResource {
    private int count = 0;
    private object lockObj = new object();
    
    public void Increment() {
        lock (lockObj) {
            count++;
            Monitor.PulseAll(lockObj);  // Similar to condition.signal()
        }
    }
    
    public void WaitForCount(int value) {
        lock (lockObj) {
            while (count < value)
                Monitor.Wait(lockObj);  // Similar to condition.wait()
        }
    }
}

Mohammad Abdul Quadeer

chapter-1

Table of Contents