Interface between user and the hardware is called operating system. Job of the operating system is to provide the user programs with a better, simpler, cleaner model of the computer and to handle managing all the resources just mentioned Kernel is a component of the os that manages the hardware resources and serve as the middle ground between applications and hardware

• Process Scheduling and Process synchronization

Monolithic, Micro, and hybrid kernels

Booting Process

The program that the users interact with - Shell, GUI

Two modes of operation - Kernel mode and User mode

OS runs in kernel mode and rest of the software runs in user mode.

Kernel mode is godlike, has access to every hardware and execute any instruction that the machine is capable of.

GUI or shell is the lowest level of user mode software

OS uses software known as driver to control I/O device.

Modern operating system allow multiple programs to be in memory and run at the same time.

System Calls

🛠️ How System Calls Work: The Mechanics

1. A program uses a user-mode API (e.g., read()) as a wrapper for a syscall.
2. That wrapper triggers a trap or interrupt, transitioning to kernel mode.
3. The kernel decodes the syscall number (or instruction), validates parameters, and executes the service.
4. Results or errors are returned to user space, and execution switches back

Process Lifecycle

Resource management

Multiplexing (sharing) resources in different ways - in time and in space.

Processors

The brain of the computer is CPU, it fetches instructions from memory and executes them. Each CPU has a specific set of instructions that it can execute. Thus an x86 processor cannot execute ARM programs.

The stack pointer points to the top of the current stack in memory. The stack contains one frame for each procedure that has entered not exited. A procedure's frame contains local variables, parameters that are not stored in registers.

PSW (Program status word) - contains bits to indicate the mode, control bits etc.

To obtains services from the operating system, a user program must make a system call which traps into the kernel and invokes the operating system. The trap instruction switches from the user mode into the kernel mode and once done gives the control back to user program. Other traps include division by 0 or floating point underflow etc. OS decides what to do (mafia boss)

===Multithreading - the CPU stores the states of multiple threads (a lightweight process) and switches back and forth between them.===

Main memory is divided into cache lines, typically 64 bytes. The most heavily cache lines are kept in a high speed cache located inside or very close the to the CPU.

CMOS stores the current date and time along with configuration parameters such as which drive to boot from.

===The software that talks to a controller giving it commands accepting responses is called device driver. ===

Device controller acts as a bridge between CPU and I/O devices, handling incoming and outgoing signals.

For device driver to work it must be put into kernel mode.

Three ways - Relink the kernel with the driver and reboot the system - Make an entry in an operating system telling it that it needs the driver and then reboot the system. - On the go

Collection of all device registers form the I/O port space

Different ways of Input and Output

• Polling - Driver continuously polls the device to see if it is done, also known as busy waiting.
• Driver starts the device and asks it to give an interrupt when it finished.

Part of the memory with addresses of interrupt handlers - interrupt vector table.

• Using DMA chip - controls the flow of bits between the memory and some controller without constant CPU intervention. The CPU sets up DMA chip with how many bytes to transfer, the device and the flow of direction and once the DMA chip is done, it calls an interrupt

Bus - path for data transfer

Booting the Computer

The flash memory in the motherboard stores the BIOS/UEFI - allows for fast booting.

After we press the power button, the motherboard waits for the signal that the power supply has been stabilized. When CPU starts executing, it fetches from a hard code physical address (known as reset vector) that is mapped to the flash memory. It executes the code from BIOS which detects and initializes the RAM, I/O devices etc.

BIOS would determine the boot device by trying a list of devices stored in CMOS memory. The first sector of the boot device is read into memory and executed (MBR), which contains a program that examines the partition table at the end of boot sector for checking the active partition of boot device. Then loads the OS from the active partition

For UEFI, checks the location of partition table in the second sector of the device. This GPT (GUID Partition Table) contains information about the location of various partitions on the disk. UEFI loads the bootloader to select the OS.

Context Switch

OS saves the process content into PCB, loads the next process's context, switches virtual address space, flushes TLB.

PCB - Identification, State, CPU context, Memory info etc.

Process Table and PCB

Process Tables maps to all active processes, pointers to PCBs.

Used for context switching, scheduling, resources sync etc.

Linux Completely Fair Scheduling

Each process has a vruntime (virtual runtime), which increases by the actual runtime * weight, weight is derived from nice value (-20 to 19). Processes with least vruntime is deemed unfairly treated and are scheduled next.

Entire setup is stored in red black tree, left most node is scheduled first.

Has dynamic time slice instead of fixed time slice like round robin

Arrival Time - When a process enters the ready queue
Burst Time - CPU time required by the process
Waiting Time - Time spent waiting
Turnaround Time - Time from arrival to completion
Response Time - First execution - arrival

FCFS, SJF, PS, RR, Multilevel Queue, Multilevel Feedback Queue

Concurrency

Thread is a lightweight process that may be a part of a larger program. It is the smallest unit of execution

• Its own program counter
• Register set
• Stack
• Execution metadata

In a multi threaded program, there are more than one point of execution.

State of a single thread is similar to that of a process, it has a program counter that tracks where the program is fetching the instructions from and a private set of registers.

If there are two threads that are running on a single processor, when switching from T1 to T2, context switch must take place.

Threads share the same address space.

Why use threads - parallelism, efficiency

TCB

• Thread ID
• Stack pointer, program counter
• Thread state
• Pointer to PCB

===A crash of a thread will affect others due to sharing of address space===

• Concurrency vs Parallelism

#include<stdio.h>
#include<assert.h>
#include<pthread.h>
#include "common.h"
#include "common_threads.h"

void *mythread() {
    printf("Hello there\n");
    return NULL;
} 

int main(int argc, char* argv[]) {
    pthread p1, p2;
    int rc'
    Pthread_create(&p1, NULL, mythread, NULL);
    Pthread_create(&p2, NULL, mythread, NULL);
    Pthread_join(p1, NULL);
    Pthread_join(p2, NULL);
    return 0;
}

Race Conditions

When multiple threads try to update a shared variable simultaneously the final result may be incorrect due to overlapping operations.

updating a variable is not atomic - Reading the value of counter from memory - Incrementing the value - Writing the value back to memory If context switch happens between these steps another thread may overwrite the value

Thread1 - Read Counter(50) -> Increment (51) -> Interrupt Thread2 - Read Counter(50) -> Increment(51) -> Write (counter=51) Thread1: Write (counter = 51e)

One way to avoid this

Disable interrupt (Masking of Interrupts)

void lock() {
    DisableInterrupts
}
void unlock(){
    EnableInterrupts
}

- A non trustable program can disable the interrupt forever - Disabling interrupts can lead to missing noticing some other important interrupts

# Load and store solution
typedef struct __lock_t{
    int flag;
}lock_t;
void init(lock_t *mutex) {
    mutex->flag = 0;
}
void lock(lock_t *mutex) {
    while(mutex->flag == 1); (spin-wait)
    mutex->flag = 1;
}
void unlock(lock_t *mutex) {
    mutex->flag = 0;
}
/* 
Race condition in lock()
Thread A reads flag == 0
Context switch Thread B flag == 0
Critical Section

Busy Waiting (Spin Waiting)

Doesnt work on Multiprocessors
*/

Solution - Use a lock

Use a variable to implement the mutually exclusive access to critical section

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock);
counter = counter+1;
pthread_mutex_unlock(&lock);

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
int counter = 0;
void *increment(void *arg) {
    pthread_mutex_lock(&lock);pthread
    counter++;
    pthread_mutex_unlock(&lock);
    return NULL;
}
int main() {
    pthread_mutex_init(&lock, NULL);
    pthread_t t1,t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t1, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    pthread_mutex_destroy(&lock);
    return 0;
}

• Mutual Exclusion
• Fairness
• Performance - if many threads frequently request a lock, performance drops as mutex operations are expensive.
• Starvation - Occurs when a thread never gets a chance to acquire a lock due to other threads constantly locking it.

Deadlock

Occurs when two or more threads wait indefinitely for each other to release a lock

thread1 locks lock1, then waits for lock2 thread2 locks lock2, then waits for lock1

Always lock in a consistent order Use try-lock pthread_mutex_trylock() so that thread can exit gracefully if fails.

Four Conditions

(MHNC) - Mutual Exclusion - Hold and Wait - No Premption - Circular Wait

DeadLock Prevention

Prevent hold & wait as well as circular wait

DeadLock Avoidance

Banker's Algorithm - Only provides resources if the resultant goes into a safe state

Detection and Recovery

Process Kill, resource preemption, ostrich algorithm

What is a Spinlock?

A spinlock is a type of lock mechanism used in multi-threaded programming where a thread continuously "spins" (busy-waits) until it acquires the lock.

Unlike mutexes, which block the thread and put it to sleep if the lock is unavailable, a spinlock keeps checking the lock in a loop until it becomes free.

---

1. How Spinlocks Work

A spinlock is typically implemented using atomic operations like:

• Test-and-Set (TAS)
• Compare-and-Swap (CAS)
• Load-Linked/Store-Conditional (LL/SC)

Test and Set (Hardware Primitive)

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

void lock(lock_t *lock) {
    while(TestAndSet(&lock->flag, 1) == 1);
}

Compare and Swap (Hardware Primitive)

void lock(lock_t *lock) {
    while(CompareAndSwap(&lock->flag, 0, 1) == 1);
}

Load-linked and store conditional (Lock free synchronization)

Load-Linked (LL) and Store-Conditional (SC) are atomic instructions used in multiprocessor systems to implement lock-free synchronization. These instructions ensure that updates to a shared variable happen atomically without using locks.

Load-linked - Reads a value from memory and monitors it for changes

Store conditional - Stores a new value only if no other thread modified it.

int LoadLinked *ptr{
    return *ptr;
}

int storeConditional(int *ptr, int value) {
    # if no update to *ptr since LL to this addr
    *ptr = value;
    return 1; // Success
    else return 0;
}

void lock(lock_t *lock) {
        while(1) {
            while(LoadLinked(&lock->flag) == 1);
            if(StoreConditional(&lock->flag, 1) == 1)
            return;
         }
}

Fetch and Add (Ticket Lock)

• Fetches the current value of a shared variable
• increments the value atomically
• returns the old value before addition.

Kind of turn based system, every thread gets the lock somehow (fairness brrr)

int FetchAndAdd(int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}
typedef struct __lock_t{
    int ticket;
    int turn;
} lock_t;

void lock_init(lock_t *lock) {
    lock->ticket = 0;
    lock->turn = 0;
}

void lock(lock_t *lock) {
    int myturn = FetchAndAdd(&lock->ticket);
    while(lock->turn != myturn);

}
void unlock(lock_t *lock) {
    lock->turn += 1;    
}

To much spinning for the above methods

Yield to avoid spinning

void init() {
    flag = 0;
}

void lock() {
    while(TestAndSet(flag, 1) == 1)
        yield() // give up the cpu
}

• Can cause starvation
• Context switch cost

Previous methods can cause starvation (either yield of spin-wait)

Using queues to avoid spinning

• Sleeping instead of spinning
• If a process finds that the lock is currently held by another process
• It will be added to a queue of waiting threads
• Then it will be put to sleep by park() system call

• unpark() wakes it up and lock is transferred

• Guard lock - a spin lock used to only protect modifications to flag and queue

• Queue
• Flag - indicates whether the lock is held

typedef struct __lock_t {
    int flag;
    int guard;
    queue_t *q;
}lock_t;

void lock(lock_t *m) {
    while(TestAndSet(m->guard, 1) == 1); // acquire guard lock, if 0, modifications for other threads not allowed
    if(m->flag == 0) { // acquires the lock
        m->flag = 1;
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t *m) {
    while(TestAndSet(&m->guard, 1));
    if(queue_empty(m->q)) {
        m->flag = 0; // release the lock
    } else unpark(queue_remove(m->q));
    m->guard = 0;
}

typedef struct __lock_t {
    int flag;
    int guard;
    queue_t* q;
}lock_t;

void lock(lock_t* m) {
     while(TestAndSet(m->guard, 1) == 1);
     if(m->flag == 0) {
        m->flag = 1;
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());
        m->guard = 0;
        park();
    }
}

void unlock(lock_t* m) {
    while(TestAndSet(&m->guard, 1));
    if(queue_empty(m->q)) {
        m->flag = 0;
    } else unpark(queue_remove(m->q));
    m->guard = 0;
}

Linux Futex (Fast User-space mutexes)

Provide efficient thread synchronization by allowing threads to sleep and wake up in user space without frequent system calls.

void mutex_lock(int *mutex) {
    int v;
    // check 31st bit
    if(atomic_bit_test_set(mutex, 31) == 0) return;
    atomic_increment(mutex);
    v = *mutex;
    while(1) {
        if(atomic_bit_test_set(mutex, 31) == 0) {
            atomic_decrement(mutex);
            return;
        }
        v = *mutex;
        if(v >= 0) {
            continue;
        }
        futex_wait(mutex, v);
    }
    void mutex_unlock(int *mutex) {
        if(atomic_add_zero(mutex, 0x80000000)) return;
        futex_wake(mutex);
    }
}

Semaphore = (Conditional Variables + mutual exclusion)

Scheduling Algorithm

Pre-emptive - A process can go from running queue to ready queue in the middle of execution

Non pre-emptive - Process has to be completed no matter what

Priority can be pre-emptive or non pre-emptive

CPU Parameters

Arrival time - time to arrive Burst time - time to execute Completion time - point of time for completion Turn around time - completion time - arrival time Waiting time - Turn around time - Burst time Response time - (The time at which a process gets CPU first time) - arrival time

===In non pre-emptive, response time = waiting time

Shortest Job First

Priority Scheduling with Pre-emption

Lottery Scheduling in Operating System

• Can be pre-emptive or non pre-emptive
• Probabilistic method ===Ways to manipulate tickets===

Scheduler gives a certain number of tickets to different users in a currency and users can give it to their process in different currency. Eg A - 100, B - 200. The given tickets are converted into global currency at the time of execution.

A process can pass its tickets to another process (client - server)

In this way a process can temporarily raise or lower the number of tickets in owns

• Fairness - less chance of starvation - completely random

• Flexibility

• An attacker can manipulate the scheduling algorithm

Stride Scheduling

Linux Completely Fair Scheduler (CFS)

The CFS is designed to ensure that all the tasks gets a fair share of CPU time, instead of relying on a fixed time slices.

• No need to fixed time slices
• No need of priority boosting

CFS removes the time slices and instead tracks how much time each task has received ensuring fairness

CFS maintains a vruntime for each process, lowest being highest priority (left node of Red Black Tree)

When a task finishes running, it is reinserted based on update vruntime

Only for extra knowledge

vuntime += actual runtime * load weight / nice value weight

The nice value affects the weight of the process (-20 to +19)

nice value 0 -> weight 1024 nice value +5 -> weight < 1024 else weight > 1024

High Memory (User Space) ┌────────────────────────┐
│ User Stack (grows down) │ <-- Used for function calls, local variables
│ │
│ │
│ Heap (grows up) │ <-- Used for dynamic allocations (malloc, new)
│ │
│ │
│ Data Segment │ <-- Stores global/static variables
│ │
│ Code (Text Segment) │ <-- Stores machine instructions
├────────────────────────┤
│ Kernel Stack (per-process) │ <-- Used when the process is in kernel mode
├────────────────────────┤
│ Kernel Space (Shared) │ <-- Contains OS code and data structures
└────────────────────────┘
Low Memory (Kernel Space)

Kernal stack - stores process details when switched to kernel mode, stores system calls, exceptions, interrupts, return address, saved registers etc.

Concurrency Race Condition Need for synchronization Atomicity

Vasu's sir portions

Initial setup

Base and bound pairs for each cpu for allocating the space in the memory for the processes

Also known as dynamic relocation

Not flexible No dynamic growth of stack and heap Context switch is difficult Contigous allocation

Basic page replacement Optimal LRU - counter and stack LRU approximation - Clock algorithm - Second chance and enhanced second chance

Counter based buddy system

FCFS SSTF SCAN LOOK C-SCAN C-LOOK

Name Extension Size Location Identifier Created Date Protection Encryption

Conditional Variables are a way for the threads to communicate with each other

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t full = PTHREAD_COND_INITIALIZER;
pthread_cond_t empty = PTHREAD_COND_INITIALIZER;

void* producer(void* arg) {
    for(int i = 0; i < 10; i++) {
        pthread_mutex_lock(&mutex);
        while(count == BUFFER_SIZE) {
            pthread_cond_wait(&empty, &mutex); // waiting to receive the signal
        }
    buffer[count] = i;
    count++
    pthread_cond_signal(&full); // signalling there is atleast one item in the buffer
    pthread_mutex_unlock(&mutex); 
    }

}

void* consumer(void* arg) {
    for (int i = 0; i < 10; i++) {
        pthread_mutex_lock(&mutex);  // Lock before accessing shared resource

        // Wait if the buffer is empty
        while (count == 0) {
            printf("Buffer is empty, consumer is waiting...\n");
            pthread_cond_wait(&full, &mutex);  // Wait for a producer to add an item
        }

        // Remove an item from the buffer
        count--;
        int item = buffer[count];
        printf("Consumed item: %d\n", item);

        // Signal the producer that there is space in the buffer
        pthread_cond_signal(&empty);

        pthread_mutex_unlock(&mutex);  // Unlock after done
    }
int main() {
    pthread_t prod, cons;
    pthread_create(&prod, NULL, producer, NULL);
    pthread_create(&cons, NULL, consumer, NULL);
    pthread_join(prod, NULL);
    pthread_join(cons, NULL);

}

A semaphore is a synchronization primitive used to manage access to shared resources in concurrent programming. It is primarily used to solve problems where multiple processes or threads need to share resources but need to be controlled to avoid conflicts and ensure proper execution.

Analogy

Imagine a parking lot with 3 spots (semaphore value = 3):

• When a car enters, it calls wait(), reducing available spots.

• When a car exits, it calls signal(), increasing available spots.

• If the lot is full (semaphore = 0), incoming cars must wait.

• As soon as one car leaves and does signal(), a waiting car is allowed in.

Producer Consumer Problem

Producer must not push to filled buffer, and consumer may not take from empty buffer

Counting semaphore / Binary Semaphore

pthread_cond empty = N
pthread_cond full = 0
pthread_mutex lock

# Producer

Producer() {
    // produces something
    wait(empty)
    lock(mutex)
    // add to the buffer
    unlock(mutex)
    signal(mutex)
}

Consumer() {
    wait(full)
    lock(mutex)
    // take from the buffer
    unlock(mutex)
    signal(empty)
}

Readers-Writers Problem

Multiple readers can access it and writers get exclusive access

Writer Preference, Reader Preference

Fair version - make them line up

Dining Philosopher

Prevention

Restrict Entry to N-1 (Atleast 1 get two forks) Odd/Even Three states - THINKING, HUNGRY, EATING

Memory Management

Contiguous Memory Allocation (Fixed and Dynamic)

Fixed partitions -suffers internal fragmentation Dynamic partitions - Variable sized allocation - reduces internal but sufffers external

Non Contiguous Allocation - Paging and Segmentation

Memory divided into fixed size pages and physical memory into frames.

Each process has a page table

MMU - translation, using a translation lookup buffer

May incur internal fragmentation

Segmentation

Divides memory into variable sized segments aligned with local divisions

Segment tables map logical segments to physical addresses.

Suffers from external fragmentation

Segmented Paging - Modern

Swapping and Virtual Memory

Swapping - moves processes between RAM and disk to free space for others.

Virtual Memory uses both paging and swapping

Thrashing - frequent page faults.

Loading & Linking - static and dynamic

Data Structures

Partition Tables, Page Table, Segment Table

Virtual Memory

Page Replacement Techniques

FIFO, LIFO, Optimal, LRU, Clock

File Allocation Techniques

Continuous Allocation Linked Allocation Indexed Allocation

Paging - Hierarchical, Hashed, Inverted

Index Node

Stores the metadata for each file in Linux Uses filename to get the node, which in turn gives the pointers to the data blocks

block[0..11] → Direct pointers to 12 blocks block[12] → Single Indirect (pointer to a block of pointers) block[13] → Double Indirect (pointer to block → pointer to block → data) block[14] → Triple Indirect (3 levels of indirection)