OSTEP Core Topics

Virtualization

Process Fundamentals

The primary question: How to provide the illusion of multiple CPUs?

For effective CPU virtualization, operating systems need both low-level mechanisms and high-level intelligence:

Mechanism: Low-level methods or protocols that implement required functionality Policy: Algorithms within the OS for making decisions

Essential tasks for running programs:

Loading code and static data into memory Allocating runtime stack memory Allocating heap memory Handling I/O-related operations

Process API Implementation

Key process states:

Running: Process executing instructions on processor Ready: Process prepared to run but not currently scheduled Blocked: Process waiting for an event before continuing

Example implementation with fork, exec, and wait:

/*
 * process_example.c
 */

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

int main(int argc, char *argv[]) {
    printf("Process start (pid: %d)\n", (int)getpid());
    
    int result_code = fork();
    
    if(result_code < 0) {
        fprintf(stderr, "fork operation failed\n");
        exit(1);
    } else if(result_code == 0) {
        // Child process
        printf("Child process running (pid: %d)\n", (int)getpid());
        
        // Execute different program
        char* args[3];
        args[0] = strdup("wc");
        args[1] = strdup("example.c");
        args[2] = NULL;
        execvp(args[0], args);
        printf("This should not appear");
    } else {
        // Parent process
        int wait_result = wait(NULL);
        printf("Parent of %d (result: %d) (pid: %d)\n", 
               result_code, wait_result, (int)getpid());
    }
    
    return 0;
}

Restricted Direct Execution Mechanism

Critical question: How to efficiently and controllably virtualize CPU?

Privilege Separation:

User mode Kernel mode

Process Switching:

Cooperative: Waiting for system calls Non-cooperative: OS control via timer interrupts

Scheduling Introduction

Standard turnaround time formula: (T_{turnaround} = T_{completion} - T_{arrival})

Common scheduling strategies:

FIFO/FCFS: Simple but suffers from convoy effect SJF: Shortest Job First optimizes turnaround time STCF: Shortest Time-to-Completion First Round Robin: Optimizes response time through time slicing

Multi-Level Feedback Queue (MLFQ)

Basic rules:

If A's priority > B's priority, run A (not B) If A's priority = B's priority, time-slice between A and B New jobs enter highest priority queue After using full time quantum, job drops to lower priority Periodically boost all jobs to highest priority to prevent starvation

Proportional Share Scheduling

Lottery scheduling uses randomness to ensure each job receives a certain proportion of CPU time.

Lottery Implementation

typedef struct lottery_scheduler {
    int total_tickets;
    int* process_tickets;
    int num_processes;
} lottery_scheduler_t;

int select_winner(lottery_scheduler_t* scheduler) {
    int random_value = rand() % scheduler->total_tickets;
    int cumulative = 0;
    
    for(int i = 0; i < scheduler->num_processes; i++) {
        cumulative += scheduler->process_tickets[i];
        if(random_value < cumulative) {
            return i;  // Return winning process index
        }
    }
    return 0;  // Default case
}

Concurrency

Threading Basics

Threads share address space while maintaining separate execution contexts including:

Program counter Register sets Stack space

Example thread creation:

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

void *worker_thread(void *arg) {
    printf("%s\n", (char *) arg);
    return NULL;
}

int main(int argc, char *argv[]) {
    pthread_t thread1, thread2;
    int status;

    printf("Main thread: starting\n");
    status = pthread_create(&thread1, NULL, worker_thread, "Task A"); 
    assert(status == 0);
    status = pthread_create(&thread2, NULL, worker_thread, "Task B"); 
    assert(status == 0);
    
    status = pthread_join(thread1, NULL); 
    assert(status == 0);
    status = pthread_join(thread2, NULL); 
    assert(status == 0);
    printf("Main thread: completed\n");
    
    return 0;
}

Lock Implementation

Basic spin lock using test-and-set:

typedef struct spinlock {
    int flag;  // 0 = available, 1 = locked
} spinlock_t;

void init_lock(spinlock_t *lock) {
    lock->flag = 0;
}

void acquire_lock(spinlock_t *lock) {
    while(__sync_lock_test_and_set(&lock->flag, 1)) {
        // Spin until lock is acquired
    }
}

void release_lock(spinlock_t *lock) {
    __sync_lock_release(&lock->flag);
}

Condition Variables

Two primary operations:

pthread_cond_wait(): Releases lock and sleeps pthread_cond_signal(): Wakes sleeping thread(s)

Semaphores

Semaphore operations:

sem_wait(): Decrements value, blocks if negative sem_post(): Increments value, wakes waiting threads

Persistence

I/O Devices

System architecture includes:

CPU connected via memory bus to system memory High-performance devices via I/O bus (PCI/PCIe) Slower devices via peripheral bus

Disk Drives

Performance equation: (T_{I/O} = T_{seek} + T_{rotation} + T_{transfer})

RAID Systems

Levels:

RAID 0: Striping for performance RAID 1: Mirroring for reliability RAID 4/5: Parity for space efficiency

File Systems

Key abstractions:

Files: Linear byte arrays with inode numbers Directories: Maps human-readable names to inode numbers

Virtual Machine Monitors

VMMs provide another layer of abstraction, allowing multiple operating systems to run simultaneously on the same hardware.

Key challenges:

CPU virtualization Memory virtualization Information gap between VMM and guest OS