Operating Systems Notes — Fundamentals to Kernel Programming

1947: First transistor (Bell Labs) - Point-contact type
1959: Planar silicon transistor - Foundation for ICs
1971: Intel 4004 - 2,300 transistors
2023: AMD EPYC Genoa - 57 billion transistors

Functions:
├── Arithmetic Operations
│   ├── Addition, Subtraction
│   ├── Multiplication, Division
│   └── Modulo operations
└── Logical Operations
    ├── AND, OR, XOR, NOT
    ├── Bit shifting (Left/Right)
    └── Comparison operations

// Simplified ALU operation representation
uint32_t alu_execute(uint8_t operation, uint32_t operand_a, uint32_t operand_b) {
    switch(operation) {
        case ALU_ADD:  return operand_a + operand_b;
        case ALU_SUB:  return operand_a - operand_b;
        case ALU_AND:  return operand_a & operand_b;
        case ALU_OR:   return operand_a | operand_b;
        case ALU_XOR:  return operand_a ^ operand_b;
        case ALU_SHL:  return operand_a << operand_b;
        case ALU_SHR:  return operand_a >> operand_b;
        default:       return 0; // Invalid operation
    }
}

1. FETCH:    Retrieve instruction from memory[PC]
2. DECODE:   Interpret opcode and extract operands
3. EXECUTE:  Perform operation via ALU or other units
4. STORE:    Write results back to registers/memory
5. INCREMENT: Update Program Counter (PC)

; Example: Adding two numbers using registers
mov rax, 10        ; Load 10 into RAX register
mov rbx, 20        ; Load 20 into RBX register
add rax, rbx       ; Add RBX to RAX (result: RAX = 30)
mov [result], rax  ; Store result in memory

CPU Registers (< 1 KB)
        ↓ Access: 0 cycles
L1 Cache (32-64 KB per core)
        ↓ Access: 1-4 cycles
L2 Cache (256-512 KB per core)
        ↓ Access: 10-20 cycles
L3 Cache (8-64 MB shared)
        ↓ Access: 40-70 cycles
Main Memory (4-256 GB)
        ↓ Access: 100-300 cycles
SSD Storage (128 GB - 4 TB)
        ↓ Access: ~50,000 cycles
HDD Storage (500 GB - 20 TB)
        ↓ Access: ~10,000,000 cycles

// Demonstrating cache-friendly vs cache-unfriendly access

// Cache-friendly: Sequential access (spatial locality)
void sum_array_row_major(int arr[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum += arr[i][j];  // Sequential memory access
        }
    }
}

// Cache-unfriendly: Column-major in row-major storage
void sum_array_column_major(int arr[N][N]) {
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            sum += arr[i][j];  // Jumps across cache lines
        }
    }
}

CPU wants to read memory location 0x1000:

1. CPU places 0x1000 on Address Bus
2. CPU asserts READ control signal on Control Bus
3. Memory responds by placing data at 0x1000 onto Data Bus
4. CPU reads data from Data Bus
5. CPU de-asserts READ signal

Mechanism: Context switching between processes
Policy: Which process to run next (scheduling algorithm)

User Space
│
├─ Application 1
├─ Application 2
└─ Application N
────────────── System Call Interface ──────────────
Kernel Space (Single Address Space)
│
├─ Process Management
├─ Memory Management
├─ File System
├─ Device Drivers
├─ Network Stack
└─ Scheduling
────────────── Hardware ──────────────

// Simplified representation of kernel subsystems
struct linux_kernel {
    struct process_manager {
        struct task_struct *process_list;
        struct scheduler *sched;
    } pm;

    struct memory_manager {
        struct page_table *pgd;
        struct vm_area *vma_list;
    } mm;

    struct file_system {
        struct super_block *sb;
        struct inode_cache *icache;
    } fs;

    struct network_stack {
        struct socket *socket_list;
        struct protocol_handler *protocols;
    } net;
};

User Space
│
├─ File Server
├─ Device Drivers
├─ Network Server
├─ Applications
────────────── IPC (Message Passing) ──────────────
Kernel Space (Minimal)
│
├─ IPC Mechanism
├─ Basic Scheduling
├─ Low-level Memory Management
└─ Hardware Abstraction
────────────── Hardware ──────────────

// Simplified IPC message passing
struct message {
    int src_pid;
    int dst_pid;
    int msg_type;
    char data[1024];
};

// Send message to file server
int read_file(const char *path, char *buffer, size_t size) {
    struct message msg;
    msg.src_pid = getpid();
    msg.dst_pid = FILE_SERVER_PID;
    msg.msg_type = MSG_READ_FILE;
    strcpy(msg.data, path);

    // Send to microkernel IPC
    send_message(&msg);

    // Wait for reply
    receive_message(&msg);

    // Copy data from reply
    memcpy(buffer, msg.data, size);
    return msg.msg_type; // Return value
}

User Space
│
├─ User-mode Services
├─ Device Drivers (some)
└─ Applications
────────────── Mixed Interface ──────────────
Kernel Space
│
├─ Core Kernel (Microkernel-like)
│   ├─ IPC
│   ├─ Scheduling
│   └─ Low-level MM
│
└─ Integrated Services (Monolithic-like)
    ├─ File System
    ├─ Device Drivers (critical)
    └─ Network Stack
────────────── Hardware ──────────────

┌─────────────────────────────────────┐
│       User Space Applications       │
├─────────────────────────────────────┤
│          System Libraries           │
│    (libSystem, Foundation, etc.)    │
├─────────────────────────────────────┤
│           XNU Kernel                │
│  ┌─────────────────────────────┐   │
│  │  BSD Layer (Monolithic)     │   │
│  │  - POSIX compatibility      │   │
│  │  - Networking (TCP/IP)      │   │
│  │  - VFS (Virtual File System)│   │
│  ├─────────────────────────────┤   │
│  │  Mach Layer (Microkernel)   │   │
│  │  - IPC (Mach ports)         │   │
│  │  - Virtual Memory           │   │
│  │  - Task/Thread management   │   │
│  ├─────────────────────────────┤   │
│  │  I/O Kit (C++ drivers)      │   │
│  └─────────────────────────────┘   │
├─────────────────────────────────────┤
│            Hardware                 │
└─────────────────────────────────────┘

┌──────────────────────────────┐
│  Application Code            │
│  + OS Services (LibOS)       │
│  (Single Binary)             │
├──────────────────────────────┤
│  Hypervisor / Hardware       │
└──────────────────────────────┘

Ring 3 (Lowest Privilege) ─── User Applications
Ring 2 (Device Drivers - rarely used)
Ring 1 (Device Drivers - rarely used)
Ring 0 (Highest Privilege) ─── Operating System Kernel

EL0 ─── User Applications
EL1 ─── Operating System Kernel
EL2 ─── Hypervisor
EL3 ─── Secure Monitor (TrustZone)

1. Application executes syscall instruction (INT 0x80, SYSCALL, SVC)
2. CPU switches from User Mode to Kernel Mode
3. CPU saves user context (registers, program counter)
4. CPU jumps to kernel's system call handler
5. Kernel validates request and executes service
6. Kernel prepares return value
7. CPU restores user context
8. CPU switches back to User Mode
9. Application resumes with result

Power On → CPU Reset → POST
│
├─ Test CPU registers
├─ Check memory
├─ Initialize chipset
├─ Detect hardware
└─ Display boot screen

Offset   Size   Description
0x000    446    Boot code
0x1BE    16     Partition entry 1
0x1CE    16     Partition entry 2
0x1DE    16     Partition entry 3
0x1EE    16     Partition entry 4
0x1FE    2      Boot signature (0x55AA)

; boot.asm - Minimal bootloader
BITS 16                 ; 16-bit real mode
ORG 0x7C00              ; BIOS loads us at 0x7C00

start:
    ; Setup segments
    xor ax, ax
    mov ds, ax
    mov es, ax
    mov ss, ax
    mov sp, 0x7C00

    ; Display message
    mov si, message
    call print_string

    ; Hang
    jmp $

print_string:
    lodsb               ; Load byte from [SI] into AL
    or al, al           ; Check if zero (end of string)
    jz done
    mov ah, 0x0E        ; BIOS teletype function
    int 0x10            ; Call BIOS video interrupt
    jmp print_string
done:
    ret

message db 'Booting...', 0x0D, 0x0A, 0

times 510-($-$$) db 0   ; Pad to 510 bytes
dw 0xAA55               ; Boot signature

Power On → UEFI Firmware → Boot Manager → Boot Loader → OS Kernel

Stage 1: Bootstrap code (in MBR or GPT)
   ↓
Stage 1.5: Filesystem drivers (if needed)
   ↓
Stage 2: Full GRUB with menu
   ↓
Kernel Loading: Load kernel image into memory
   ↓
Kernel Execution: Jump to kernel entry point

// Multiboot header (must be in first 8KB of kernel)
#define MULTIBOOT_HEADER_MAGIC  0x1BADB002
#define MULTIBOOT_HEADER_FLAGS  0x00000003

.section .multiboot
.align 4
multiboot_header:
    .long MULTIBOOT_HEADER_MAGIC
    .long MULTIBOOT_HEADER_FLAGS
    .long -(MULTIBOOT_HEADER_MAGIC + MULTIBOOT_HEADER_FLAGS)

; Disable interrupts
cli

; Load Global Descriptor Table (GDT)
lgdt [gdt_descriptor]

; Set PE (Protection Enable) bit in CR0
mov eax, cr0
or eax, 0x1
mov cr0, eax

; Far jump to load CS with code segment selector
jmp 0x08:protected_mode

[BITS 32]
protected_mode:
    ; Setup data segments
    mov ax, 0x10        ; Data segment selector
    mov ds, ax
    mov es, ax
    mov fs, ax
    mov gs, ax
    mov ss, ax

    ; Setup stack
    mov esp, 0x90000

    ; Jump to kernel
    call kernel_main

struct gdt_entry {
    uint16_t limit_low;
    uint16_t base_low;
    uint8_t  base_middle;
    uint8_t  access;
    uint8_t  granularity;
    uint8_t  base_high;
} __attribute__((packed));

struct gdt_ptr {
    uint16_t limit;
    uint32_t base;
} __attribute__((packed));

struct gdt_entry gdt[5];

void gdt_set_gate(int num, uint32_t base, uint32_t limit, uint8_t access, uint8_t gran) {
    gdt[num].base_low = (base & 0xFFFF);
    gdt[num].base_middle = (base >> 16) & 0xFF;
    gdt[num].base_high = (base >> 24) & 0xFF;
    gdt[num].limit_low = (limit & 0xFFFF);
    gdt[num].granularity = ((limit >> 16) & 0x0F) | (gran & 0xF0);
    gdt[num].access = access;
}

void gdt_install() {
    struct gdt_ptr gp;
    gp.limit = (sizeof(struct gdt_entry) * 5) - 1;
    gp.base = (uint32_t)&gdt;

    gdt_set_gate(0, 0, 0, 0, 0);                // Null segment
    gdt_set_gate(1, 0, 0xFFFFFFFF, 0x9A, 0xCF); // Code segment
    gdt_set_gate(2, 0, 0xFFFFFFFF, 0x92, 0xCF); // Data segment
    gdt_set_gate(3, 0, 0xFFFFFFFF, 0xFA, 0xCF); // User code
    gdt_set_gate(4, 0, 0xFFFFFFFF, 0xF2, 0xCF); // User data

    gdt_flush(&gp); // Assembly function to load GDT
}

# Load kernel from SD card
fatload mmc 0:1 ${kernel_addr_r} zImage

# Load device tree
fatload mmc 0:1 ${fdt_addr_r} bcm2710-rpi-3-b.dtb

# Boot kernel
bootz ${kernel_addr_r} - ${fdt_addr_r}

/dts-v1/;

/ {
    compatible = "raspberrypi,3-model-b", "brcm,bcm2837";
    model = "Raspberry Pi 3 Model B";

    memory@0 {
        device_type = "memory";
        reg = <0x00000000 0x40000000>; // 1GB
    };

    cpus {
        #address-cells = <1>;
        #size-cells = <0>;

        cpu@0 {
            device_type = "cpu";
            compatible = "arm,cortex-a53";
            reg = <0>;
        };
        // ... more CPUs
    };

    soc {
        uart0: serial@7e201000 {
            compatible = "brcm,bcm2835-uart";
            reg = <0x7e201000 0x1000>;
            interrupts = <2 25>;
        };
    };
};

1. Decompress kernel (if compressed)
2. Setup initial page tables
3. Enable MMU and caches
4. Parse device tree
5. Initialize memory subsystem
6. Mount initial ramdisk (initramfs)
7. Initialize drivers
8. Start init process (PID 1)

// Simplified Linux kernel initialization (kernel/init/main.c)

asmlinkage __visible void __init start_kernel(void) {
    char *command_line;

    // 1. Setup architecture-specific components
    setup_arch(&command_line);

    // 2. Initialize memory management
    mm_init();

    // 3. Setup scheduler
    sched_init();

    // 4. Initialize IRQs and timers
    init_IRQ();
    init_timers();

    // 5. Initialize console for early output
    console_init();

    // 6. Initialize rest of kernel subsystems
    vfs_caches_init();
    signals_init();

    // 7. Rest of initialization (drivers, etc.)
    rest_init();
}

static noinline void __init rest_init(void) {
    // Create kernel threads
    kernel_thread(kernel_init, NULL, CLONE_FS);
    kernel_thread(kthreadd, NULL, CLONE_FS | CLONE_FILES);

    // CPU idle loop
    cpu_startup_entry(CPUHP_ONLINE);
}

static int __init kernel_init(void *unused) {
    // Try to run init program
    if (!try_to_run_init_process("/sbin/init") ||
        !try_to_run_init_process("/etc/init") ||
        !try_to_run_init_process("/bin/init") ||
        !try_to_run_init_process("/bin/sh"))
        return 0;

    panic("No working init found.");
}

Program: Passive entity (file on disk containing instructions)
Process: Active entity (program loaded in memory and executing)

Example:
- "notepad.exe" is a program
- When you run it, each window is a separate process

High Memory (0xFFFFFFFF)
┌─────────────────────┐
│   Kernel Space      │ ← OS kernel (1GB on 32-bit Linux)
├─────────────────────┤
│   Stack             │ ← Grows downward
│        ↓            │   Function calls, local variables
│                     │
│   (Unused)          │
│                     │
│        ↑            │
│   Heap              │ ← Grows upward
├─────────────────────┤   Dynamic allocation (malloc/new)
│   BSS Segment       │ ← Uninitialized data
├─────────────────────┤
│   Data Segment      │ ← Initialized data
├─────────────────────┤
│   Text Segment      │ ← Program code (read-only)
└─────────────────────┘
Low Memory (0x00000000)

#include <stdlib.h>

int global_initialized = 42;    // Data segment
int global_uninitialized;       // BSS segment
const char *text_data = "Hello"; // Text/Read-only segment

void function() {
    int stack_var = 10;         // Stack
    int *heap_var = malloc(sizeof(int)); // Heap
    *heap_var = 20;
    free(heap_var);
}

struct task_struct {  // Linux representation (simplified)
    // 1. Process State
    volatile long state;        // Running, Ready, Waiting, etc.

    // 2. Process ID
    pid_t pid;                  // Process ID
    pid_t tgid;                 // Thread group ID
    struct task_struct *parent; // Parent process

    // 3. CPU Scheduling Information
    int prio;                   // Priority
    int static_prio;            // Static priority
    int normal_prio;            // Normal priority
    unsigned int policy;        // Scheduling policy
    struct sched_entity se;     // Scheduling entity

    // 4. Memory Management
    struct mm_struct *mm;       // Memory descriptor

    // 5. File Descriptors
    struct files_struct *files; // Open file information

    // 6. CPU Context
    struct thread_struct thread; // CPU registers, PC, SP

    // 7. Signal Handling
    struct signal_struct *signal;

    // 8. Process Times
    u64 utime;                  // User mode time
    u64 stime;                  // Kernel mode time

    // 9. Process Credentials
    uid_t uid, euid;            // User ID, Effective UID
    gid_t gid, egid;            // Group ID, Effective GID

    // 10. List Management
    struct list_head tasks;     // Process list
    struct list_head sibling;   // Sibling list
    struct list_head children;  // Children list
};

      ┌─────────┐
      │   New   │ ← Process being created
      └────┬────┘
           │
           ↓
      ┌─────────┐     Scheduler     ┌─────────────┐
 ┌───→│  Ready  │ ← ─ ─ ─ ─ ─ ─ ─ ─ ┤   Running   │
 │    └────┬────┘    Dispatch       └──────┬──────┘
 │         │                                │
 │         └────────────────────────────────┘
 │                                           │
 │                                           │ I/O or
 │              I/O Complete                 │ Event Wait
 │         ┌─────────────────────────────────┘
 │         │
 │         ↓
 │    ┌─────────┐                       ┌─────────────┐
 └────┤ Waiting │                       │ Terminated  │
      └─────────┘                       └─────────────┘

// Process states in Linux (linux/sched.h)
#define TASK_RUNNING         0
#define TASK_INTERRUPTIBLE   1  // Can be woken by signals
#define TASK_UNINTERRUPTIBLE 2  // Cannot be interrupted
#define __TASK_STOPPED       4
#define __TASK_TRACED        8
#define EXIT_ZOMBIE          16
#define EXIT_DEAD            32

// State transition example
void state_transition() {
    set_current_state(TASK_INTERRUPTIBLE); // Ready → Waiting
    schedule();                             // Yield CPU

    // After wake-up
    // Waiting → Ready → Running (when scheduled)
}

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main() {
    pid_t pid;
    int x = 10;

    printf("Before fork: x = %d\n", x);

    pid = fork();

    if (pid < 0) {
        // Fork failed
        fprintf(stderr, "Fork failed\n");
        return 1;
    } else if (pid == 0) {
        // Child process
        x = 20;
        printf("Child: x = %d, PID = %d\n", x, getpid());
    } else {
        // Parent process
        x = 30;
        printf("Parent: x = %d, Child PID = %d\n", x, pid);
    }

    return 0;
}

/* Output:
Before fork: x = 10
Child: x = 20, PID = 1235
Parent: x = 30, Child PID = 1235
*/

#include <stdio.h>
#include <unistd.h>
#include <sys/wait.h>

int main() {
    pid_t pid = fork();

    if (pid == 0) {
        // Child: Replace with "/bin/ls" program
        char *args[] = {"/bin/ls", "-l", "/tmp", NULL};
        execv("/bin/ls", args);

        // If execv returns, it failed
        perror("execv failed");
        return 1;
    } else {
        // Parent: Wait for child to finish
        int status;
        waitpid(pid, &status, 0);
        printf("Child exited with status %d\n", WEXITSTATUS(status));
    }

    return 0;
}

#include <windows.h>
#include <stdio.h>

int main() {
    STARTUPINFO si;
    PROCESS_INFORMATION pi;

    ZeroMemory(&si, sizeof(si));
    si.cb = sizeof(si);
    ZeroMemory(&pi, sizeof(pi));

    // Create child process
    if (!CreateProcess(
        NULL,               // Application name
        "notepad.exe",      // Command line
        NULL,               // Process attributes
        NULL,               // Thread attributes
        FALSE,              // Inherit handles
        0,                  // Creation flags
        NULL,               // Environment
        NULL,               // Current directory
        &si,                // Startup info
        &pi                 // Process info
    )) {
        printf("CreateProcess failed (%d)\n", GetLastError());
        return 1;
    }

    // Wait for child
    WaitForSingleObject(pi.hProcess, INFINITE);

    // Close handles
    CloseHandle(pi.hProcess);
    CloseHandle(pi.hThread);

    return 0;
}

#include <stdlib.h>

int main() {
    // exit(0)   - Success
    // exit(1)   - General error
    // exit(127) - Command not found

    if (error_occurred) {
        exit(EXIT_FAILURE);
    }

    return EXIT_SUCCESS;
}

// Creating a zombie
#include <unistd.h>

int main() {
    if (fork() == 0) {
        // Child exits immediately
        exit(0);
    }

    // Parent doesn't call wait()
    sleep(60); // Child becomes zombie for 60 seconds
    return 0;
}

#include <sys/wait.h>
#include <stdio.h>
#include <unistd.h>

int main() {
    pid_t pid = fork();

    if (pid == 0) {
        printf("Child process\n");
        sleep(2);
        exit(42); // Exit with status 42
    } else {
        int status;
        pid_t child = wait(&status); // Wait for any child

        if (WIFEXITED(status)) {
            printf("Child %d exited with status %d\n",
                   child, WEXITSTATUS(status));
        }

        // Alternative: waitpid() for specific child
        // waitpid(pid, &status, 0);
    }

    return 0;
}

1. Save current process state (registers, PC, SP) to PCB
2. Update PCB (state, timing information)
3. Move PCB to appropriate queue (ready, waiting)
4. Select next process (scheduling algorithm)
5. Update new process PCB (state = RUNNING)
6. Restore new process context from PCB
7. Switch memory management (page tables)
8. Resume execution of new process

// arch/x86/include/asm/switch_to.h

#define switch_to(prev, next, last) do {                \
    /* Save previous task's context */                   \
    asm volatile(                                        \
        "pushfl\n\t"              /* Save flags */       \
        "pushl %%ebp\n\t"         /* Save base pointer */\
        "movl %%esp,%[prev_sp]\n\t" /* Save stack ptr */ \
        "movl %[next_sp],%%esp\n\t" /* Load next stack*/\
        "movl $1f,%[prev_ip]\n\t"   /* Save return IP */ \
        "pushl %[next_ip]\n\t"      /* Push next IP */  \
        "jmp __switch_to\n\t"       /* Context switch */ \
        "1:\t"                                           \
        "popl %%ebp\n\t"          /* Restore base ptr */ \
        "popfl\n"                 /* Restore flags */    \
        : [prev_sp] "=m" (prev->thread.sp),              \
          [prev_ip] "=m" (prev->thread.ip)               \
        : [next_sp]  "m" (next->thread.sp),              \
          [next_ip]  "m" (next->thread.ip),              \
          [prev]     "a" (prev),                         \
          [next]     "d" (next)                          \
        : "memory", "cc"                                 \
    );                                                   \
} while (0)

init (PID 1) or systemd
├─ sshd
│  └─ bash (login shell)
│     └─ vim
├─ cron
│  └─ backup_script
├─ Apache httpd
│  ├─ httpd (worker 1)
│  ├─ httpd (worker 2)
│  └─ httpd (worker N)
└─ X Window System
   └─ window_manager
      ├─ terminal_emulator
      └─ browser

$ pstree
init─┬─acpid
     ├─cron
     ├─dbus-daemon
     ├─dhclient
     ├─login───bash───pstree
     ├─rsyslogd───3*[{rsyslogd}]
     ├─sshd───sshd───bash
     └─udevd───2*[udevd]

$ ps -ef  # Full process list
$ ps aux  # BSD-style format

Each thread has its own:
├── Program Counter (PC)
├── Stack (local variables, function calls)
├── CPU Registers
├── Thread-local storage
└── Stack pointer

Shared by all threads in process:
├── Process memory (heap, code, globals)
├── File descriptors
├── Signal handlers
└── Current working directory

// User-level thread example (POSIX Threads)
#include <pthread.h>
#include <stdio.h>

void* thread_function(void *arg) {
    printf("Thread ID: %ld\n", (long)pthread_self());
    return NULL;
}

int main() {
    pthread_t thread;

    // Create user-level thread
    pthread_create(&thread, NULL, thread_function, NULL);

    // Wait for thread completion
    pthread_join(thread, NULL);

    return 0;
}

User Thread 1 ↔ Kernel Thread 1
User Thread 2 ↔ Kernel Thread 2
User Thread 3 ↔ Kernel Thread 3

Advantages:
- Full parallelism
- Blocking doesn't stop other threads
- OS sees all threads

Disadvantages:
- High kernel overhead
- Limited number of threads
- Resource consumption

User Thread 1 ┐
User Thread 2 ├→ Kernel Thread 1
User Thread 3 ┘

Advantages:
- Low overhead
- Fast context switching
- No syscalls needed

Disadvantages:
- No true parallelism
- One blocking thread blocks all
- Cannot use multiprocessors

User Thread 1 ┐     ┌→ Kernel Thread 1
User Thread 2 ├─→ ├→ Kernel Thread 2
User Thread 3 ┤     └→ Kernel Thread 3
User Thread 4 ┘

Best of both worlds:
- Multiple kernel threads
- Efficient thread management
- True parallelism with low overhead

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
int shared_counter = 0;

void* increment_counter(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&mutex);
        shared_counter++;  // Critical section
        pthread_mutex_unlock(&mutex);
    }
    return NULL;
}

int main() {
    pthread_t threads[2];

    pthread_create(&threads[0], NULL, increment_counter, NULL);
    pthread_create(&threads[1], NULL, increment_counter, NULL);

    pthread_join(threads[0], NULL);
    pthread_join(threads[1], NULL);

    printf("Counter value: %d (expected: 2000000)\n", shared_counter);

    pthread_mutex_destroy(&mutex);
    return 0;
}

#include <semaphore.h>
#include <pthread.h>
#include <stdio.h>

sem_t semaphore;
int shared_resource = 0;

void* worker(void *arg) {
    for (int i = 0; i < 5; i++) {
        sem_wait(&semaphore);     // Acquire (P operation)

        printf("Thread %ld accessing resource\n",
               (long)pthread_self());
        shared_resource++;

        sem_post(&semaphore);      // Release (V operation)
    }
    return NULL;
}

int main() {
    sem_init(&semaphore, 0, 1);  // Binary semaphore

    pthread_t threads[3];
    for (int i = 0; i < 3; i++) {
        pthread_create(&threads[i], NULL, worker, NULL);
    }

    for (int i = 0; i < 3; i++) {
        pthread_join(threads[i], NULL);
    }

    sem_destroy(&semaphore);
    return 0;
}

#include <pthread.h>
#include <stdio.h>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t condition = PTHREAD_COND_INITIALIZER;
int ready = 0;

void* waiter_thread(void *arg) {
    pthread_mutex_lock(&mutex);

    while (!ready) {  // Always use while, not if
        printf("Waiting...\n");
        pthread_cond_wait(&condition, &mutex);
    }

    printf("Proceeding!\n");
    pthread_mutex_unlock(&mutex);
    return NULL;
}

void* signaler_thread(void *arg) {
    sleep(2);

    pthread_mutex_lock(&mutex);
    ready = 1;
    pthread_cond_signal(&condition);  // Wake one waiter
    pthread_mutex_unlock(&mutex);

    return NULL;
}

int main() {
    pthread_t t1, t2;

    pthread_create(&t1, NULL, waiter_thread, NULL);
    pthread_create(&t2, NULL, signaler_thread, NULL);

    pthread_join(t1, NULL);
    pthread_join(t2, NULL);

    return 0;
}

// FCFS Scheduler Implementation
struct process {
    int pid;
    int arrival_time;
    int burst_time;
    int start_time;
    int end_time;
};

void fcfs_schedule(struct process procs[], int n) {
    int current_time = 0;
    double total_turnaround = 0, total_wait = 0;

    for (int i = 0; i < n; i++) {
        procs[i].start_time = current_time;
        procs[i].end_time = current_time + procs[i].burst_time;
        current_time = procs[i].end_time;

        int turnaround = procs[i].end_time - procs[i].arrival_time;
        int wait = procs[i].start_time - procs[i].arrival_time;

        total_turnaround += turnaround;
        total_wait += wait;

        printf("P%d: Wait=%d, Turnaround=%d\n",
               procs[i].pid, wait, turnaround);
    }

    printf("Average Wait Time: %.2f\n", total_wait / n);
    printf("Average Turnaround: %.2f\n", total_turnaround / n);
}

/*
Example: Processes with burst times [24, 3, 3]
FCFS:  P1_____________________  P2__  P3__
       0                       24    27  30

Waiting times: P1=0, P2=24, P3=27
Average wait: 17ms

Problem: Convoy effect - short processes wait for long ones
*/

void sjf_schedule(struct process procs[], int n) {
    // Sort by burst time (ascending)
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (procs[j].burst_time > procs[j+1].burst_time) {
                struct process temp = procs[j];
                procs[j] = procs[j+1];
                procs[j+1] = temp;
            }
        }
    }

    fcfs_schedule(procs, n);  // Then apply FCFS on sorted list
}

/*
Example: Processes [24, 3, 3]
Sorted:   [3, 3, 24]

Gantt Chart:
P2_  P3_  P1_____________________
0    3    6                       30

Average wait: (0 + 3 + 6) / 3 = 3ms (vs 17ms for FCFS!)
*/

void srtf_schedule(struct process procs[], int n) {
    int remaining[n];
    for (int i = 0; i < n; i++) {
        remaining[i] = procs[i].burst_time;
    }

    int time = 0;
    int total_processes = n;

    while (total_processes > 0) {
        // Find process with shortest remaining time
        int min_index = -1;
        int min_remaining = INT_MAX;

        for (int i = 0; i < n; i++) {
            if (remaining[i] > 0 && remaining[i] < min_remaining &&
                procs[i].arrival_time <= time) {
                min_remaining = remaining[i];
                min_index = i;
            }
        }

        if (min_index == -1) {
            time++;
            continue;
        }

        // Execute for 1 time unit
        remaining[min_index]--;
        time++;

        if (remaining[min_index] == 0) {
            total_processes--;
        }
    }
}