Operating Systems Overview

Conceptual Analogy

• Hardware = Car

• software = Driver

• Direct interaction with hardware can be tedious.

Types of Operating Systems

1. Embedded OS

   • Specific and designed for particular hardware (e.g., AC, oven, fridge).

2. Batch OS

   • Processes jobs in batches without user interaction.

   • Users submit jobs without knowing the completion time.

   • e.g Apache Hadoop

3. Cluster OS

   • Combines multiple computers to act as a single supercomputer.

   • Provides load balancing and redundancy.

4. Distributed OS

   • Manages a network of computers cohesively without a central point, ensuring no single point of failure.

Goals of an Operating System

• Convenience: Provides an easy-to-use interface.

• Efficiency: Maximizes resource utilization (CPU, memory).

• Reliability: Ensures stability and handles errors.

• Security: Protects data from unauthorized access.

User Interaction

• Users interact with the OS, not directly with hardware.

• Jobs can be processed in batches; users cannot track completion time.

Job Management

• Batch Processing: Executes jobs sequentially, not allowing others during execution.

• Multi programming: Loads multiple programs in memory, improving CPU utilization.

Resource Management

• OS manages process scheduling, memory allocation, and I/O devices.

• Aims to keep the CPU busy and reduce idle time.

Additional Notes

• If the system interacts with hardware, it simplifies tasks but may involve tedious processes.

• The OS manages processes, memory, security, files, and I/O tasks.

Multitasking and Multiprocessing

Multitasking

• Multiple processes share CPU time, giving the illusion of full availability.

• Preemption: A process can be stopped to allow another process to run, especially during I/O operations.

Multiprocessing

• Involves multiple CPUs executing processes simultaneously.

• Benefits:

  • Parallelism: Multiple processes run simultaneously.

  • Enhanced performance for applications using multiple cores.

Real-Time Operating Systems (RTOS)

• Designed for critical systems where meeting deadlines is essential (e.g., airbags, missiles).

• Hard RTOS: No tolerance for missed deadlines.

• Soft RTOS: Some tolerance for missed deadlines.

Memory Management

• Main Memory: Where active processes reside (RAM).

• Secondary Memory: Long-term storage (e.g., hard disk).

• A program must be loaded into main memory before execution.

Operating System Architecture

Process Management

• Program: Static entity (e.g., players in a dressing room).

• Active Process: When a program is loaded into memory (e.g., players on the field).

Memory Components in a Process

• Stack: Used for function calls and local variables.

• Heap: For dynamic memory allocation.

• Data: Global and static variables.

• Code: Set of instructions.

OS Structures

1. Monolithic: Everything in one large file (e.g., Mach kernel).

2. Layered OS: Each layer has specific tasks; upper layers can use lower layers (e.g., UNIX).

3. Micro kernel OS: Minimalist kernel, with non-essential functions moved out (e.g., mac OS).

User and Kernel Modes

• User Mode: Limited access; processes cannot directly interact with hardware.

• Kernel Mode: Full access; used for executing system calls.

Context Switching

• Involves saving the state of the current process and loading the state of the next process.

• Allows multiple processes to share CPU time efficiently.

Process Creation

• Fork() System Call: Creates a new process (child) from an existing process (parent).

• Forking is like creating a process identical to the parent process. Consider an example: you are working on a building project, but you can't do all the work by yourself. If you could multiply yourself, you could do a million tasks, but you would have to pay a million workers' wages, which isn't feasible. This is where threading helps. It allows you to have many "hands" on one wage. To the outside operating system, threads appear as one process.

• Parent and child processes can execute concurrently.

• A system call is like asking someone else to do your work, similar to reporting to a police station to catch criminals. You don't go yourself; the constable acts as the operating system in this example.

Process Control Block (PCB)

Data structure for managing process information (state, program counter, memory management). It is like the kundali of the process

Key Components:

• • Process ID : Unique identifier.

    • Process State: Current status (e.g., New, Ready, Running, Waiting, Terminated).

    • Program Counter: Next instruction to execute. if prempt after prempt where to start

    • CPU Registers: Values needed for execution.

    • Memory Management Information: Details about memory allocation.

    • Priority: Affects scheduling.

    • I/O Status Information: Lists allocated I/O devices.

Process States and Transitions

1. New: Created but not yet in memory.

2. Ready: Loaded in memory, waiting for CPU.

3. Running: Actively executing.

4. Waiting: Awaiting an event (like I/O).

5. Terminated: Finished execution.

State Transitions

• New to Ready: Process is created.

• Ready to Running: Scheduler selects the process.

• Running to Waiting: Requests I/O.

• Waiting to Ready: I/O operation completes.

• Running to Terminated: Process finishes execution.

CPU Scheduling

• Decides which process in the ready queue will receive CPU time.

• Preemptive Scheduling: Includes algorithms like:

  • Shortest Job First (SJF)

  • Round Robin

  • Priority Scheduling

• Non-preemptive Scheduling: Includes:

  • First-Come, First-Serve (FCFS)

  • Shortest Job Next (SJN)

Key Metrics

• Arrival Time: When a process enters the ready state.

• Burst Time (BT): Total execution time on the CPU.

• Waiting Time (WT): Time spent waiting in the queue. TAT - BT

• Turnaround Time (TAT): Total time from arrival to completion. CT - AT

• Response Time (RT): Time until the first CPU allocation. FIRST TIME - AT

• As process box left process schedule went time available we minus the first schedule time with the AT FIRST TIME - AT

• Completion Time: The time at which the process completes.

  completion time find by moving right side of the box

As we done with one process and see the ct of process and see arrival time of other process to know which process arrived or not at certain time. and then according to condition of algo choose from options.

In the preemptive nature we stop by each unit of time

CPU Scheduling Types

1. Long-Term Scheduler (Job Scheduler): Controls job admission into the system.

2. Short-Term Scheduler (CPU Scheduler): Selects the next process to execute.

3. Medium-Term Scheduler: Temporarily removes processes from memory to manage resources.

Degree of Multiprogramming (DMP)

• Refers to the number of processes in memory.

• High DMP keeps the CPU busy and reduces idle time.

LTS= Most control on the degree of multi programming

STS= Less control on degree on multi programming

MTS= It reduces the degree of multi programming as takes out process from main memory to secondary memory .

Types of CPU Scheduling

Non-Preemptive Scheduling

In non-preemptive scheduling, once a process starts execution, it runs until completion or voluntarily yields control of the CPU.

Examples:

1. First-Come, First-Served (FCFS): Processes are executed in the order they arrive in the ready queue.

   • Characteristics: Non-preemptive; once a process is running, it cannot be interrupted until it finishes.

   • Problems:

     • Starvation: Not a significant issue, as every process will eventually get CPU time.

     • Convoy Effect: Long processes can delay shorter ones.

FCFS Scheduling Example:

Shortest Job First (SJF)

The process with the smallest burst time is executed next. It can be preemptive or non-preemptive.

Characteristics:

• Non-preemptive: Once a process starts, it runs to completion.

• Preemptive (Shortest Remaining Time First - SRTF): If a new process arrives with a shorter burst time than the currently running process, it preempts the current one.

SJF Example:

Highest Response Ratio Next (HRRN)

This scheduling algorithm prioritizes processes based on the response ratio, calculated as (waiting time + burst time) / burst time.

Example:

1. Given Processes:

   • A: Arrival Time = 0, Burst Time = 5

   • B: Arrival Time = 1, Burst Time = 3

   • C: Arrival Time = 2, Burst Time = 2

2. Execution Steps:

   • At time 0, only A is available, so it runs first.

   • Calculate waiting times for B and C.

   • C has the highest response ratio and runs next.

Preemptive Scheduling

In preemptive scheduling, a process can be interrupted and moved to the ready state before it finishes execution. This is commonly used in time-sharing systems.

Key Characteristics:

• Burst Time Handling: Instead of completing the entire burst time, processes are stopped after 1 unit of time and the burst time is decremented until it reaches zero.

• Equal Burst Time: If multiple processes have the same burst time, the scheduler uses arrival time to decide execution order.

Common Algorithms:

1. Round Robin (RR):

   • Each process is assigned a fixed time slice (quantum). If a process does not complete within this time, it is placed back in the ready queue.

   • Suitable for time-sharing systems where response time is critical.

   • Execution order is based on the time quantum.

   • min (BT,Q ) : burst time : time quantum : Q

Example:

• Given Processes:

  • Process A: Arrival Time = 0, Burst Time = 5

  • Process B: Arrival Time = 1, Burst Time = 3

  • Process C: Arrival Time = 2, Burst Time = 2

  • Time Quantum = 2 ms

• Execution Order:

  • A runs for 2 ms (3 ms left).

  • B runs for 2 ms (1 ms left).

  • C runs for 2 ms (0 ms left, finishes).

  • A runs for 2 ms (1 ms left).

  • B runs for 1 ms (0 ms left, finishes).

  • A runs for 1 ms (0 ms left, finishes).

2. Shortest Remaining Time First (SRTF):

   • The process with the smallest remaining burst time is executed next.

   • If a new process arrives with a shorter burst time, the current process is preempted.

3. Priority Scheduling:

   • Processes are assigned priorities, and the one with the highest priority is executed first.

---

Multilevel Queue Scheduling

This approach divides the ready queue into separate queues based on criteria like process priority or type. There are types of process some high level processes some low level priority processes (system,batch ,interactive ) so different priority queues for different process and different algorithms on it

Characteristics:

• Each queue can have its own scheduling algorithm (e.g., FCFS for batch processes, Round Robin for interactive processes).

• High-priority processes preempt low-priority processes.

• No movement of processes between queues, although some systems allow promotion/demotion based on behavior (e.g., CPU usage).

Key Issues:

1. Starvation: Low-priority processes may starve if high-priority processes keep arriving. Aging can be implemented to gradually increase the priority of waiting processes.

2. Context Switching: The overhead of switching between processes can impact performance. Reducing context switches can help.

Example:

• Two Queues:

  • High Priority Queue (uses Round Robin)

  • Low Priority Queue (uses FCFS)

• Processes:

  • A (High Priority, Arrival Time = 0, Burst Time = 5)

  • B (Low Priority, Arrival Time = 1, Burst Time = 3)

  • C (High Priority, Arrival Time = 2, Burst Time = 2)

  • D (Low Priority, Arrival Time = 3, Burst Time = 4)

• Execution Order:

  • A runs (5 units, completes).

  • C runs (2 units, completes).

  • B runs (3 units, completes).

  • D runs (4 units, completes).

---

Synchronization

Synchronization refers to coordinating concurrent processes to ensure they do not interfere with each other while accessing shared resources.Multiple process sharing sharing resources without interfering with each other and maintain data consistency.

results will different when order is different in code it is race condition.

entry section: Trap to check should i go in the critical section or not

critical section:

exit section: To confirm no other process in cs . I had done my work done it and now I am going

Types of Processes:

• Cooperative Processes: Share the same memory space and can affect each other.

• Independent Processes: Do not share resources and thus do not affect each other.

Critical Section:

A critical section is a part of the code where a process accesses shared resources and must be executed by only one process at a time.

Critical Section Problems:

1. Mutual Exclusion: Only one process can be in its critical section at any time.

2. Progress: Only the interested process goes in the critical section . Non interested should not interfere with the interested process.

3. Bounded Waiting (optional): There should be a limit on how many times other processes can enter their critical sections before the requesting process is granted access.

   e.g : I wil call you . I will call you in 5 min . (Bounded waiting )

Without Synchronization (Race Condition Example):

• Initial State: Shared Variable count = 10

• Process P1 reads count, increments it to 11, prepares to write back.

• Process P2 reads count, also increments it to 11, writes back.

• Final State: The final value of count is 11 instead of the expected 12.

With Synchronization:

Using a lock to ensure mutual exclusion:

plaintextCopy codelock(mutex)     # Acquire lock
# Critical Section
count = count + 1  # Update shared variable
unlock(mutex)   # Release lock

Turn Variable and Flag Array:

• Turn Variable: Indicates whose turn it is to enter the critical section.

• Flag Array: Each process indicates whether it wants to enter the critical section.

Peterson’s Solution:

A method that ensures mutual exclusion using a turn variable and flag array:

plaintextCopy code// Initial state
flag[0] = false // Alice is not interested
flag[1] = false // Bob is not interested
turn = 0       // Start with Alice's turn

function Alice() {
    while (true) {
        flag[0] = true; // Alice wants to use the bathroom
        turn = 1;       // Give Bob a chance to go first
        while (flag[1] && turn == 1) {
            // If Bob wants to go and it's his turn, Alice waits
        }
        // Critical Section: Alice uses the bathroom
        flag[0] = false; // Alice is done using the bathroom
    }
}

function Bob() {
    while (true) {
        flag[1] = true; // Bob wants to use the bathroom
        turn = 0;       // Give Alice a chance to go first
        while (flag[0] && turn == 0) {
            // If Alice wants to go and it's her turn, Bob waits
        }
        // Critical Section: Bob uses the bathroom
        flag[1] = false; // Bob is done using the bathroom
    }
}

---

Lock Variable

A lock variable is used to control access to the critical section in concurrent programming.

• State of Lock Variable:

  • Lock = 0: The critical section is free (unlocked).

  • Lock = 1: The critical section is occupied (locked).

Code Explanation

Analogy: Think of it like a bathroom with a single lock:

• Locked (1): Someone is using it.

• Unlocked (0): It’s free to use.

Code Example:

plaintextCopy codelock_variable = 0; // 0 means unlocked, 1 means locked

function enterCriticalSection() {
    while (lock_variable == 1) {
        // Wait until the lock is available
    }
    lock_variable = 1; // Lock the critical section
    // Code that needs exclusive access goes here
}

function exitCriticalSection() {
    lock_variable = 0; // Unlock the critical section
}

---

Semaphores

A semaphore is a synchronization primitive used to control access to a common resource in a concurrent system using an integer value. Semaphores can be classified into two types: binary semaphores and counting semaphores. Managing the concurrent processes by use of Integer value.

Types of Semaphores

1. Binary Semaphore:

   • Value: Can only be 0 or 1.

   • Use Case: Implements mutual exclusion. When the value is 1, access to the critical section is allowed; when it is 0, access is blocked.

   • Operations:

     • P(S) (wait/down): Decrease the semaphore value. If the value is 0, the process blocks until the semaphore is released.

     • V(S) (signal/up): Increase the semaphore value. If processes are waiting on the semaphore, one will be woken up.

2. Counting Semaphore:

   • Value: Can take any non-negative integer value.

   • Use Case: Indicates the number of processes that can reside in the critical section.

   • Overflow and Underflow:

     • Overflow: Prevented by a counting semaphore that counts empty slots. If full, the producer blocks until space is available.

     • Underflow: Managed using another counting semaphore that counts filled slots. If empty, the consumer blocks until an item is available.

---

Producer-Consumer Problem

The Producer-Consumer problem is a classic synchronization problem that illustrates the challenges of concurrent processes.

A buffer is a temporary storage area used to hold data while it is being transferred between devices or processes.

• Scenario:

  • Producers generate data and put it into a buffer.

  • Consumers take data from the buffer.

  • The buffer has a fixed size, necessitating synchronization to avoid overflow and underflow.

Semaphores in Producer-Consumer

• Empty: Counts how many empty slots are in the buffer (starts at N).

• Full: Counts how many filled slots are in the buffer (starts at 0).

Initialization:

plaintextCopy codeSemaphore Empty = N;   // N empty slots
Semaphore Full = 0;    // 0 filled slots
Semaphore Mutex = 1;   // Lock for mutual exclusion

Producer Process:

plaintextCopy codefunction producer() {
    while (true) {
        item = produce_item(); // Step 1: Create an item
        P(Empty);              // Step 2: Wait if no empty slots
        P(Mutex);              // Step 3: Lock the buffer
        buffer[in] = item;     // Step 4: Add item to the buffer
        in = (in + 1) % N;     // Step 5: Move to the next slot
        V(Mutex);              // Step 6: Unlock the buffer
        V(Full);               // Step 7: Signal a new filled slot
    }
}

Consumer Process:

plaintextCopy codefunction consumer() {
    while (true) {
        P(Full);               // Step 1: Wait if no filled slots
        P(Mutex);              // Step 2: Lock the buffer
        item = buffer[out];    // Step 3: Get an item from the buffer
        out = (out + 1) % N;   // Step 4: Move to the next slot
        V(Mutex);              // Step 5: Unlock the buffer
        V(Empty);              // Step 6: Signal a new empty slot
        consume_item(item);    // Step 7: Use the item
    }
}

---

Reader-Writer Problem

In the Reader-Writer problem, there are two types of processes: readers and writers.

Key Requirements

• Multiple Readers: Multiple readers can access the shared resource simultaneously without issues.

• Exclusive Writing: Only one writer can write to the shared resource at a time, and while writing, no readers can access the resource.

• Consistency: Ensures that readers do not read inconsistent or partially updated data.

Initialization:

plaintextCopy codeSemaphore mutex = 1;       // Mutex for synchronizing access to readCount
Semaphore writeSemaphore = 1; // Semaphore for writers
int readCount = 0;         // Counter for the number of active readers

Reader Process:

plaintextCopy codefunction reader() {
    while (true) {
        P(mutex);            // Acquire mutex to update readCount
        readCount++;         // Increment the number of active readers
        if (readCount == 1) { // If this is the first reader
            P(writeSemaphore); // Block writers
        }
        V(mutex);            // Release mutex
        // Read from the shared resource
        read_data();
        P(mutex);            // Acquire mutex to update readCount
        readCount--;         // Decrement the number of active readers
        if (readCount == 0) { // If this was the last reader
            V(writeSemaphore); // Allow writers to write
        }
        V(mutex);            // Release mutex
    }
}

Writer Process:

function writer() {
    while (true) {
        P(writeSemaphore);   // Acquire exclusive access to write
        // Write to the shared resource
        write_data();
        V(writeSemaphore);   // Release exclusive access
    }
}

Overview of the Dining Philosophers Problem

The Dining Philosophers Problem is a classic synchronization problem in concurrent computing that illustrates the challenges of resource allocation and deadlock. Here’s a breakdown of the problem and its solutions step by step.

Scenario

There are five philosophers sitting at a round table. Each philosopher can either think or eat. To eat, a philosopher needs two forks: one on their left and one on their right.

Resources

The forks are shared resources that each philosopher must pick up before eating.

Problem

If each philosopher picks up the fork on their left simultaneously, they will end up waiting indefinitely for the right fork, leading to a deadlock.

Notation

• 1 = fork on table

• 0 = someone picked up the fork

• V (Up) = signal to put the fork back

• P (wait/Down) = take the fork

Components

• Philosophers: Processes that alternate between thinking and eating.

• Forks: Shared resources required by philosophers to eat.

States of a Philosopher

1. Thinking: The philosopher is not using the forks.

2. Hungry: The philosopher wants to eat and tries to pick up the forks.

3. Eating: The philosopher has both forks and is eating.

Issues to Address

• Deadlock: All philosophers pick up the left fork and wait for the right fork, causing a standstill.

• Starvation: A philosopher might never get to eat if others keep picking up forks.

Adjacent philosophers cannot eat simultaneously due to the arrangement of forks. For instance, if philosopher P0 has fork 0, then philosopher P1 cannot eat because they are sitting together.

Fork Allocation

• Philosopher number = left fork

• Philosopher number + 1 = right fork

Deadlock Scenario

If each of the five philosophers picks up the left fork while waiting for the right fork, it will lead to a deadlock.

Solutions to the Problem

Here are some strategies to prevent deadlock and ensure that all philosophers can eat:

1. Resource Hierarchy Solution

One effective approach to avoid deadlock is to impose an ordering on the resources (forks). Philosophers will always pick up the lower-numbered fork first, which helps in breaking the circular wait condition.

• Fork Picking Order: Philosophers can pick up the right fork first, breaking the traditional left-first strategy.

• Fork Exchange: For instance, if philosopher P4 picks up the right fork, it need forks 0 ,4 to eat as it cant it so , it drop both the forks . philosopher P3 can then acquire forks 3 and 4 to eat. After eating, P3 puts down forks 3 and 4 and signals, allowing P2 to pick up forks 2 and 3. This pattern continues until all philosophers have eaten. Eventually, philosopher P4 can pick up fork 4 and fork 0 to eat.

Example Scenario

• Initial State: All philosophers are thinking.

• P1 wants to eat and picks up the left fork (Fork 1).

• P2 picks up the left fork (Fork 2).

If P1 then tries to pick up the right fork (Fork 2), it leads to a deadlock because P2 is holding it. By implementing the above solutions, such as ensuring proper fork allocation and order, we can prevent deadlock, allowing each philosopher to eat without causing issues.