Operating Systems (Georgia Tech MSCS)

July 20, 2026

Lecture notes from my time in Georgia Tech’s MSCS program. Reference text: OSTEP.

P1L1/2: Introduction to Operating Systems
P2L1: Processes and Process Management
P2L2: Threads and Concurrency
P2L3: Threads Case Study: PThreads
P2L4: Thread Design Considerations
P2L5: Thread Performance Considerations
Midterm Practice Questions
Midterm Formulas
P3L1 Scheduling
P3L2 Memory Management
P3L3 Inter Process Communication
P3L4 Synchronization Constructs
P3 L5 IO Management
P3 L6 Virtualization
P4 L1 Remote Procedure Calls
P4 L2 Distributed File Systems
P4 L3 Distributed Shared Memory
P4 L4 Datacenter Technologies
Final Practice Question
Papers

P1L1/2: Introduction to Operating Systems

An OS is software that abstracts and arbitrates the use of a computer systems resources
- Similar to a toy shop manager as both direct operational resources (use of cpu/memory/devices), enforces working policies (resource access/limits), and mitigates difficulties of complex tasks (abstracts hardware details ie syscalls)
- Has privileged access to the underlying hardware, hides hardware complexity, manages hardware based on policies, and makes sure applications are isolated and protected from each other
OS should separate mechanisms and policies and implement mechanisms to support multiple policies + optimize for the common case
OS operates in kernel mode via cpu bit set allowing it to perform privileged hardware operations and applications are in user mode
- Privileged operations in user mode cause trap instruction where OS verifies request and system calls (open, send, malloc) trap into kernel too
- Signals are sent from kernel mode to application user mode
System calls(OS provided services) 3 steps: 1. write arguments 2. save data at location (pass through or load address) and 3. make the call
- User process calls system call → trap into kernel + execute call → return from trap
- Hardware supported, takes multiple nanoseconds(perf), and switches cache locality
Monolithic OS includes every abstraction and service and optimizations possible allowing inlining and compile time optimizations but less customization, portability, large memory footprint
Modular OS(linux) has basic abstractions and services with customizable module additions via an interface to implement from which drastically reduces memory but less optimizations due to modile interface indirection
Microkernel only has bare minimum abstractions and services with everything else (file systems/device drivers) running outside the kernel
- Supports IPC(inter process communication) as a mechanism due to this
- Very small and easy to test but hard to develop on + very specialized for 1 device + incurred costs for user/kernel context switches

P2L1: Processes and Process Management

A process is an instance of a program
- Like an order of toys with current state(program counter, stack), parts + temporary holding area(data, register state, in memory), special hardware(IO devices)
- Applications on disk/static get loaded in memory into an active entity
Process virtual address space includes stack, heap, data, and text
- Text/code segment has instructions
- Data segment stores global and static variables
- Stack for static allocated memory heap for dynamically allocated memory
Can’t store all virtual addresses to physical in 1 process so OS dynamically allocates address spaces per process and swaps between memory and disk as needed
OS for every process has Process Control Block which includes program counter, register state, stack pointers, state, memory limits etc
- Fields get updated, saved, and restored for every new process running on CPU
- Context switches save and update PCBs and load new process in memory and takes time to do + multiple cache misses due to new cache
OS on bootup creates privileged processes which in turn produce child processes as needed
- Fork child PCB copies parent PCB and starts from instruction after fork()
- Exec replace procedd with new program and start from beginning
OS scheduler decides which ready process to schedule and how long
- It must preempt (interrupt and save context), schedule, and dispatch processes
Processes interact with each other through Inter Process Communication (IPC) where OS maintains protection and isolation while maintaining flexibility and performance
- Message passing IPC OS provides shared communication channel/queue where processes write and read to/from it
  - overhead due to copying from userspace into queue and recieving information
- Shared memory IPC OS establishes shared channel and maps into process address space where processes read/write from memory
  - OS less restrictive here but no provided API’s so must reimplement code

P2L2: Threads and Concurrency

Threads are like a worker in a toy shop as it is an active entity, works simultaneously with others, and requires coordination
Processes have different address space while threads within the same process share the same address space
- Threads still have their own program counter, registers, stack pointers as they still are mini entities of a process
Threads allow you to process separate pieces of input simultaneously/work on different tasks
- Every thread has own cache so fits in more data improving perf and instead of 4 processes with 4 address spaces/4 execution context only 1 address space 4 execution contexts
- Allows the OS to execute its own services concurrently on multicore system
Threads useful even if greater than cpu count if time to idle > 2 * time to context switch
- Thread context switch time < process context switch time as no need to create virtual to physical address mappings
Birrell paper notes down methods for managing threads
- Thread creation with Fork(process/function, arguments) and start where current PC is
- Thread waiting with Join(thread) waiting for thread to finish and return result
- Critical sections which can only be executed by 1 thread at a time need to be explicitly locked and unlocked via a mutex where all other threads are blocked until finished
- Condition variables allow threads to Wait on a variable, allowing it to release the mutex and let other threads Signal with that variable that the task has been done
  - Can Broadcast to all waiting threads to wake and reaquire mutex additionally
Reader/Writer problem where multiple readers can read a file or only 1 writer can write to a file concurrently
- If no one is reading then you can write or read → 0
- If someone is reading then you can only read → 0 >
- If someone is writing then you cannot read or write → -1
- Spurious wake ups happen when multiple threads wake up via broadcast but are unable to acquire the lock as the broadcaster has not unlocked
  - Go from condition variable queue to mutex queue which wastes cycles
  - Solution is to lock only the non state dependent logic and nothing else
Deadlocks occur when threads try to occur mutexes but the mutexes they try to acquire are being held by another thread causing a cycle
- Can unlock n - 1 mutexes before unlocking nth mutex(fine grained locking) but if need to get multiple variables or get all locks upfront and release or mega lock but reduces paralellism
- Instead acquire locks throughout the application in the same order
- Can construct deadlock graph where every node is a thread and every edge is a mutex where the thread is waiting on to the thread where the mutex is held → cycle = deadlock
Threads can either be kernel level (used for os operations) user level (application usage but linked to a kernel level thread)
- One to one model maps a user level thread to a single kernel level thread
  - Allows OS to see what is happening with every user application and can easily manage thread management and synchronization but need to go to OS for all operations and user is limited by OS policies reducing portability
- Many to one model maps all user level threads to 1 kernel thread which is portable and doesn’t depend on OS policies but OS has no idea what user needs and entire process blocks if one user thread blocks
- Many to many model allows dynamic grouping/individualizing of user to kernel level threads which is best of both worlds but need to coordinate user and kernel level thread managers for performance
Kernel can choose between process scope and system scope
- Process scope deals with user level library managing threads within a single process (doesn’t distribute workload evenly)
- System scope manages user threads OS side
Boss-Workers pattern is where boss thread assigns work to workers and workers perform the entire task where throughput is 1/boss time
- Can signal specific workers to assign work so no synchronization but boss will need to track worker status and throughput goes down
- Instead establish a shared queue where boss writes to queue and readers read from the queue (reader/writer pattern) and boss doesn’t need to track workers but queue needs to be synchronized
- Adding/removing workers on demand to fulfill queue workload is very ineffective so maintain a dynamic thread pool of workers allowing easy understanding but must manage thread pool and be aware of thread task cache locality
- Can expand on the boss worker pattern by assigning tasks based on workers specialized for certain tasks
  - More work to do on the boss side is offset by better cache locality but need to determine how much load is needed per task and number of threads per task
Pipeline pattern is there threads get assigned a subtask in the system where every thread is a stage and get passed from stage to stage
- The throughput is the weakest link so assign a threadpool to compensate for this
- Can let next stage thread know and pass on work but lower throughput so use reader/write buffer based communication instead
- Good for specialization and locality but need to balance the workload throughout the stages and synchronize stages
Layered pattern is like the pipeline pattern but groups related subtasks and layers are in any order allowing specialization and less fine grained than pipeline pattern
- However not worth it for all applications and more complicated to synchronize layers

P2L3: Threads Case Study: PThreads

PThreads = POSIX Threads == Portable Operating System Interface Threads specifying the standard OS thread API implementation
Intro code

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

void *foo (void *arg) { /* thread main */
    printf("Foobar!\n");
    pthread_exit(NULL);
}

// If undetachable, can join threads and get result with status variable
int pthread_join(pthread_t thread, void **status);

int main (void) {
    int i;
    pthread_t tid; // Type of thread
    pthread_attr_t attr; // Attributes struct
    
    // Must initialize then set attributes
    // Attributes include stack size, joinable, scheduling, scope, inheritance...
    pthread_attr_init(&attr);
    pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_DETACHED);
    pthread_attr_setscope(&attr, PTHREAD_SCOPE_SYSTEM);
    
    // Pass in pthread, pthread attributes, start routine/function pointer, arguments
    pthread_create(NULL, &attr, foo, NULL);
    
    // Can get/set or destroy attribute structure at end
    pthread_attr_getdetachstate(&attr, &detachstate); // compare detach state
    pthread_attr_destroy(&attr);

    return 0;
}

Creating and joining 4 threads + dealing with arg parameter

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

#define NUM_THREADS 4

void *hello(void *arg) { /* thread main */
    printf("Hello Thread\n");
    return 0;
}

typedef struct {
    int arg1;
    float arg2;
    char *arg3;
} ThreadArgs;

void *foo(void *arg) {
    //Need to cast the argument to the appropriate type
    ThreadArgs *args = (ThreadArgs *)arg;

    printf("arg1: %d, arg2: %.2f, arg3: %s\n", args->arg1, args->arg2, args->arg3);

    return 0
}

int main(void) {
    int i;
    pthread_t tid[NUM_THREADS];
    
    for (i = 0; i < NUM_THREADS; i++) { /* create/fork threads */
        pthread_create(&tid[i], NULL, hello, NULL);
    }

    for (i = 0; i < NUM_THREADS; i++) { /* wait/join threads */
        pthread_join(tid[i], NULL);
    }

    return 0;
}

Mutexes exist too

pthread_mutex_t aMutex;  // mutex type

// explicit lock
int pthread_mutex_lock(pthread_mutex_t *mutex);

// explicit unlock
int pthread_mutex_unlock(pthread_mutex_t *mutex);

// initialize mutex with attributes
int pthread_mutex_init(pthread_mutex_t *mutex, const pthread_mutexattr_t *attr);

// try to lock mutex
int pthread_mutex_trylock(pthread_mutex_t *mutex);

// destroy mutex
int pthread_mutex_destroy(pthread_mutex_t *mutex);

Can have condition variables and can wait on one along with signaling and broadcasting

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond = PTHREAD_COND_INITIALIZER;
int ready = 0;

void* worker(void* arg) {
    int id = *(int*)arg;
    
    pthread_mutex_lock(&lock);
    while (!ready) {
        printf("Thread %d waiting...\n", id);
        pthread_cond_wait(&cond, &lock);
    }
    printf("Thread %d received signal!\n", id);
    pthread_mutex_unlock(&lock);

    return NULL;
}

int main(){
        ...
        printf("Signaling one thread...\n");
    pthread_cond_signal(&cond);
    sleep(2);

    printf("Broadcasting to all...\n");
    pthread_cond_broadcast(&cond);
      ...
}

Producer/Consumer example

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

#define BUFFER_SIZE 5
#define PRODUCE_COUNT 10

int buffer[BUFFER_SIZE];
int count = 0; // Number of items in the buffer

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond_full = PTHREAD_COND_INITIALIZER;
pthread_cond_t cond_empty = PTHREAD_COND_INITIALIZER;

void* producer(void* arg) {
    for (int i = 1; i <= PRODUCE_COUNT; i++) {
        pthread_mutex_lock(&lock);

        while (count == BUFFER_SIZE) {
            pthread_cond_wait(&cond_empty, &lock);
        }

        buffer[count++] = i;
        printf("Produced: %d | Buffer Size: %d\n", i, count);

        pthread_cond_signal(&cond_full);
        pthread_mutex_unlock(&lock);

        sleep(1);
    }
    return NULL;
}

void* consumer(void* arg) {
    for (int i = 0; i < PRODUCE_COUNT; i++) {
        pthread_mutex_lock(&lock);

        while (count == 0) {
            pthread_cond_wait(&cond_full, &lock);
        }

        int item = buffer[--count];
        printf("Consumed: %d | Buffer Size: %d\n", item, count);

        pthread_cond_signal(&cond_empty);
        pthread_mutex_unlock(&lock);

        sleep(2);
    }
    return NULL;
}

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);

    pthread_mutex_destroy(&lock);
    pthread_cond_destroy(&cond_full);
    pthread_cond_destroy(&cond_empty);

    return 0;
}

P2L4: Thread Design Considerations

User level threads store stack/reg/ids on the user side if using user level library and kernel level thread information is separate from PCB for separation of concerns issue
- User level threads and PCB relationship as need to keep track of address spaces
- PCB and kernel level threads both need to know which kernel level threads are executing and which/where address spaces where the threads are executing are
- CPU and kernel level threads need to know which thread is executing and which cpu is the thread using
- Hard process state (address mappings) accessible by all threads in PCB and light process state only for user level threads linked with a kernel level thread
- Instead of using a single PCB per process which gets saved/restored entirely on context switches and needs to be updated all at once, use multiple data structures that split up the PCB for easy sharing, saving/restoring necessary info, smaller state updates
Sun Solaris OS implements a lightweight threading model where every kernel thread executing user thread has lightweight process data
- Stack/threads may overwrite next process memory so implement red zone which causes fault by OS if accessed
The user level library does not know what happens in the kernel and vice versa
- How many kernel level threads do we have, is the kernel level thread blocking causing process to block, do we have unused kernel level threads, scheduler unaware of external factors
- Solve this by passing syscalls or signals from user ↔kernel or kernel thread ↔kernel thread to communicate and change threading info
- User threads bind to kernel threads known as pinning
For short critical sections on multiple cpus, better to spin lock for mutex over blocking and ceding control of the cpu to avoid context switch cost
Put threads on death row and occasionally destroy them with reaper thread if exits ; if needs to be reused then performance gains
Interrupts are events generated not by the CPU (hardware, timers) which are platform dependent and asynchronous vs Signals generated by the CPU dependent on the OS and can be synchronous or asynchronous
- Uiuds for both are cpu masked affecting OS for interrupts and process masked affecting process for signals
- Hardware sends message signaled interrupt which if enabled disturbs thread execution and determine execution logic with <interrupt number, handler start address> table
  - <Hardware defined, OS defined> table
- Similar for signal handling but sent by cpu directly and has <signal number, handler start address> table
  - <OS defined, process specific> table
If interrupts/signals are enabled 24/7 we may deadlock if a thread has to resolve one while acquiring a mutex
- Use bitmasks where 1 enabled and 0 disabled before lock and after locking mutex and if disabled then set them as pending
  - Treat interrupt/signal as a thread in order to wait on pending/disabled if the handler can block on a mutex else execute on uninterrupted thread stack
    - Optimization to preinitialize X threads for interrupts as dynamic thread creation is expensive
- Interrupt masks are per cpu and signal masks per execution context/thread
- Can designate interrupts to any cpu but to avoid overhead, designate 1 cpu to send off interrupts to
One shot signals convert n signals pending to 1 signal and all must be renabled explicitly vs real time signals where n signals get called by handler n times
Interrupts are processed in 2 stages: top half and bottom half to minimize blocking time
- Top half is fast and non blocking and usually schedules bottom half
- Bottom half is slower and has the bulk of complexity of the handler
If we clear signal masks on the user side, how to clear mask kernel side without trapping inside kernel?
- Wrap signal handler logic within thread library handling routine to check all user threads masks and can also send directed signals to other kernel/user level threads on separate cpus to execute signals there
- If kernel thread sends signal to user thread and all user threads are 0, then set kernel thread signal mask to 0 and try again with next kernel thread
- Essentially for all kernel level threads one by one, examine their user level threads greedily for a signal and try to handle the first one where its enabled
Linux has task structs to represent a kernel level thread which is created by clone(function, stack pointer, bitmask flag, arguments)
- Uses 1:1 model as kernel traps are cheaper and memory is widely available

P2L5: Thread Performance Considerations

For execution time, the pipeline threading model is better ; for average time to completion the boss worker model is better
Threads parallelize/speed up, specialize/provide hot caches, and are efficient with lower memory overhead and cheaper synchronization but we need to measure performance based on the individual problem at hand for usefulness
- Metrics need to be measureable or quantifiable for a system evaluating its behavior
Can achieve concurrency by spawning multiple processes for a web server which is simple but incurs high memory overhead, costly context switches, and hard to maintain shared state
Instead we can multithread the web server achieving shared state and address space(less memory overhad) along with cheap context switches ; but this is harder to implement, must synchronize threads, and platform must have support for threads
Event driven model has 1 event dispatcher looking for incoming events that run handlers to completion
- A single thread switches among processing of different requests and concurrency is achieved here as if handler blocks, relinquish control to event dispatcher
  - Works as long as waits happen as more efficient to context switch and incur that overhead instead of waiting aimlessly
- Benefits include single address space + flow of control, smaller memory requirement, no context switching, no synchronization
Event driven model works via file descriptors (both files and sockets use this)
- An event is an input on file descriptor and we search for events with select() or poll() call → recently epoll() as don’t have to search entirety of file descriptors and detect input changes
One con of event driven model is that one blocking operation blocks the entire process
- Can use asynchronous I/O operations where OS gets all relevant info, runs operation on separate thread, and learns where to return results or tells caller where to return result
- What if we dont have kernel support or device support? → Use helpers that execute only for blocking I/O operations so that event loop does not block
  - Not all kernels were multithreaded when Flash was created so helpers are a separate process ie Asymetric Multi Process Event Driven Model (AMPED)
  - No portability limitation + smaller footprints than worker threads
Flash is an Event Driven Web Server which implements pattern above
- Caches file content, response headers, and even the lookup mechanisms for finding file
- Has alignment for DMA and scatter gather/vector I/O operations
Apache Web Server more modern Web Server
Benchmark for webservers in terms of bandwidth for SPED, AMPED, ZEUS, MT, MP, and unoptimized Apache
- When data is in cache SPED > AMPED as less memory presence checks >> MT/MP as no synchronization or context switch overheads
- When data is in disk AMPED > SPED as uses helpers and async I/O does not make this block >> MT/MP

Midterm Practice Questions

Part 1:

What are the key roles of an operating system?
1. An OS abstracts away a lot of the logic away from end user (system calls) and arbitrates use of system resources (memory, cpu)
Can you make distinction between OS abstractions, mechanisms, policies?
1. Abstractions make the process of doing something (fopen, mmap, syscalls) for the end user simple and hides implementation details
2. Mechanisms are the logic behind what the OS does and they implement policies which enforce some capacity of the os
What does the principle of separation of mechanism and policy mean?
1. Mechanisms tell you how to implement the task and policies tell you when to do/enforce/perform a task
What does the principle optimize for the common case mean?
1. Optimizing for the common case means that we optimize for the thing that occurs most often in real life scenarios and get the best performance benefit most of the time
What happens during a user-kernel mode crossing?
1. Go from user mode to privileged kernel mode where we can do privileged operations such as access cpu, ram, file systems usually done with a trap instruction
2. User space state saved and restored later
What are some of the reasons why user-kernel mode crossing happens?
1. We want to perform a privileged operation (system calls, device IO, page faults) from the user side
2. Interrupt handling from hardware needs to be handled by the OS
3. Threads/processes context switch
What is a kernel trap? Why does it happen? What are the steps that take place during a kernel trap?
1. When we go from user mode to kernel mode (trap instruction in asm)
2. Save the cpu state then trap into kernel, then check the trap type via trap table, run the trap handler based on that, restore cpu state and return fromt rap
What is a system call? How does it happen? What are the steps that take place during a system call?
1. User space function where we need to do a privileged operation which requires trapping into the os, performing the system call there via the system call number, and returning from trap with the result by executing the system call handler
Contrast the design decisions and performance tradeoffs among monolithic, modular and microkernel-based OS designs.
1. Monolithic has everything which optimizes performance the best but hard to customize and not portable at all with highest memory overhead
2. Modular has the essentials provided and allows customizability via modules (linux) so it is more portable and drastically reduces memory overhead
3. Microkernel only has the bare minimum and nothing more which optimizes memory usage the best but no portability meant for one device and kernel crossings unoptimized Part 2:
Process vs. thread, describe the distinctions. What happens on a process vs. thread context switch.
1. Threads are “lightweight processes” where they are contexts that share the same address space.
2. On context switch you replace process PCB and need to replace memory mappings compared to thread control block
  1. Process needs to switch address spaces, flush caches, update tlb, remap which has a high overhead
Describe the states in a lifetime of a process?
1. Processes are created, can be ready for queuing, can terminate, can be interrupted, and can wait on an IO call
Describe the lifetime of a thread?
1. Same as 2a
Describe all the steps which take place for a process to transition form a waiting (blocked) state to a running (executing on the CPU) state.
1. An IO request is made which makes process go from running to waiting
2. The IO request finishes and process goes from wait queue to ready queue
3. Process ready to be scheduled again and ready queue to running
What are the pros-and-cons of message-based vs. shared-memory-based IPC.
1. Shared memory based IPC needs to set up memory mappings before communication transfer but no reason to go to kernel except for initial calls but need to synchronize access to shared memory compared to message based which os simplifies
What are benefits of multithreading? When is it useful to add more threads, when does adding threads lead to pure overhead? What are the possible sources of overhead associated with multithreading?
1. Useful to add more threads to horizontally scale or when idle time > 2 * context switch time
2. Need to context switch, manage synchronization, lock contention
Describe the boss-worked multithreading pattern. If you need to improve a performance metric like throughput or response time, what could you do in a boss-worker model? What are the limiting factors in improving performance with this pattern?
1. Boss schedules workers to do tasks to completion
2. Can make sure to reduce boss time (worker queue) or add more workers or specialize threads for certain tasks but the boss + the shared queue is the main bottleneck here
Describe the pipelined multithreading pattern. If you need to improve a performance metric like throughput or response time, what could you do in a pipelined model? What are the limiting factors in improving performance with this pattern?
1. Every step of the logic is handled by a thread and the throughput is the weakest step so for certain steps add more threads but could have queue buildup and slower stages in general
What are mutexes? What are condition variables? Can you quickly write the steps/code for entering/existing a critical section for problems such as reader/writer, reader/writer with selective priority (e.g., reader priority vs. writer priority)? What are spurious wake-ups, how do you avoid them, and can you always avoid them? Do you understand the need for using a while() look for the predicate check in the critical section entry code examples in the lessons?
1. Mutexes lock access to shared memory and condition variables wait on a variable to be signaled/brodcasted while releasing the lock for other workers to do whats needed
2. Spurious wake ups when threads wake up but still locked so waste cycles from sleep to wait queue/while loop and u can sometimes solve by signaling/broadcasting after the mutex unlock as long as not accessing shared memory there
3. Use while CV instead of if CV since you don’t know if you’re the thread that will have the mutex lock
What’s a simple way to prevent deadlocks? Why?
1. Implement partial ordering of deadlocks so if u will lock m1 then m2 then m3 somewhere then all threads that lock should acquire locks in that order
Can you explain the relationship among kernel vs. user-level threads? Think though a general mxn scenario (as described in the Solaris papers), and in the current Linux model. What happens during scheduling, synchronization and signaling in these cases?
1. 1:1, N:1, M:N thread pinning where user thread needs to attach itself to kernel thread for safety and syscalls
  1. 1:1 in linux and allows os to see what happens but less portability as limited by os policies and need to go to os for all operations
  2. N:1 user level side has control of threads and not dependent on OS but since OS doesn’t know what user needs 1 thread block means entire block and scheduling done user side
  3. M:N best of both worlds but need to coordinate user and kernel level thread managers
2. Scheduling needs to be done user side also if multiple N threads user side bunched up and signaling for every kernel level thread, need to check all user level threads to dispatch a signal greedily
What’s an interrupt? What’s a signal? What happens during interrupt or signal handling? How does the OS know what to execute in response to a interrupt or signal? Can each process configure their own signal handler? Can each thread have their own signal handler?
1. Interrupt sent by hardware and the hardware handler is OS configured and only async
2. Signal sent by cpu and the signal handler is process configured
3. OS knows what to execute with interrupt/signal handlers and every process has signal handler but not threads but signals can be sent to specific threads
Can you explain why some of the mechanisms described in the Solaris papers (for configuring the degree concurrency, for signaling, the use of LWP…) are not used or necessary in the current threads model in Linux?
1. Adding new kernel level threads are pretty cheap and memory efficient so no need to do the N:M model anymore + signal handling is easier to implement with 1:1 model
What’s the potential issue if a interrupt or signal handler needs to lock a mutex? What’s the workaround described in the Solaris papers?
1. If u lock mutex and then handle signal you could deadlock so make sure to have signal mask in order to set signal as disabled/pending and then renable once allowed … can also treat interrupts as threads to wait on pending result
Contrast the pros-and-cons of a multithreaded (MT) and multiprocess (MP) implementation of a webserver, as described in the Flash paper.
1. MP is process does entire webserver and MT there are multiple requests handled essentially memory utilization is less in threads but must synchronize
What are the benefits of the event-based model described in the Flash paper over MT and MP? What are the limitations? Would you convert the AMPED model into a AMTED (async multi-threaded event-driven)? How do you think ab AMTED version of Flash would compare to the AMPED version of Flash?
1. Event driven model has no context switching overheads along with no context switching and extra sync but if IO operation happens it blocks (AMPED reason) but AMPED not every kernel supports async IO so need to convert threads to processes
  1. Use AMTED if there since threads cheaper in memory
There are several sets of experimental results from the Flash paper discussed in the lesson. Do you understand the purpose of each set of experiments (what was the question they wanted to answer)? Do you understand why the experiment was structured in a particular why (why they chose the variables to be varied, the workload parameters, the measured metric…).
1. Sequential vs random trace and metric was bandwidth to show how fast web servers can process files and what happens on small vs larger traces
If you ran your server from the class project for two different traces: (i) many requests for a single file, and (ii) many random requests across a very large pool of very large files, what do you think would happen as you add more threads to your server? Can you sketch a hypothetical graph?
1. This assumes as long as thread count ≤ cpu core count as if this exceeded this and idle time < 2 * ctx switch time then inefficient
2. If multiple threads added under that limit for same file then file is cached in memoery and dealing with hot cache but if dealing with same file then icnreased contention but cache utiolizaiton vs random files where workload spread out but cold cache

Midterm Formulas

Throughput: tasks/time
Useful CPU work: Total processing time / total time
CPU utilization: CPU running time / (cpu running time + context switching overhead)
Whether context switch is worth it: time idling > 2 * context switch
Boss worker
- Completion time: Time to finish 1 order * ceiling ( num orders / num of threads)
- Average time: Total time for orders / number of orders
Pipeline
- Completion time: the time to finish the first order + (remaining orders * the time to finish the bottlenecked stage)
- Average time: Total time for orders/ number of orders

P3L1 Scheduling

CPU Scheduler picks from ready state tasts with a timeslice by context switching, entering user mode, setting the program counter for that task and dispatched
Run to completion scheduling includes First Come First Server and Shortest Job First (with an ordered run queue structure)
Preemptive scheduling means OS can interrupt process and schedule another one instead and should not expect tasks to come all at once + execution time is unknown
- Priority scheduling runs and preempts tasks based on priority with ordered queue
  - Should note starvation happens here with low priority tasks so need to have good priority heuristic for this
  - Sometimes when a high priority task needs a mutex but cannot get it from lower priority tasks, the order of execution inverses → priority inversion
    - Solution is to temporarily boost mutex owner then lower on mutex release
- Round robin scheduling keeps scheduling tasks from start to end then start of queue
  - To add priorities, must add preemption to scheduler and interleaving add timeslicing
- Timeslicing allows involuntary preemption to prevent starvation allowing more responsiveness and shorter tasks finished off but need to deal with interrupt/context switch/scheduling overheads
  - Timeslice should be greater than context switch time
  - For CPU bound tasks, larger timeslices has better throughput and completion time but worse waiting time
  - For IO bound + normal tasks shorter timeslices has better performance
Need to make sure runqueue is easily accessible to find the next task
- If we have both cpu and io bound values then use multi level feedback queue where topmost is IO bound tasks and bottommost cpu bound tasks and prioritize top to bottom
Linux O(1) scheduler allows O(1) time to select/add task with 140 priority levels where higher priorities had more timeslices (for IO intensive)
- However must wait for active tasks to finish before expired tasks reschedule which causes jitter in interactive tasks and reduces fairness
Linus CFS (Completely Fair Scheduler) queue is a red black tree ordered by time spent on cpu
- Always pick leftmost node to schedule and adjust the runtime and keep running as long as its runtime is smaller than the next smallest node else preempt and place in tree
- Runtime increase depends on task priority and niceness so faster increase for low priority tasks and slower increase for high priority tasks
- O(1) task select and O(logn) task add
CPUs can sometimes have multiple cores with their own private caches and OS treats these as more entities to schedule tasks on
- When scheduling a thread on 1 cpu it stores state on a cache but if it gets scheduled on another cpu then lower performance cold cache
  - Aim is to schedule same thread on same CPU → cache affinity
    - Achieve this using a load balancer where every cpu has its own per cpu scheduler
Can also have multiple memory and aim is to keep memory nodes closer to socket of certain cpus → Non Uniform Memory Access (NUMA)
Hyperthreading/SMT allows 1 cpu to have multiple hardware supported execution contexts allowing very fast context switches
- Good to schedule both cpu and memory intensive tasks concurrently and ctx switch only to perform memory operation to fully utilize all cpu cycles
To determine if a task is cpu or memory bound we cannot use sleep time as thread isnt sleeping on memory access and using software takes too much time to compute metrics
- Hardware counters (L1, L2… misses, IPC, power/energy data) are used instead to estimate
Cycles per Instruction could be useful as cpu bound tasks are 1 CPI and memory bound tasks are high (using multiple cpu cycles waiting on memory access)
- Simulate this on 4 core * 4 SMT with 4 threads and CPI’s of 1, 6, 11, 16 and on every core, run a mix of CPI’s
- For mixed CPI workloads we have the highest IPC as processor pipeline is most utilized with the same CPI we have some core contention and waste cycles on other cores
- However real life workloads dont have big CPI variance so in practice this will not work

P3L2 Memory Management

Memory management uses intelligently sized containers (memory pages), doesn’t need all memory (subset of memory is used), and is optimized for performance (reduced time to access memory)
Memory managements goal is to allocate/replace pages + arbitrate translation/validation access mapping virtual pages to physical page frames
- Page based memory management allocates pages/page frames and arbitrates page tables
- Segment based memory management allocates segments and arbitrates segment registers
- MMU hardware unit that translates virtual to physical addresses
- Registers tell you where page table is, base/limit sizes, and number of segments
- TLB is a cache that holds valid virtual to physical address translations
Page tables are allocated per process and map virtual pages to physical pages
- A virtual page number is used to index into the page table and the physical address is accessed with the[physical frame number + offset]
- On access of the first memory allocation we realize that the page table has no allocation, so pick a page from physical DRAM memory and establish the mapping
Page table entries have flags to determine memory access permissions and if invalid access then page faults, generates error code, traps into kernel and runs handler
- Page fault handler varises from bringing page from disk to memory to actual protection error (SIGSEGV)
Page table size is (virtual address space / page size) * size of page table entry
- If 4 byte PTE, 32 bit architecture, and 4kb page sizes then size is (2^32/2^12) * 4 bytes = 4mb ; 64 bit systems means petabytes of page table size since assumes using all VPNs
- Instead to conserve space use multi level page tables where we have multiple virtual page numbers that index into directories which helps on 64 bit architectures as their address spaces are larger and more sparse
  - Reduces space but more memory accesses are needed to translate + need to allocate new page directories on top of physical memory in real time
N level page tables lead to N memory accesses so use TLB to store cache of VPN → PPN frames
Instead of basing page table on virtual addresses why not invert the page table and make it the size of physical memory where we index via process id + virtual page number
- Saves size that way but need to linearly search table as not ordered (TLB can catch) or hash the VPN and provide possible entries based on that to speed up
Segmentation is utilized with selector bits to segment into an area of memory and size is determined with the limit registers and used along with paging
The larger that pages are, the fewer page table entries and page table size is causing more TLB hits but leads to internal fragmentation
While paging/segmentation translates virtual to physical addresses, memory allocation determines which virtual to physical mappings are created
- Kernel level allocators allocate memory for kernel and static process state and user level allocators allocate memory for user processes and the user process is in control if memory is created or freed (malloc/free)
- Challenge with memory allocation as can have enough free bytes on heap to allocate but bytes are not contiguous and will not fit (external fragmentation)
Buddy allocator starts with a 2^x segment and divides the memory space into 2 until you find smallest possible fit for request which makes freeing and aggregation easy
- Still has internal fragmentation so can use slab allocator which prebuilds caches for certain structs and allocates slabs per cache and request goes to cache so no internal fragmentation but has external fragmentation
The virtual address space is bigger than the physical RAM memory itself usually so sometimes we must bring in a page from disk to ram and swap a page
We free pages when memory usage is high (lots of swapping) or cpu usage is low (can use resources then) with LRU or pages that wont be written out
- On linux can categorize pages to tune thresholds
For process creation w/ fork we copy the entire address space but why not just reference the original parents pages until a write happens then copy those pages only → Copy on Write
Checkpointing useful for saving process state so don’t have to restart everything on a crash
- Write protect and copy everything once + copy diffs of dirty pages for incremental checkpoints
- Rewind replay helps for debugging where you restart process state from checkpoints and keep going back unti the error is found
- Can also use this for migration where you continue process state on another machine

P3L3 Inter Process Communication

IPC OS supported mechanisms to communicate between processes
- Can message pass with sockets, pipes, message queues
- Can communicate via memory w/ shared memory or memory mapped files
- Can use files or RPC too
Message passing IPC the OS creates the channel and provides interface to processes to send/recieve messages from this interface
- Very simple but overhead due to both sending and recieving needing system calls + copying of data leading to 4 user/kernel space crossings
- Pipes carry byte stream between 2 processes and used for connecting output from 1 process to input of another
- Message queues carry messages between processes and use SystemV or POSIX
- Sockets pass message buffers from user to kernel buffer to user
Shared memory IPC the OS establishes a shared channel between processes which are physical pages mapping into virtual address space and VA(P1) and VA(P2) map to same physical address
- However VA(P1) doesn’t need to be equal to VA(P2) and physical memory doesn’t have to be contiguous
- Only system calls are for setup and data copies reduced but you need to explicitly synchronize, define communication, and share buffers responsibly
For Message IPC cpu cycles are spent copying data to/from port ; for Shared Memory IPC cpu cycles are spent establishing physical to virtual address memory mappings + copying data to channel
- For large data Message IPC takes longer so worthwhile to use Shared Memory even with additional overhead
Shared memory segments is system wide and has limits on count and total segment size
Can synchronize shared memory access via threading or OS supported IPC
Need to make sure synchronization data structures are shared

// ...make shm data struct
typedef struct {
    pthread_mutex_t mutex;
    char *data;
} shm_data_struct, *shm_data_struct_t;

// ...create shm segment
seg = shmget(ftok(arg[0], 120), 1024, IPC_CREATE | IPC_EXCL));
shm_address = shmat(seg, (void *) 0, 0);
shm_ptr = (shm_data_struct_t) shm_address;

// ...create and init mutex
pthread_mutexattr_t(&m_attr);
pthread_mutexattr_set_pshared(&m_attr, PTHREAD_PROCESS_SHARED);
pthread_mutex_init(&shm_ptr.mutex, &m_attr);

Segment sizes are dependent on what you want to do
- 1 large segment means u need to manage allocating/freeing memory from segment
- Many small segments means preallocating a pool of segments and controlling access via a queue ; process knows which segment id to get data from by communicating it
- If segment size == data size then can do all in 1 go else need to transfer data one by one and include synchronization and flags header to track progress

P3L4 Synchronization Constructs

Synchronization relates to an instance waiting for another instance to finish
- They could repeatedly check to continue w/ spinlocks, wait for a signal to continue (mutexes, CV’s), and know what waiting hurts performance
Mutexes and CV’s are building blocks of synchronization but are error prone when developing and need to code up multiple readers/writers imperatively
Spinlocks spin instead of sleeping when waiting on a lock
Semaphores easily allow multiple task accesses as they are initialized with a value which states how many tasks can access it → wait decrement if non zero and post increment
Reader writer locks are inbuilt locks which support multiple readers and single writers
- Implementations differ in how to unlock recursive read locks, dynamic priority of readers, and interaction with thread scheduling policies
Synchronization has a lot of components → use monitors which specify all the shared resources, entry procedures, and possible condition variables
- On entry check and lock and on exit unlock and check signals
- More constructs available ike serializers, path expressions, wait free sync, rendezvous points, and barriers and all need underlying hardware support
For spinlock using if/while (lock == busy) spin does not work as multiple threads can access the same entry point at one time → need to use hardware support
- Test and set, read and increment, compare and swap provide atomicity, mutual exclusion, and concurrent instructions are queued
- Test and set will return the original value but set new value to 1 so first thread will be free and other threads will wait
Shared memory multiprocessing either bus based (only 1 request to all of memory) or interconnect based where can send requests specifically to portion of memory
- When writing to memory can use no-write (only write to memory), write-through(write to both cache and memory), and write-back(write later to memory) when dealing with caches
For multiple cpus, can have the same value in cache → how to deal with this on change?
- Non cache coherent platforms use write-invalidate which invalidates the variables new value in software
- Cache coherent platforms use write-update which updates the variables new value in cache in hardware
If using atomics on multi cpu setup then can’t atomically access values in cache due to write invalidate/update work happening so no mutual exclusion
- Must read from direct memory itself with atomics which synchronizes everything but takes longer to read and generates coherence traffic/write-invalidate/update due to safety reasons
Spinlock performance metrics: reduce latency to acquire free lock, reduce waiting time for a spinning lock, reduce contention in bus/network traffic
- Test and set spinlock minimizes latency (atomics), minimizes waiting delay(constantly spinning), but increases contention as needs to fetch value in memory every spin cycle
- Test and test and set spinlock has more latency and delay but worse performance on average due to contention + hitting up memory every time for contention traffic for write invalidate
- Can add a delay in the while loop which reduces contention but worsens delay
  - Fixed delay is simple but unnecessary under low contention so track percieved contention and adjust delay more if more contention and vice versa
Queue lock assigns tickets to spinlocked threads in FIFO order but read_and_increment must be atomic and O(n) space for queue
- More latency but better delay and better contention as orderly additions and unlocking as long as cache coherent (don’t spin on memory references) and elements on diff cache lines (don’t invalidate lines if elements close together)

P3 L5 IO Management

OS I/O management has protocols/interfaces for device IO, dedicated handlers (interrupt/device drivers), and abstracts I/O device details from abstractions
- I/O devices include keyboards, mouse, network cards, disks
Devices can be abstracted to have command, data transfer, and status registers + microcontroller(cpu), device memory, and other hardware specific logic
Devices are linked to the cpu via controllers via PCI(Peripheral Component Interconnect)
- PCI express has more bandwidth, faster, lower access latency, more devices
- For every controller/device, there needs a device driver for device access, management, control, provided by manufacturers for OS and OS standardizes the interface
Devices can be block/disk based (can R/W/access data blocks), character based, or network devices and represented as a device file in the OS
- CPU will access device registers via memory load/store
  - Access via memory mapped IO controlled by base accessed registers or dedicated IO port
Devices can either interrupt or poll to get requests from device to CPU
- Interrupts generated ASAP but have to deal with interrupt handler overhead
- Polling is convenient for OS but delayed event + CPU overhead due to constant poll
2 ways of CPU to device access PIO/Programmed IO or DMA/Direct Memory Access
- PIO requires no hardware support and CPU “programs” the device by accessing the command and data registers so significant cpu overhead here
- DMA will write into command registers but data flow is via a DMA controller which reduces the number of CPU cycles needed but DMA configuration is more complex + data buffer must be completely present in physical memory until transfer completes
  - Smaller transfers PIO > DMA for this reason
The user process will issue a system call to the kernel, the kernel does any data forming relating to the hardware to the driver, the device driver will tell the device to do X hardware operation
Sometimes can access device driver directly and bypass the kernel but need to provide user level driver library
Device operations can be synchronous and the process will block or asynchronous where the process will check and get result or process notified that operation is completed
User processes think about files and the kernel thinks about how to find/access file and the block layer provides the block interface in order to access blocks from the device/hardware
What happens if files are on more than 1 device, some devices work better than others on diff file system implementations, or files not on local device via network → use virtual file system
- File descriptors represent an OS’s view of a file, inodes represent the files “index” and shows all data blocks, permissions, size, etc, dentry’s are cached OS specific file directory entries, and superblocks are file system specific info about the layout
  - On disk, the superblock provides a mapping of inode blocks, data blocks, and free blocks on disck
Ext2 file system layout
Inodes list all disk blocks for a file and can easily read file but file size is limited based on the inode size
- To solve file size problem use indirect pointers and let inodes point to other inodes via single indirect or double indirect blocks but now file accesses slow down as indirect pointers lead to more disk accesses
Can perform optimizations to reduce file access overhead

P3 L6 Virtualization

Virtualization allows multiple operating systems to run on the same physical machine
- Every OS thinks they own their hardware resources and VM consists of the OS + applications + virtual resources
- Allows us to consolidate (place multiple OS’s in 1 VM) saving costs, easy migrations allowing more availability and reliability, and are isolated to the VM increasing security and making debugging easier
VMs supported by a Virtual Machine Monitor which
- Allows almost identical environment vs original, minor decrease in spead, and VMM has control over system resources
2 types of virtualization models: Bare metal/Hypervisor or Hosted
- Bare metal manages all hardware resources and VM execution and has privileged service VM to deal with device drivers/configuration management
- Hosted virtualization the Host OS has a VMM module that owns all the hardware and contains all the device drivers and has VM’s and native applications combined
Hardware has protection levels 0 to x where 0 is most privileged operations(OS/hypervisor) and x is least privileged (apps) + 2 protection modes root (all privileges) and non root (limited privileges)
For processor virtualization, guest instructions get executed directly by hardware and only during privileged operations do we trap to the hypervisor
- Hypervisor determines if access was illegal (terminate VM) or legal and emulates behavior guest OS was expecting from hardware → trap and emulate
- However for x86 architectures there are privileged operations (enable/disabling interrupts) that do not trap to hypervisor and fail silently and both OS and hypervisor unaware
  - Use binary translation instead where we rewrite the binary to not execute the specific instructions above → how VMWare was made
    - Binary translation is dynamic here as cannot request companies to change their products invidually so for every block of code, see if we need to translate to new instructions and do so else run normally ; cache translated blocks helps amortizing translation costs
- Another approach is paravirtualization where the guest VMs know they are being virtualized and code is modified such they make system calls to hypervisor (hypercalls) which traps to VMM and does operation there
Memory VM virtualization now has virtual, physical, and machine addresses with MMU + TLB still used
- Option 1 is to use VA → PA guest OS page table and PA → MA hypervisor page table but too expensive
  - MMU will translate both page tables and TLB will only manage virtual to physical addresses
- Option 2 is to use VA ⇒ PA guest OS page table and VA → MA hypervisor shadow page table
  - MMU only translates VA → MA and TLB only manages virtual to physical addresses
- Paravirtualized Memory removes requirement of guest contiguous physical memory starting at 0, explicitly registers page tables with hypervisor so no dual page table system ie VA ⇒ MA mappings, and can batch page table updates for a single hypercall to reduce VM exits
CPU’s/Memory have less diversity due to Instruction Set Architecture standardization but devices have high diversity and lack of standardization
- Passthrough model/VMM bypass makes device driver bypass hypervisor and connects to device driver directly but very hard to share device, must have exact device since no hypervisor virtualization, amd VM migration harder
- Hypervisor Direct Model the VMM intercepts all device accesses and tries to emulate the device operation as needed which helps migration and sharing, device specifics and decoupled but adds in more latency on every device access and device driver complexity in hypervisor
- Split Device Driver Model makes guest VMs with FE driver hit up Service VM with backend driver which eliminates elimination overhead and better management of shared devices with shared VM
Hardware companies realized how important virtualization is and started implementing those features themselves

P4 L1 Remote Procedure Calls

Reason for RPC is to simplify IPC by removing a lot of repeated steps (socket initialization, modifying buffers, and sending over low level protocol)
- Higher level interface for data movement/communication, easier error handling, and hide cross machine interaction complexity
Some requirements for RPC are that they must follow client/server patterns, must have a synchronous procedure call interface, type checking, accoutn for cross machine datatype conversions, and provided a higher level protocol that allows different access control, fault tolerance, transport protocols, …
RPC Flow:
RPC allows any machine any language for communication but we still need an Interface Definition Language/IDL to know what types and args needed
- IDL defines procedure name, arguments, return values, and version
- Pointers make no sense to RPC as this is caller address space specific so either define no pointers or serialize pointer data
Marshaling encodes rpc method, arguments, and packs them all into a buffer in the client to send while unmarshaling decodes this for the server to execute
Binding makes available a registry where we can search for service names to find service and contact details and can be distributed (any can register) or machine specific (only for same machine services)
For errors RPC provides error notification which is a catch all and options are to timeout and retry
Sun RPC library created by Sun Microsystems for UNIX supporting per machine registry, XDR IDL, serialized pointers, and timeout and retries on failure
XDR gets compiled into template code where client and server share the same datatypes
- Must pass in a flag to make the compilation thread safe to make multiple RPC calls
Sun RPC Registry is a portmapper where we query it with rpcinfo -p using either tcp/udp + Binding used with help of template files
Java RMI where IDL is Java and client stub communicates with server skeleton

P4 L2 Distributed File Systems

Distributed file systems are accessed with well defined interface (Virtual File System), focused on consistent state (tracking file system), and can be implemented with mixed distribution models (replicated, partitioned, peer-like)
Virtual File System abstracts away any specific file accesses and can have multiple local or remote file systems
- Can have client/server on different machines where file server can be both replicated and partitioned or files stored and served from all machines
3 ways to access a remote file
- Can Upload/Download where you download file first, perform modifications on client, and send back to server allowing local reads/writes clientside but must download entire file and server has no control over file
- Can access file remotely by sending requests to server so access is centralized on server but every file operation goes over the network and server has more requests to deal with limiting scalability
- Can store parts of file (blocks) on client to perform operations on and force clients to interact with server so server load reduced and server knows what client is doing/permissions but makes server interaction more complex
Can keep a file server stateless or stateful
- Stateless no caching/consistency management and more bits transferred due to self contained requests but minimal cpu/memory needed and just restart on failure
- Stateful keeps the client state and tracks accesses which allows locking, caching, incremental operations but need to checkpoint and have recovery protocols on failure and need to maintain state and consistency
Need to cache file state on file system similar to write update/write invalidate but perform caching operation not on write but on demand/periodically/on open/dependent on file system
Consistency is a problem when CRUD operations happen on distributed vs single node file systems so come up with some semantics
- UNIX semantics every write visible immediately
- Session semantics write back on close() and update on open() but won’t be enough
- Periodic Updates write back periodically and server invalidates cached data periodically too and use flush/sync to help with this
- Immutable Files never modify these files and only create new ones
- Transactions make all changes to file system atomic
For files vs directories we should examine their access patterns and if applicable choose different policies for each
Replication allows better fault tolerance and availability but writes become more complex as must write to all machines or propagate writes + on failure replicas need to reconciliate
Partitioning allows better scalability as less load on multiple servers and writes are easier but on failure we lose a portion of data and bad partition leads to hot spots so combine with replication
Network File System Architecture:
NFS3 is stateless NFS4 is stateful and is session based + periodic updates and can delegate to client to period of time if needed + lease based/reader writer locking available
Sprite File System researched Distributed File System design requirements by using trace data on usage/file access

P4 L3 Distributed Shared Memory

Managing distributed shared memory involves deciding their placement (placing memory pages close to relevant processes), deciding their migration (when to copy pages from remote to local), and deciding sharing rules (making sure memory operations are ordered)
- In Distributed File Servers how do we own and manage state of files and provide consistent service of file accesses
In Peer Distributed applications every node owns its own state and provides services and every node is a peer - “peer to peer” applications though do the control and management plane tasks with all nodes instead of having dedicated configuration nodes to do this
In Distributed Shared Memory, every node owns its own memory state and manages reads/writes from any node allowing better scaling and cheaper costs are you just need to add more nodes as system scales but slower to call remote memory over local memory
- Can implement in Hardware with Network Interface Card/NIC which tranlsates remote memory accesses to messages, manages memory, supports atomics but very expensive so implement with software
- Can communicate DSM with cache line but thats too big and variables are too small
  - If implemented at the OS level can communicate pages and if implemented by runtime that can recognize local vs shared objects
  - Be aware of false sharing → if 2 items are on same page but accessed independently by 2 different processors then coherence and sharing mechanisms will take place even tho no concurrency
Need to coordinate multiple readers and writers for DSM
- Can migrate data if requested from another node but data move overhead or replicate memory across multiple nodes but need to make data consistent
  - Write invalidate and write update for SMP caching is too expensive so push vs pull modifications
DSM needs to intercept requests to access state or coherence messages but make sure not to intercept for local accesses since overhead of accessing remote memory + DSM logic
- MMU helps a lot here and we only trap into the OS and pass request to DSM if MMU finds invalid access/mapping or if we are doing a cache coherence operation
Consistency model is agreement between memory and software to determine access ordering and visibility of updates
- Strict Consistency all updates are visible immediately but no guarantees unless lock and synchronize but latency and message reordering loss make impossible to guarantee
- Sequencial Consistency interleaves operations but all processes see the same interleaving/sequence of steps
- Causal Consistency preserve operations from the same processor in order
- Weak Consistency processors sync and make operations available before the time period of the sync

P4 L4 Datacenter Technologies

Internet services incldue presentation (static content), business logic (dynamic content), and database and can be done open source on 1 process or can use IPC + middleware
When requests come to frontend can use boss/worker (FE distributes them to nodes), all equal (all homogeneous nodes execute any possible step in request), specialized (heterogeneous) nodes where nodes execute specific step
Use cloud based infrastructure in general over local hardware due to sudden increase/decrease in customers where much easier to use cloud over setting up in house deployment and provisioning
- The ideal cloud is on demand that scales up and down without dropping requests, has fine grained usage pricing, professionally managed and hosted, and have API based access
- Vision of cloud computing was to use it as a utility like a phone but obviously there is lots to configure here
Cloud provider offers infrastructure/software/services, with web/library, command line apis, with spot/reservation/marketplace based billing based on instance specs
- Hardware cost is amortized by customer usage and demand averages out due to resource variation needs
- Public cloud exposes services to third party customers, private uses internally, hybrid uses internally but public in case of excess demand or failure, and community is owned by users
Throughout the service stack you can choose to manage none or all of the components or something in between
Cloud is so big, people are interested in performing big data operations on them

Final Practice Question

P3L1

How does scheduling work? What are the basic steps and datastructures involved in scheduling a thread on the CPU?
1. Run to completion scheduling if know everything beforehand or premptive scheduling where OS interrupts process
2. Multi level feedback queue, 2 run queues for O(1) scheduler, red black tree for completely fair scheduler
What are the overheads associated with scheduling? Do you understand the tradeoffs associated with the frequency of preemption and scheduling/what types of workloads benefit from frequent vs. infrequent intervention of the scheduler (short vs. long timeslices)?
1. Context switches is overhead + IO events waiting on thing and shorter timeslices better for IO and longer timeslices better for cpu intensive tasks
Can you work through a scenario describing some workload mix (few threads, their compute and I/O phases) and for a given scheduling discipline compute various metrics like average time to completion, system throughput, wait time of the tasks…
1. Yep find formulas
Do you understand the motivation behind the multi-level feedback queue, why different queues have different timeslices, how do threads move between these queues… Can you contrast this with the O(1) scheduler? Do you understand what were the problems with the O(1) scheduler which led to the CFS?
1. MLFQ most prioritized is top level shorter timeslices which are IO bound to maximize IO operations and they stay there since relinquish cpu fast else move down list so less priority but more time to execute for CPU intensive tasks
2. O(1) scheduler has priorities where 0 highest priority highest timeslice and X lowest priority lowest timeslice and the more one sleeps decrease priority (IO) and the more compute intensive taks lower priority (CPU)
3. 2 run queues finished needs to wait on active which causes jitter and reduces fairness leading to CFS
Thinking about Fedorova’s paper on scheduling for chip multi processors, what’s the goal of the scheduler she’s arguing for? What are some performance counters that can be useful in identifying the workload properties (compute vs. memory bound) and the ability of the scheduler to maximize the system throughput.
1. Scheduler intention was a mix of cpu and memory intensive tasks to limit contentuion on the processor pipeline and utilize the cpu and memory to the best it can
2. Track performance with hardware counters/cycles per instruction P3L2
How does the OS map the memory allocated to a process to the underlying physical memory? What happens when a process tries to access a page not present in physical memory? What happens when a process tries to access a page that hasn’t been allocated to it? What happens when a process tries to modify a page that’s write protected/how does COW work?
1. Does segmentation + paging from virtual to physical memory using VPN → PPN in page table + offset
2. Page fault and if not in physical memory then terminate, if not allocated then memory allocator determines which physical address to allocate too, page fault and terminate if writing to a write protect page, COW read only until write then clone respective pages up to parent for new process memory
How do we deal with the fact that processes address more memory than physically available? What’s demand paging? How does page replacement work?
1. Can use multi level page tables to reduce page table size or inverted page table + hashing to make size roughly equivalent to physical memory
2. Demand paging keeps adding and swapping pages on demand on emmory access fault → acquire page and LRU/LFU/etc page replacement algorithms
How does address translation work? What’s the role of the TLB?
1. VPN maps to PPN in page table and then combine with offset bits to find physical address in DRAM
2. TLB is cache of VA to PA in order to reduce memory access latency
Do you understand the relationships between the size of an address, the size of the address space, the size of a page, the size of the page table…
1. Page table size = (virtual address space size/page size) * size of page table entry
Do you understand the benefits of hierarchical page tables? For a given address format, can you workout the sizes of the page table structures in different layers?
1. Page table gets huge at 64+ bit architectures so multi level page tables to reduce space but N level page table is N memory accesses P3L3
For processes to share memory, what does the OS need to do? Do they use the same virtual addresses to access the same memory?
1. Need to establish shared VA to PA memory mappings and no VA’s could be diff between processes and still map to same PA
For processes to communicate using a shared memory-based communication channel, do they still have to copy data from one location to another? What are the costs associated with copying vs. (re-/m)mapping? What are the tradeoffs between message-based vs. shared-memory-based communication?
1. Only data copies for shared memory is to and from the channel vs socket/mq where data copying goes into the call, then over the network, then copied again from call but have to set shared memory channel up
What are different ways you can implement synchronization between different processes (think what kids of options you had in Project 3).
1. Threading, mq, sockets, pipes etc P3L4
To implement a synchronization mechanism, at the lowest level you need to rely on a hardware atomic instruction. Why? What are some examples?
1. Race conditions come down to the hardware level executed in 1 step so need hardware atomic to set in place test and set/compare and swao
Why are spinlocks useful? Would you use a spinlock in every place where you’re currently using a mutex?
1. Wait on response instead of sleep/wakeup which has context switch overheads and no if single processor or waiting long time on IO/other operation use sleeplock and let another process take oevr
Do you understand why is it useful to have more powerful synchronization constructs, like reader-writer locks or monitors? What about them makes them more powerful than using spinlocks, or mutexes and condition variables?
1. Building synchronization mechanisms from scratch is hard and can be buggy ; higher level synchronization constructs help with development process and less bugs
Can you work through the evolution of the spinlock implementations described in the Anderson paper, from basic test-and-set to the queuing lock? Do you understand what issue with an earlier implementation is addressed with a subsequent spinlock implementation?
1. test and set realize that need to read from direct memory since SMP cache coherence not atomic → test and test and set reads from invalid cache first but has bad cache invalidation leading to worse contention → can add delays in while loop to reduce contention but increase delay → queuing lock reduces contention but o(n) queue and needs to have read + increment operation atomic P3L5
What are the steps in sending a command to a device (say packet, or file block)? What are the steps in receiving something from a device? What are the basic differences in using programmed I/O vs. DMA support?
1. Write command then get data in and send over packets and read from it and PIO vs DMA is that PIO is direct and cpu involved the whle time reading/writing from registers but DMA only write command initially and DMA on its own gets the in memory data and writes/reads from device as needed
For block storage devices, do you understand the basic virtual file system stack, the purpose of the different entities? Do you understand the relationship between the various data structures (block sizes, addressing scheme, etc.) and the total size of the files or the file system that can be supported on a system?
1. Think in terms of blocks and inodes and data blocks on the kernel level
For the virtual file system stack, we mention several optimizations that can reduce the overheads associated with accessing the physical device. Do you understand how each of these optimizations changes how or how much we need to access the device?
1. Caching, IO scheduling, prefetching, journaling/logging P3L6
What is virtualization? What’s the history behind it? What’s hosted vs. bare-metal virtualization? What’s paravirtualization, why is it useful?
1. Virtualization allows multiple OS/applications to run on the same machine allowing cost saving, max resource utilization, better isolation for a small performance penalty due to virtualizing
2. Bare metal has hypervisor which is source of truth for hardware/VM execution + service VM to deal with drivers vs Hosted has dedicated VMM hardware module allowing regular applications to run too
3. Paravirtualization VMs know they are being virtualized so can write code to develop off this and optimize as needed + code is modified to trap to hypervisor and execute as needed
What were the problems with virtualizing x86? How does protection of x86 used to work and how does it work now? How were/are the virtualization problems on x86 fixed?
1. Privileged operations need to trap to hypervisor and either terminate VM if instruction illegal or trap and emulate
2. Some architectures in x86 have privileged operations that don’t trap to hypervisor and fail silently so use binary translation where u rwerite the binary to not execute the specific instructions and do something else (invention of VMWare)
How does device virtualization work? What a passthrough vs. a split-device model?
1. Now we have VA ⇒ PA ⇒ MA due to hypervisor virtualizing hardware
2. Devices have high diversity and no standardization compared to CPU/Memory so need to virtualize device
  1. Passthrough bypass hypervisor for device but no device sharing and must have exact type of device leading to harder migrations
  2. Hypervisor direct VMM intercepts all device accesses and emulates device operation which allows sharing but increased latency due to interruption + driver complexity in hypervisor
  3. Split device driver model VM FE driver hits up Service VM BE driver which only works for paravirtualized VMs but no emulation overhead and better shared device management P4L1
What’s the motivation for RPC? What are the various design points that have to be sorted out in implementing an RPC runtime (e.g., binding process, failure semantics, interface specification… )? What are some of the options and associated tradeoffs?
1. Instead of sending raw bytes over have a typed language IDL that generates code stubs which removes repeated steps
2. Must follow client/server patterns, must have a synchronous procedure call interface, type checking, accoutn for cross machine datatype conversions, and provided a higher level protocol that allows different access control, fault tolerance, transport protocol
3. More complicated to actually implement the underlying rpc framework but alr given + no pointers and must serialize data
What’s specifically done in Sun RPC for these design points – you should easily understand this from your project?
1. Client server procedure calls, has IDL called XDR, server registry, serialized pointers, timeout, retries on failure
What’s marshalling/unmarschaling? How does an RPC runtime serialize and deserialize complex variable size data structures? What’s specifically done in Sun RPC/XDR?
1. Encode and decoding raw data into actual types intermediary is buffer + for complex data structures done recursively P4L2
What are some of the design options in implementing a distributed service? What are the tradeoffs associated with a stateless vs. stateful design? What are the tradeoffs (benefits and costs) associated with using techniques such as caching, replication, partitioning, in the implementation of a distributed service (think distributed file service).
1. Stateless vs stateful, physical vs virtual file system, types of caching/caching at all, replication, partition, peer to peer
2. Stateless no caching/consistency management + more bytes transferred but minimal setup and overhead vs stateful has caching and consistency management improving performance but deal with dys system
The Sprite caching paper motivates its design based on empirical data about how users access and share files. Do you understand how the empirical data translated in specific design decisions? Do you understand what type of data structures were needed at the servers’ and at the clients’ side to support the operation of the Sprite system (i.e., what kind of information did they need to keep track of, what kids of fields did they need to include for their per-file/per-client/per-server data structures).
1. Most file access is sequential so optimize for sequential caching allowed vs no caching with concurrent access
2. Write back every 30 seconds allows updating cache efficiently without overloading but short enough to minimize data loss
3. Don’t cache directories since they change consistently affecting consistency
4. Minimal file opens so can go through server and manage P4L3
When sharing state, what are the tradeoffs associated with the sharing granularity?
1. Hardware DSM needs interconnect and NIC card which manages all memory atomics but expensive
2. Software DSM is much cheaper and can share pages if implemented at OS level and objects if implemented by runtime
3. Need to make sure to avoid false sharing if 2 items on same page but accessed independently by 2 processors
For distributed state management systems (think distributed shared memory) what are the basic mechanisms needed to maintain consistence – e.g., do you why is it useful to use ‘home nodes’, why do we differentiate between a global index structure to find the home nodes and local index structures used by the home nodes to track information about the portion of the state they are responsible for.
1. Need to enable cache coherency in certain scenarios + local caches + home nodes which manage their own shared memory
2. Need to add some sort of locking + push invalidations or pull modifications
3. Glocal index structure needs to be accessible to all and local index structure to track shared state is done only in that home node → encapsulation
Do you have some ideas how would you go about implementing a distributed shared memory system?
1. yes
What’s a consistency model? What are the different guarantees that change in the different models we mentioned – strict, sequential, causal, weak… Can you work through a hypothetical execution example and determine whether the behavior is consistent with respect to a particular consistency model?
1. Determines when data shows up after one node does a modification
2. Strict shows up immediately, sequential all processes see same sequence of steps, causal any operations from same processor in order and causally related writes are ordered, weak checkpointing P4L4
When managing large-scale distributed systems and services, what are the pros and cons with adopting a homogeneous vs. a heterogeneous design?
1. Homogenous is flexible and easier to implement but cold caches heterogenous hard to setup and maintain but hotter caches if doing the same step
Do you understand the history and motivation behind cloud computing, and basic models of cloud offerings? Do you understand some of the enabling technologies that make cloud offerings broadly useful?
1. On prem vs EC2 vs Google App Engine vs SAAS more higher level you go in the cloud the less components you manage
Do you understand what about the cloud scales make it practical? Do you understand what about the cloud scales make failures unavoidable?
1. Cloud is so big something is going to happen and must have rigid error handling in place
2. If your demand goes up then cloud can scale easier vs on prem physical server

Contents

P1L1/2: Introduction to Operating Systems

P2L1: Processes and Process Management

P2L2: Threads and Concurrency

P2L3: Threads Case Study: PThreads

P2L4: Thread Design Considerations

P2L5: Thread Performance Considerations

Midterm Practice Questions

Midterm Formulas

P3L1 Scheduling

P3L2 Memory Management

P3L3 Inter Process Communication

P3L4 Synchronization Constructs

P3 L5 IO Management

P3 L6 Virtualization

P4 L1 Remote Procedure Calls

P4 L2 Distributed File Systems

P4 L3 Distributed Shared Memory

P4 L4 Datacenter Technologies

Final Practice Question

Papers