I need you to help me study by analysing the lecture slides I give you, and then forming…
- User
I need you to help me study by analysing the lecture slides I give you, and then forming a study plan based on the course material, as well as the final exam template I give you. In the next prompt, I will feed you lecture slides starting with chapter 6, all the way to 15. Do not respond anything until at the end of all slides, I specifically ask you to start working based on the data. Capisce?
- Assistant
Understood. Please provide the lecture slides, and I will begin formulating a study plan once you've presented all the necessary material and given the go-ahead.
- User
Chapter 6 & 7 – Process Synchronization Fall 2023 Overview • Race Conditions • The Critical-Section Problem • Peterson's Solution • Hardware Solutions • Mutex Locks • Semaphores Chapter 6 & 7 – Process Synchronization Race Conditions • Processes can run concurrently • Processes can be interrupted at any time • Hardware interrupts • Software interrupts (traps) • Including timer interrupts for exceeding time quantum • Two or more processes may read data that is in an inconsistent state Chapter 6 & 7 – Process Synchronization Race Conditions • Example • We have seen that a producer and consumer can share a pointer to the next slot • count++ could be implemented as • register1 = count register1 = register1 + 1 count = register1 • count-- could be implemented as • register2 = count register2 = register2 - 1 count = register2 Chapter 6 & 7 – Process Synchronization Race Conditions • Example • Consider the following order of operations when count == 5 • What is the value of count? Chapter 6 & 7 – Process Synchronization Time Who Instruction Value T0 Producer register1 = count register1 = 5 T1 Producer register1 = register1 + 1 register1 = 6 T2 Consumer register2 = count register2 = 5 T3 Consumer register2 = register2 – 1 register2 = 4 T4 Producer count = register1 count = 6 T5 Consumer count = register2 count = 4 Race Conditions • Example • When fork() is called, how does the operating system pick the next pid? • Unless there is a mechanism to prevent P0 and P1 from accessing the variable next_available_pid the same pid could be assigned to two different processes! Chapter 6 & 7 – Process Synchronization Race Conditions • Example • Suppose a bank account has 600 comes from two ATMs Chapter 6 & 7 – Process Synchronization ATM 1 ATM 2 Read balance: 600 Context Switch Read balance: 600 Update balance to -400) Context Switch Context Switch Update balance to -200) … … Race Conditions • Example • What if the value of the balance was read and then used later in the update? Chapter 6 & 7 – Process Synchronization ATM 1 ATM 2 Read balance: 600 Context Switch Read balance: 600 Update balance to 600 (Balance is now 1000-400) … … Race Conditions • Example: Multiple processes require multiple resources • The "Dining Philosopher's Problem" • Five philosophers sit at a table with 5 chopsticks • A philosopher will either think or eat • If the philosopher thinks, the philosopher leaves two chopsticks available • If the philosopher eats, the philosopher requires two chopsticks • High potential for deadlock and starvation (literally!) Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • A critical section could be any section of code that uses shared data • Process may be • changing common variables • updating tables • writing files • etc. • Read-only data can be safely shared (e.g. a lookup table, opening a file for reading only) Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • General structure of a process with a critical section: • Entry section – Request permission to enter the critical section • Critical section • Exit section – Relinquish control of the critical section • Remainder section – (non-critical section parts) Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • Suppose Process A and Process B both request access to their critical section Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • "Solutions" that don't work • Disallow interrupts (nonpreemptive). This is impractical. • Temporarily disable interrupts. Re-enable when you are done. • What if a process spends too much in the critical section? Processes could starve! • Too much control given to the developers/users • How do you deal with multiple CPUs? Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • "Solutions" that don't work • Use a shared flag to indicate which process can enter their critical section • E.g. Consider Process i and Process j. The only valid values for turn is i or j • The code for Process i: • while (true){ while (turn == j); /* critical section / turn = j; / remainder section / } Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • "Solutions" that don't work • Why a shared flag does not work • What if both process observe that turn is equal to a value other than their own? • What if one of the processes gets stuck in its critical section or encounters an issue that prevents it from reaching the turn = j;? • This solution allows entering critical sections by alternating only Chapter 6 & 7 – Process Synchronization The Critical-Section Problem • A solution must satisfy three conditions • Mutual exclusion – If process Pi is executing in its critical section, then no other processes can be executing in their critical sections • Progress – If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the process that will enter the critical section next cannot be postponed indefinitely. (The "no deadlock" rule) • Bounded waiting – A bound must exist on the number of times that other processes are allowed to enter their critical sections (the "no starvation" rule) Chapter 6 & 7 – Process Synchronization Peterson's Solution • Developed in 1981 but no longer applicable on modern architectures • Restricted to two, single-threaded processes on a single-core architecture • Some modern architectures re-order instructions for efficiency • However, it is still an illustrative solution Chapter 6 & 7 – Process Synchronization Peterson's Solution • The two processes share two variables: • int turn; boolean flag[2]; • The variable turn indicates whose turn it is to enter the critical section • The flag array is used to indicate if a process is ready to enter the critical section. • flag[i] = true implies that process Pi is ready Chapter 6 & 7 – Process Synchronization Peterson's Solution • The code for Pi • while (true){ flag[i] = true; turn = j; while (flag[j] && turn == j) ; / critical section / flag[i] = false; / remainder section / } • If both processes were in their critical sections, then flag[i] == flag[j] == true • Mutual Exclusion Achieved! Chapter 6 & 7 – Process Synchronization Peterson's Solution • If Pi is blocking while Pj is in its critical section, as soon as Pj finishes, Pi can immediately continue • Progress Achieved • Pi must wait only as long as Pj is in its critical section. The next process to enter its critical section is Pi • Bounded Waiting Achieved Chapter 6 & 7 – Process Synchronization Hardware Solutions • Modern computer architectures provide tools to protect data • Memory barrier instructions – Instructions to force memory updates to all processors ensuring that all threads use the correct data • Hardware instructions – Instructions guaranteed to function atomically (uninterruptible) • Atomic variables – Variables with operations that use only atomic hardware instructions • Applicable to kernel and assembly language programmers Chapter 6 & 7 – Process Synchronization Mutex Locks • A "user-friendly" approach built by kernel developers for application developers to provide mutual exclusion • Mutex lock – A Boolean variable indicating if a lock is available or not • Use acquire() to acquire the lock and enter the critical section • While the lock is held, no other process can hold the same lock • Use release() to release the lock and exit the critical section • (Both acquire() and release() are implemented using atomic hardware instructions. So they can be trusted) Chapter 6 & 7 – Process Synchronization Mutex Locks • acquire() { while (!available) ; / busy wait / available = false; } release(){ available = true; } • while (true){ acquire() / critical section / release() / remainder section / } Chapter 6 & 7 – Process Synchronization Mutex Locks • This solution requires busy waiting – Any process that wishes to enter its critical section must loop continuously while it waits. This wastes CPU cycles • Therefore, this is known as a spin-lock (It spins while it waits for a lock to become available) • Spin-locks can be acceptable or even advantageous • A call to acquire() does not immediately force a context switch • If the spin-lock is short, a thread can spin on one core while another core completes the critical section Chapter 6 & 7 – Process Synchronization Semaphores • A more sophisticated mutex lock • Binary semaphore – integer value can range only between 0 and 1 (Same as a mutex lock) • Counting semaphore – integer value can range over an unrestricted domain • Can be used to control access to a given resource consisting of a finite number of instances (not just one). For example, initialize the semaphore to N when N processes can be in the critical section simultaneously Chapter 6 & 7 – Process Synchronization Semaphores • Set S to the number of resources available • Use wait(S) to obtain a resource if one is available • Use signal(S) to release a resource • If the value of S reaches 0, then no resources are available, and the call wait(S) will block until one becomes available • (Again, both wait() and signal() are implemented using atomic hardware instructions. So they can be trusted) Chapter 6 & 7 – Process Synchronization Semaphores • wait(S) { while (S <= 0) ; / busy wait / S--; } signal(S){ S++; } Chapter 6 & 7 – Process Synchronization Semaphores • Solution to the critical section problem: Create a semaphore initialized to 1 (a Mutex) • wait(mutex); / critical section / signal(mutex); • Force synchronization: Suppose S1 in P1 must execute before S2 in P2. Initialize synch to 0 • / S1 / signal(synch); • wait(synch); / S2 */ Chapter 6 & 7 – Process Synchronization Semaphores • Semaphores without busy waiting • In addition to an integer value, also maintain a waiting queue of processes • Instead of using a spin-lock, place the process into a waiting queue and put it to sleep() • When a resource is released, place a process in the waiting queue in the ready queue and use wakeup() Chapter 6 & 7 – Process Synchronization Semaphores • typedef struct { int value; struct process *list; } semaphore; Chapter 6 & 7 – Process Synchronization Semaphores • wait(semaphore *S) { S->value--; if (S->value < 0) { add this process to S->list; sleep(); } } • signal(semaphore *S) { S->value++; if (S->value <= 0) { remove a process P from S->list; wakeup(P); } } Chapter 6 & 7 – Process Synchronization Semaphores • Note this solution allows value to be negative • The negative value can indicate the number of processes waiting on that semaphore Chapter 6 & 7 – Process Synchronization Semaphores • Watch out for common mistakes with semaphores • Mixing up signal() and wait() (e.g. Using signal() before a critical section and wait() after a critical section) • Calling wait() twice (e.g. Using wait() before a critical section and wait() after a critical section) • Forgetting to call either signal() or wait() Chapter 6 & 7 – Process Synchronization Examples • Binary semaphores for threads in Linux • pthread_mutex_t lock • pthread_mutex_init(&lock) • pthread_mutex_lock(&lock) • pthread_mutex_unlock(&lock) • pthread_mutex_destroy(&lock); Chapter 6 & 7 – Process Synchronization Examples • #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <pthread.h> pthread_mutex_t lock; void *thread_prints_msg(void *msg) { pthread_mutex_lock(&lock); // ENTRY printf(" ENTERING CRITICAL SECTION...\n"); printf("From thread_prints_msg: %s\n", (char *) msg); printf(" LEAVING CRITICAL SECTION...\n"); pthread_mutex_unlock(&lock); // EXIT return 0; } Chapter 6 & 7 – Process Synchronization Examples • int main() { pthread_t thread_1; if (pthread_mutex_init(&lock, NULL) != 0) { printf("\n mutex init has failed\n"); return 1; } printf("From main: Going to create Thread...\n\n"); pthread_create(&thread_1, NULL, thread_prints_msg, "Hello World"); pthread_join(thread_1, NULL); printf("\nthread terminates...\n"); pthread_mutex_destroy(&lock); return 0; } Chapter 6 & 7 – Process Synchronization Examples • Counting semaphores for Linux • #include <semaphore.h> • sem_t S • sem_init(sem_t *sem, int pshared, unsigned int value); • sem_wait(sem_t *sem); • sem_post(sem_t sem); • sem_destroy(sem_t mutex); Chapter 6 & 7 – Process Synchronization Examples • #include <stdio.h> #include <pthread.h> #include <semaphore.h> #include <unistd.h> sem_t mutex; void thread(void arg){ sem_wait(&mutex); //wait printf("\nEntered..\n"); sleep(4); //critical section printf("\nJust Exiting...\n"); sem_post(&mutex); //signal } Chapter 6 & 7 – Process Synchronization Examples • int main(){ sem_init(&mutex, 0, 1); pthread_t t1,t2; pthread_create(&t1,NULL,thread,NULL); sleep(2); pthread_create(&t2,NULL,thread,NULL); pthread_join(t1,NULL); pthread_join(t2,NULL); sem_destroy(&mutex); return 0; } Chapter 6 & 7 – Process Synchronization
Chapter 8 - Deadlocks Fall 2023 Overview • System Model • Deadlock Characterization • Methods for Handling Deadlocks • Deadlock Prevention • Deadlock Avoidance • Deadlock Detection • Recovery from Deadlock Chapter 8 - Deadlocks System Model • Any system has a set of resources denoted R1, R2, … Rn • These could be CPU cycles, memory space, I/O devices, mutex locks, semaphores • Each resource Ri has 1 or more instances • E.g. 4 CPUs, 2 Network interfaces, Semaphore value set to 5, etc. • Each process or thread that requests a resources follows these steps: • Request • Use • Release Chapter 8 - Deadlocks System Model • For example, consider a traffic jam Chapter 8 - Deadlocks System Model • For example, return to the Dining Philosopher's problem • Suppose all five philosophers pick up their left chopstick. None of the philosophers can pick up their right chopstick. Some potential solutions: • Allow only 4 philosophers or less at the table • Allow a philosopher to pick up both chopsticks if and only if both are available • Odd numbered philosophers pick up their left chopstick, then the right. Even numbered philosophers pick up the right chopstick, then the left. Chapter 8 - Deadlocks System Model • For example, consider the "Sidewalk Shuffle". This is a special case known as livelock. There is no blocking but there is no progress either. Chapter 8 - Deadlocks System Model • For example, consider two threads with two semaphores • T1: • wait(s1) wait(s2) • T2: • wait(s2) wait(s1) Chapter 8 - Deadlocks Deadlock Characterization • A deadlock occurs under all the following four conditions simultaneously • Mutual Exclusion – only one thread at a time can use a resource • Hold and Wait – a thread holding at least one resource is waiting to acquire additional resources held by other threads • No preemption – a resource can be released only voluntarily by the thread holding it, after that thread has completed its task • Circular wait – Thread T0 waits on a resource held by T1, T1 waits on a resource held by T2, …, Tn waits on a resource held by T0 Chapter 8 - Deadlocks Deadlock Characterization • Identifying circular wait with resource allocation graphs • Consider two types of vertices • Threads – denoted T = {T1, T2, …, Tn} • Resources – denoted R = {R1, R2, …, Rm} • Two types of edges • Request edge – A directed edge Ti → Rj ("wants to hold") • Assignment edge – A directed edge Rj → Ti ("is holding") Chapter 8 - Deadlocks Deadlock Characterization • Identifying circular wait with resource allocation graphs • One instance of R1 • Two instances of R2 • One instance of R3 • Three instance of R4 • T1 holds one instance of R2 and is waiting for an instance of R1 • T2 holds one instance of R1, one instance of R2, and is waiting for an instance of R3 • T3 holds one instance of R3 Chapter 8 - Deadlocks Deadlock Characterization • Identifying circular wait with resource allocation graphs Chapter 8 - Deadlocks Deadlock Characterization • Identifying circular wait with resource allocation graphs • If a graph does not contain cycles, then we do not have deadlock • If a graph does contain cycles, we may have deadlock Chapter 8 - Deadlocks Handling Deadlocks • Four options • Ignore the deadlock – Force application developers to ensure deadlock does not occur. For reasons of efficiency, this is the most common approach by most operating systems. • Deadlock Prevention – Ensure one of the four characteristics of deadlock does not occur. This typically underutilizes system resources. • Deadlock Avoidance – Declaring all resources that may be required before starting. Force threads to wait if there is a potential for overlap. Very inefficient. • Deadlock Detection – Periodically check to see if there is a deadlock and recover appropriately. Common in relational database management systems. Chapter 8 - Deadlocks Deadlock Prevention • Ensure one of the four characteristics of deadlock does not occur • Mutual Exclusion – Some resources are just intrinsically unshareable. Preventing mutual exclusion is just not feasible • Hold and Wait – Force a thread to hold all its resources before it can start. Most resources will be held for no reason. Popular resources will create starvation. • No preemption – If a resource cannot be secured, voluntarily release all existing resources and restart. Only feasible if state can be saved such as CPU registers and database transactions • Circular wait – Enforce an increasing order on all resources for all threads. It's up to the application developer to obey the order. E.g. R1 then R2. Never R2 then R1 Chapter 8 - Deadlocks Deadlock Avoidance • Resource Allocation Graphs – Do not allow any thread to enter the graph if it will create a cycle • E.g. T2 must wait until T1 finishes because introducing it could create a cycle Chapter 8 - Deadlocks Deadlock Avoidance • Deadlock Trajectory Diagram – Consider two Processes that require access to two resources Chapter 8 - Deadlocks Deadlock Avoidance • Deadlock Trajectory Diagram – Consider two Processes that require access to two resources Chapter 8 - Deadlocks Deadlock Detection • Collapse a resource allocation graph into a "wait-for" graph. Periodically invoke an algorithm to search for a cycle in the graph Chapter 8 - Deadlocks Deadlock Detection • How often to run the algorithm depends on a few factors • How often is a deadlock likely to occur? • When it does occur, how many threads will need to be aborted or rolled back? • Running the algorithm uses precious CPU cycles, so we don't want to run it too often • However, if the algorithm is not invoked often enough, deadlock will occur too frequently. The process to abort or roll back threads may take some time Chapter 8 - Deadlocks Recovery from Deadlock • Abort or rollback all deadlocked threads? • Abort or rollback one thread at a time until deadlock stops? • Should aim to choose the minimum cost • Priority of the thread(s)? • Computation time completed? Computation time remaining? • Number of resources held? Number of remaining resources needed? • Fewest number of thread(s) to clear the deadlock • Starvation could occur if the same thread is always the victim Chapter 8 - Deadlocks
Chapter 9A – Memory Management (Basics) Fall 2023 Overview • Background • Basic Hardware • Address Binding • Logical versus Physical Address Space • Dynamic Loading • Dynamic Linking and Shared Libraries • Contiguous Memory Allocation Chapter 9A – Memory Management (Basics) Background • Modern computer systems maintain several processes (at least partially) in memory during system execution • Modern computer systems have a lot of memory • Operating systems must manage the memory well • Operating systems must closely integrate with the hardware to manage the memory • Hardware design and support is important Chapter 9A – Memory Management (Basics) Background • Memory management requires • Allocating memory to processes when needed from disk • Managing memory efficiently during runtime • Deallocate memory when processes are done Chapter 9A – Memory Management (Basics) Basic Hardware • The CPU can access main memory and registers directly. If the data is not in memory or in registers, the operating system must fetch the data from disk • Register access is very fast (one CPU clock cycle or less) • Memory access may generate a memory stall • CPUs have a cache to speed up memory access at the hardware level • SSDs are ~4x faster than HDDs • Memory is ~30x faster than SSDs • Cache is ~100x faster than memory Chapter 9A – Memory Management (Basics) Basic Hardware • The CPU "sees" a stream of addresses and data • The CPU cannot tell if a process has "permission" to read or write memory addresses • Asking the operating system to police this activity comes with significant overhead • A hardware solution is needed • CPUs use a base register and a limit register • Base register – contains the lowest address in memory a process can access • Limit register – contains the size of the memory space for a process • Base+Limit == the maximum address in memory a process can access Chapter 9A – Memory Management (Basics) Basic Hardware • One solution: When in user mode, the CPU must check every memory access to ensure it is between the base and the limit • The instructions to load the base and limit registers are privileged Chapter 9A – Memory Management (Basics) Address Binding • A user process could reside in any part of the physical memory • Data in the process will reside somewhere in its allocated block • It would be inconvenient for developers to be forced to keep track of exact physical addresses in memory. For example, • Programmers usually use a symbolic "address". E.g. count • The compiler binds the symbolic address to a relocatable address. E.g. "14 bytes from the beginning of this module" • The linker binds the relocatable address to an absolute address. E.g. 74014 Chapter 9A – Memory Management (Basics) Address Binding • The binding step can occur at: • Compile time – The location in memory may be known at compile time. The compiler generates absolute code. If the location changes, the program must be recompiled • Load time – The location in memory may not be known at compile time but it is decided when the program is loaded. The loader can use relocatable code. If the location changes, the program just needs to be reloaded • Execution time – If the process can be moved during its execution from one memory segment to another, binding must wait until run time. Special hardware is required to make this work. This is the method most modern operating systems use. Chapter 9A – Memory Management (Basics) Address Binding Chapter 9A – Memory Management (Basics) Logical vs Physical Addresses • Logical address – The "address" generated by the CPU • This is sometimes also known as a virtual address • Physical address – The address of the memory-address register in memory • If binding occurs at compile time, these are the same. If binding occurs at execution time, these are different Chapter 9A – Memory Management (Basics) Logical vs Physical Addresses • The translation from logical address to physical address is handled by a hardware device in the CPU called the memory-management unit (MMU) • A simple implementation: Instead of a base register, use a relocation register in the MMU. The value will be added to every logical address to get the physical address Chapter 9A – Memory Management (Basics) Logical vs Physical Addresses • The logical addresses are in the range 0 to max • All addresses generated by the user program think it is using address 0 to max • The physical addresses are in the range R+0 to R+max for a base value R Chapter 9A – Memory Management (Basics) Dynamic Loading • The entire program does not need to be in memory to execute • To manage memory better, routines are kept on disk in relocatable load format • Load routines in memory when it is called • Unused routines are never loaded (e.g. Very rare error handling functions) • This is managed in user space without special support from the operating system • Operating systems may provide some tools to help implement dynamic loading Chapter 9A – Memory Management (Basics) Dynamic Linking and Shared Libraries • Some operating systems only support static linking. All system libraries are loaded into the binary program image. This is very inefficient • Dynamically linked libraries (DLLs) (also known as shared libraries) are system libraries that loaded dynamically at execution time • This is a more efficient use of memory • It is also possible to share loaded libraries among multiple processes • Libraries can be updated without relinking the programs that use it. Programs could choose which version to use. Chapter 9A – Memory Management (Basics) Dynamic Linking and Shared Libraries • Because DLLs are shared, for memory protection, operating system assistance is required Chapter 9A – Memory Management (Basics) Contiguous Memory Allocation • An early approach to memory management. The other approach is non-contiguous • Better known as paging and will be addressed later • Main memory is divided into two partitions • Operating system can be in low or high memory. Most operating systems place it in high memory • User processes are held in the other partition • Each process is contained in a single contiguous section of memory Chapter 9A – Memory Management (Basics) Contiguous Memory Allocation • To protect user processes from each other and from the operating system itself, the MMU uses the relocation (base) register and the previously mentioned limit register • Each logical address must be less than the limit register • These registers are updated when a context switch occurs Chapter 9A – Memory Management (Basics) Contiguous Memory Allocation • Each contiguous section of memory is a fixed or dynamic partition • Fixed partition • Partitions are allocated with sizes that never change • Each partition may be the same or different sizes depending on implementation • If the sizes are different, select a partition for a process by first-fit or best-fit • Internal fragmentation is a problem. There will always be portions of the partition that are wasted • External fragmentation is a problem. There may be enough free space but spanning partitions is not allowed Chapter 9A – Memory Management (Basics) Contiguous Memory Allocation • First-fit • P1 = 190 • P2 = 400 • P3 = 150 • P4 = 160 • Internal Fragmentation • 10 + 50 + 150 = 210 • External Fragmentation • 50 + 70 + 150 > 160 Chapter 9A – Memory Management (Basics) 200 300 5 0 7 0 150 450 P1 P3 P2 P4 Contiguous Memory Allocation • Best-fit • P1 = 190 • P2 = 400 • P3 = 150 • P4 = 160 • Internal Fragmentation • 10 + 50 + 0 + 140 = 200 • External Fragmentation • None Chapter 9A – Memory Management (Basics) 200 300 5 0 7 0 150 450 P1 P4 P3 P2 Contiguous Memory Allocation • Each contiguous section of memory is a fixed or dynamic partition • Dynamic (variable) partition • Partitions are allocated with sizes that may change as needed • Empty partitions can be shifted and adjusted through compaction • Select a partition for a process by first-fit, best-fit, or worst-fit (This is okay because we use compaction) • Internal fragmentation is not a problem. • External fragmentation is a problem, but it is easily resolved with compaction Chapter 9A – Memory Management (Basics) Contiguous Memory Allocation • First-fit • P1 = 190 • P2 = 10 • P3 = 150 • P4 = 100 • P5 = 500 • Internal Fragmentation • None • External Fragmentation • 50 + 100 + 70 + 150 + 450 > 500 Chapter 9A – Memory Management (Basics) 200 350 5 0 7 0 150 450 P1 P2 P3 P4 P5 100 1 0 190 150 100 200 Contiguous Memory Allocation • Best-fit • P1 = 190 • P2 = 10 • P3 = 150 • P4 = 100 • P5 = 500 • Internal Fragmentation • None • External Fragmentation • 200 + 50 + 70 + 450 > 500 Chapter 9A – Memory Management (Basics) 5 0 7 0 150 450 P3 P5 200 P1 P2 1 0 190 300 P4 100 200 Contiguous Memory Allocation • Compaction Chapter 9A – Memory Management (Basics) 5 0 7 0 450 P5 200 500 270 150 P1 P2 P3 1 0 190 P4 100 Contiguous Memory Allocation • Compaction • The compaction process is costly • A better solution is to permit non-contiguous memory allocation (paging) • Compaction is also used to manage storage so it will come up again Chapter 9A – Memory Management (Basics)
Chapter 9B – Memory Management (Paging) Fall 2023 Overview • Basic Method • Hardware Support • Protection • Shared Pages • Structure • Swapping Chapter 9B – Memory Management (Paging) Basic Method • With paging, process space is no longer contiguous • Used by most modern operating systems • Partition the physical memory into fixed-size blocks called frames • Partition the logical memory into same-sized fixed-size blocks called pages • There can be more pages than there are frames. This is virtual memory and will be covered in the next chapter. • Use a Page Table for each process to translate logical addresses to physical addresses Chapter 9B – Memory Management (Paging) Basic Method • Processes use pages 0 to N so it thinks the memory is contiguous • However, the physical location of each frame in memory is non-contiguous • Internal fragmentation is still possible • External fragmentation is avoided Chapter 9B – Memory Management (Paging) Basic Method • The logical address generated by the CPU is divided into a bitmap of length m. That's 2m logical addresses with: • Page number (p) - used as an index into a page table which contains base address of each page in physical memory. It is of length m-n or 2m-n bits. • Page offset (d) – combined with base address to define the physical memory address that is sent to the memory unit. It is length n or 2n bits. This is the size of each page. Chapter 9B – Memory Management (Paging) page number page offset p d m -n n Basic Method Chapter 9B – Memory Management (Paging) Basic Method • Example page numbers and page offsets • 3 bits – 21 | 22 (2 pages, 4 page offsets each) Chapter 9B – Memory Management (Paging) 000 Page 0 Location 0 001 Page 0 Location 1 010 Page 0 Location 2 011 Page 0 Location 3 100 Page 1 Location 0 101 Page 1 Location 1 110 Page 1 Location 2 111 Page 1 Location 3 Basic Method • Example page numbers and page offsets • 4 bits – 23 | 21 (8 pages, 2 page offsets each) Chapter 9B – Memory Management (Paging) 0000 Page 0 Location 0 0001 Page 0 Location 1 0010 Page 1 Location 0 0011 Page 1 Location 1 0100 Page 2 Location 0 0101 Page 2 Location 1 0110 Page 3 Location 0 0111 Page 3 Location 1 1000 Page 4 Location 0 1001 Page 4 Location 1 1010 Page 5 Location 0 1011 Page 5 Location 1 1100 Page 6 Location 0 1101 Page 6 Location 1 1110 Page 7 Location 0 1111 Page 7 Location 1 Basic Method • Example page numbers and page offsets • 4 bits – 22 | 22 (4 pages, 4 page offsets each) Chapter 9B – Memory Management (Paging) 0000 Page 0 Location 0 0001 Page 0 Location 1 0010 Page 0 Location 2 0011 Page 0 Location 3 0100 Page 1 Location 0 0101 Page 1 Location 1 0110 Page 1 Location 2 0111 Page 1 Location 3 1000 Page 2 Location 0 1001 Page 2 Location 1 1010 Page 2 Location 2 1011 Page 2 Location 3 1100 Page 3 Location 0 1101 Page 3 Location 1 1110 Page 3 Location 2 1111 Page 3 Location 3 Basic Method • Mapping pages to frames • 5 bits – 23 | 22 (8 pages, 4 page offsets each) • Page 0, offset 0 (a) is at physical address 20 • Page 0, offset 3 (d) is at physical address 23 • Page 1, offset 0 (e) is at physical address 24 • Page 3, offset 1 (n) is at physical address 9 • (Note: In this diagram, if a physical address is handled in 1-byte increments, there are 32 bytes of memory, a page is 4 bytes, and there are 8 pages/frames) Chapter 9B – Memory Management (Paging) Basic Method • Internal fragmentation • Consider a page size of 2048 bytes and process size is 72,766 bytes • 35 pages + 1,086 bytes • The last page is using 1,086 bytes with 962 bytes left over • A process could use n pages + 1 byte so n+1 frames in the worst case. Almost the entire frame is useless. On average, ½ of the last frame is unused • Smaller page sizes minimizes the waste but adds overhead to the operating system • Larger page sizes make disk I/O to memory more efficient but adds more internal fragmentation Chapter 9B – Memory Management (Paging) Basic Method • Internal fragmentation • Most operating systems support two page sizes • 4KB or 8KB for regular processes • 2MB or 4MB or higher for processes that use a lot of memory Chapter 9B – Memory Management (Paging) Basic Method • External fragmentation • We have none. Any free frame can be allocated to a process as needed. Chapter 9B – Memory Management (Paging) Basic Method • Free frames • The operating system maintains a system-wide frame table • One entry per frame • Each entry has a flag indicating whether the frame is free or not • If it is not free, which process is using it Chapter 9B – Memory Management (Paging) Basic Method • Free frames Chapter 9B – Memory Management (Paging) Hardware Support • Due to the size of a process' page table, the table is kept in memory • The address of the page table is stored in the Page-table base register (PTBR) • The size of the page table is stored in the Page-table length register (PTLR) • Every instruction that accesses memory will trigger two memory accesses: • One to reference the page table itself and find the physical address • One to access the found address in memory • Solution: Cache the page table (Most systems have multiple levels) • This is called the Translation Look-aside Buffer (TLB) Chapter 9B – Memory Management (Paging) Hardware Support • Some TLBs hold address-space identifiers (ASIDs) so processes can only use their own entries • Otherwise, the TLB will need to be reloaded at each context switch • Typically small (e.g. 64 – 1024 entries). Some entries can be made permanent. • If the page is found in the TLB (a hit), use the frame • If the page is not found in the TLB (a miss) • Consult the page table in memory instead • Load it into the TLB so we can avoid a miss in the future (Use an algorithm like Least-recently used, round-robin, or random to replace existing entries) Chapter 9B – Memory Management (Paging) Hardware Support Chapter 9B – Memory Management (Paging) Hardware Support • Effective memory-access time • The percentage of times the page number of interest is found in the TLB is the hit ratio • If it is not found in the TLB, we need to consult the page table (1 access) • Then we can use the address (1 access) • Suppose a hit ratio of 80% and a memory access time of 10 nanoseconds, then effective access time is 0.80x10 + 0.2x20 = 12 nanoseconds • A hit ratio of 99% is 10.1 nanoseconds Chapter 9B – Memory Management (Paging) Protection • Each entry in the page table can hold a protection bit to indicate whether the frame is read-only or read-write. • To determine whether the frame is in the process' logical address space • Use a page-table length register • Each entry in the page table can hold a valid-invalid bit for all frames in the address space Chapter 9B – Memory Management (Paging) Protection Chapter 9B – Memory Management (Paging) Shared Pages • Paging makes sharing address space easy • These pages should be read-only • Commonly used for DLLs Chapter 9B – Memory Management (Paging) Structure • Page tables can be very large. We don't want to put this in one contiguous block • Solution: Hierarchical Page Tables Chapter 9B – Memory Management (Paging) Structure • Here are some examples using 64 bits • More page tables means more memory accesses, so this strategy only goes so far Chapter 9B – Memory Management (Paging) Structure • Hashed Page Tables • Common in address spaces larger than 32 bits • Each entry in the page table holds • A hash of the page number • The frame • A pointer to the next hash • A logical address is hashed and then the matching hash is searched in the list Chapter 9B – Memory Management (Paging) Structure • Hashed Page Tables Chapter 9B – Memory Management (Paging) Structure • Inverted Page Tables • Instead of one page table per process, one page table for all processes • One entry in the table for each frame in the system • This removes the need to maintain many page tables • This adds to the amount of time it takes to search the page table • Since pages to frames is one-to-one, shared memory will be regularly mapped and re-mapped Chapter 9B – Memory Management (Paging) Structure • Inverted Page Tables Chapter 9B – Memory Management (Paging) Structure • In reality, modern operating systems will employ a mixture of these structures Chapter 9B – Memory Management (Paging) Swapping • A process can be temporarily swapped to a backing store (usually disk) and then brought back in • Total memory space for processes can exceed the physical memory (oversubscribed) Chapter 9B – Memory Management (Paging) Swapping • The backing store needs to be reasonably fast • Swapping entire processes is generally no longer used • Modern operating systems may still swap pages • Swapping pages due to low memory is an "emergency" situation and should be avoided • Terminate unnecessary processes • Get more memory Chapter 9B – Memory Management (Paging)
Chapter 10 – Virtual Memory Fall 2023 Overview • Background • Demand Paging • Page Replacement • Allocation of Frames • Thrashing • Other Considerations Chapter 10 – Virtual Memory Background • Programs need to be in memory to execute, but not the whole program • Some routines are rarely (or never) used. E.g. Error routines • Only a portion of a large data structure might be used at any time • Ideally, we would like to load only the portion of a program that is needed • We are no longer constrained by the limits of physical memory • Fewer programs in memory means more programs can execute Chapter 10 – Virtual Memory Background • Virtual Memory – Separation of user logical memory from physical memory • Chapter 9 covered logical (pages) and physical addresses (frames) but assumed the number of pages and frames were equal. • If a system uses more pages than frames, it is using virtual memory Chapter 10 – Virtual Memory Demand Paging • Bring a page into memory only when it is needed ("demanded") • Less I/O and no unnecessary I/O • Less memory used • Faster response time • Similar to swapping except exactly which pages are brought in is intentional • The MMU requires new functionality • Use the valid/invalid bit approach: Valid (memory-resident) means the page is in memory and legal. Invalid means the page is either illegal or legal but not in memory yet Chapter 10 – Virtual Memory Demand Paging • Initially, every entry in the page table is set to invalid • If a requested page is invalid, generate a page fault Chapter 10 – Virtual Memory Demand Paging • 1. If there is a reference to a page, first reference to that page will trap to operating system (Page fault) • 2. Operating system looks at another table to decide: • Invalid reference → abort • Just not in memory • 3. Find free frame Chapter 10 – Virtual Memory Demand Paging • 4. Swap page into frame via scheduled disk operation • 5. Reset tables to indicate page now in memory. Set validation bit = v • 6. Restart the instruction that caused the page fault Chapter 10 – Virtual Memory Demand Paging Chapter 10 – Virtual Memory Demand Paging • If all frames begin as invalid, the page table will eventually populate with valid pages • In practice, this means a lot of page faults initially but eventually the process will settle Chapter 10 – Virtual Memory Demand Paging • Free-Frame list • When a page needs to be brought into memory, the operating system needs to know where to put it • Operating systems maintain a list of free-frames • For security reasons, a frame is "zeroed-out" prior to being assigned • Which frame to choose will be discussed later Chapter 10 – Virtual Memory Demand Paging • Performance • Page faults need to be kept to a minimum • Reading a page from disk can take considerable time • Calculate the effective access time similar to how we calculate the effective memory-access time • If 0 ≤ p ≤ 1 where p is the probability of a page fault Chapter 10 – Virtual Memory Demand Paging • Performance • Suppose a HDD has a page fault time of ~8 milliseconds • Suppose memory access time is 200 nanoseconds • Suppose a page fault in 1/1000 accesses • Then effective access time is 8.2 microseconds instead of 200 nanoseconds • Using efficient secondary storage (like SSDs) structured to manage swap space can help • Mobile devices typically do not use swap space Chapter 10 – Virtual Memory Demand Paging • Another way to improve performance of demand paging is to employ copy-on-write • We learned the fork() system call copies the parent process space to the child including all pages • In fact, for efficiency, the pages are shared until there is an update • Most child processes simply call exec(). Not copying pages makes a lot of sense Chapter 10 – Virtual Memory Page Replacement • Demand paging, as it has been discussed, ensures that a page fault occurs for a page exactly once: The first time the page is used • Eventually, the system will run out of free frames. Some pages that are valid but no longer needed will need to be replaced Chapter 10 – Virtual Memory Page Replacement • 1. Find the location of the desired page on disk • 2. Find a free frame: • If there is a free frame, use it • If there is no free frame, use a page replacement algorithm to select a victim frame • Write victim frame to disk; update the page and frame tables • 3. Bring the desired page into the (newly) free frame; update the page and frame tables • 4. Continue the process by restarting the instruction that caused the trap Chapter 10 – Virtual Memory Page Replacement • This involves a page-out and a page-in for every page fault • We can eliminate the need for a page-out by maintaining a modify bit (dirty bit) • If any byte in this page has been changed, set the modify bit • If the modify bit is set, then a page-out is required • If the modify bit is not set, then the page can be discarded Chapter 10 – Virtual Memory Page Replacement • How do we select a victim frame? • Page replacement algorithms • First-in First-out (FIFO) • (Optimal Page Replacement) • Least Recently Used (LRU) • Counting algorithms • Least Frequently Used (LFU) • Most Frequently Used (MFU) Chapter 10 – Virtual Memory Page Replacement • Using a string of page numbers and calculate the number of page faults for a given number of frames • E.g. • 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1 • 3 frames • We should expect More frames == Fewer faults Chapter 10 – Virtual Memory Page Replacement • FIFO • 15 page faults Chapter 10 – Virtual Memory Page Replacement • FIFO can sometimes produce poor or unexpected results • For example, here is a graph for 1,2,3,4,1,2,5,1,2,3,4,5 • Sometimes simply adding more memory (frames) can increase page faults • This is known as Belady's anomaly Chapter 10 – Virtual Memory number of page faults 16 14 12 10 8 6 4 2 123 number of frames 4567 Page Replacement • Optimal Page Replacement • We can derive the theoretical optimal replacement algorithm by replacing the page that will not be used for the longest period of time • Just like the Shortest-Job First algorithm, this requires perfect knowledge of future values. It is used as a theoretical target to measure against • E.g. 9 page faults Chapter 10 – Virtual Memory Page Replacement • Least Recently Used • Use past knowledge to expire old entries • E.g. 12 page faults • Better than FIFO • Approaching Optimal Chapter 10 – Virtual Memory Page Replacement • Least Recently Used • How to determine which frame was least recently used? • Counter • Update the counter whenever it is used • When a page needs to be replaced, search all entries for the oldest entry • Stack (with modifications) • Move the frame to the top of the stack when it is used • When a page needs to be replaced, use the page at the bottom of the stack Chapter 10 – Virtual Memory Page Replacement Chapter 10 – Virtual Memory 2 1 0 4 7 stack before a 7 2 1 4 0 stack after b reference string 4707101212 2 7 a b 1 Page Replacement • Least Recently Used • It might not be ideal to be so judicious about replacing pages • We can introduce a bit of tolerance to the replacement algorithm by introducing a reference bit. Set the bit to 1 when it is used • This could be • a simple 0/1 flag • something larger like an 8-bit number. Set the highest order bit when it is used • This is a Second-Chance Algorithm Chapter 10 – Virtual Memory Page Replacement • Least Recently Used • If the page is a candidate for a victim page • check the reference bit first • If it is >0, set the bit to 0 (or shift the bits right) • Else, the page is 0 (or 0000 0000) • This is the victim page Chapter 10 – Virtual Memory circular queue of pages (a) next victim 0 reference bits pages 0 1 1 0 1 1 … … circular queue of pages (b) 0 reference bits pages 0 0 0 0 1 1 … … Page Replacement • Counting Algorithms. Not commonly used, but described for illustration purposes • Requires a counter for each page • Least Frequently Used (LFU) – Replace the page with the smallest count • An actively used page should have a high count and therefore should not get replaced. However, it might have a high count at program startup and never used again. This algorithm could just slowly decrease the count of unused pages over time • Most Frequently Used (MFU) – Replace the page with the highest count • The page with the smallest count definitely should not be replaced since it is likely going to be used soon Chapter 10 – Virtual Memory Page Replacement • All these algorithms have operating system guessing about future page access • Some applications have better knowledge (e.g. Databases, Data Warehouses, …) • These applications usually manage memory for their specific workload better than the operating system defaults • Operating systems can give these applications direct access to the disk, bypassing all the operating system memory management and file-system structures Chapter 10 – Virtual Memory Allocation of Frames • As frames are pulled from the free-frame list, eventually we will run out and need to employ some page replacement strategies • Since a page fault hinders performance, a page fault and forcing a page-out/page-in hinders performance even more • Ideally, the operating system should always have a set of free-frames ready for use • Instead of allowing the free-frame list to drop to 0, periodically search for frames that can be freed Chapter 10 – Virtual Memory Allocation of Frames Chapter 10 – Virtual Memory Thrashing • If a process needs a page in memory, it may replace a page it will need very soon • Then a request for that page will page fault causing a recent page to be replaced • Then a request for that recent page will page fault causing a recent page to be replaced • If the system has too many active processes, processes may start "stealing" pages from other active processes • CPU utilization will drop so the operating system will think it should accept more processes creating more page faults • Thrashing – When the amount of time spent paging exceeds the amount of time spent executing real work Chapter 10 – Virtual Memory Thrashing • Possible Solutions • Force processes to use their own set of pages so they do not steal from others. Good estimates for how many pages a process will need is required. • Page-in the page requested and other pages with the same locality (e.g. all the instructions in the same program structure or same data structure) Chapter 10 – Virtual Memory Other Considerations • More on locality and program/data structure • Consider the following code • int i,j; int[128][128] data; for (j=0; j < 128; j++){ for (i=0; i < 128; i++){ data[i][j] = 0; } } • Since C holds multidimensional arrays in row-major order, if a page can hold one row, this code could generate 128x128 (16,384) page faults due to demand paging. One for every update. Chapter 10 – Virtual Memory Other Considerations • More on locality and program/data structure • Compare with the following code • int i,j; int[128][128] data; for (i=0; i < 128; i++){ for (j=0; j < 128; j++){ data[i][j] = 0; } } • This will zero each element in the page before requesting the next one. This will cause 128 page faults (~0.8% of 16384). Good programming can reduce page faults. Chapter 10 – Virtual Memory Other Considerations • More on locality and program/data structure • Stacks have good locality since access is always at the top • Hash tables do not have good locality since it scatters references all over the place • The compiler and loader can separate read-only code from data. More read-only pages means no need to page-out. • The loader can avoid placing routines across page boundaries. It can combine routines that call each other together on the same page. • (Of course, locality is only one factor to consider. Programmers must also consider search speed, memory references, algorithmic efficiency, etc.) Chapter 10 – Virtual Memory Other Considerations • Prepaging • In contrast to demand paging, prepaging some or all of a program can be used to avoid page faults at program startup, decreasing startup time. • Prepaging part of a program can be difficult because it is difficult to know what pages will be required • Prepaging an input file is easier since files are usually read sequentially. • Linux provides readahead() to prefetch a file into memory, so all subsequent reads are done in memory instead of to disk Chapter 10 – Virtual Memory Other Considerations • Page Locking (Pinning) • The operating system may tell a disk drive which memory address to write to • Meanwhile, the process that asked for the data is in an I/O waiting queue • Another process needs a frame, but the page replacement algorithm recommends replacing the frame being written to! • The operating system can set a lock bit to ensure the page is "off-limits" • For efficiency, the operating system may set the lock bit for common internal processes (e.g. the memory management module itself) • Some privileged user processes (e.g. Databases) may also request the lock bit Chapter 10 – Virtual Memory
Chapter 11 – MassStorage Structure Fall 2023 Overview • Overview • HDDs and NVMs • HDD and NVM Scheduling • Error Detection and Correction • Storage Device Management • Swap-Space Management • Storage Attachment • RAID Structure Chapter 11 – Mass-Storage Structure Overview • Modern computers must • Store large amounts of data • Store this data beyond the lifetime of any processes (even if powered off) • Multiple processes must be able to use the data concurrently Chapter 11 – Mass-Storage Structure Overview • Secondary storage for modern computers uses either • hard disk drives (HDD) or • nonvolatile memory (NVM) • Most common version of NVM is solid state drives (SSD) and USB drives • Some systems can use part of the volatile memory as if it were secondary storage. This is known as a RAM drive • This is typically used to hold temporary data, data in transit between disk and memory, or swap space • Magnetic tape is used for inexpensive, long-lasting backup and archive Chapter 11 – Mass-Storage Structure HDD and NVM • HDDs spin platters of magnetically-coated material under moving read-write heads • The read-write head is separated from the platter using a very thin cushion of air or gas (e.g. helium) • Each platter is divided into cylinders divided into tracks divided into sectors • Drives rotate at 60 to 250 times per second (rotations per minute – RPM) • 5,400 or 7,200 or 10,000 or 15,000 RPMs are common • CDs, DVDs, and Blu-Ray discs are removable Chapter 11 – Mass-Storage Structure HDD and NVM • Platters, Cylinders, Tracks, and Sectors • Sectors were typically 512 bytes each until about 2010 • Sectors are now 4KB each • Each track used to hold the same number of sectors. Data on outer tracks were less dense with lots of inaccessible space • Variable number sectors allow more sectors on outer tracks. This increases data density and therefore capacity Chapter 11 – Mass-Storage Structure track t sector s spindle cylinder c platter arm read-write head arm assembly rotation HDD and NVM • Performance • Transfer rate is rate at which data flow between drive and computer • Positioning time (random-access time) affects the actual transfer rate • Seek time – is time to move disk arm to desired cylinder (this is usually the longest wait time) • Rotation latency – time for desired sector to rotate under the disk head • Head crash can occur if the disk head contacts the disk surface • Physical damage cannot be repaired and is usually unrecoverable unless using backups or RAID protection Chapter 11 – Mass-Storage Structure HDD and NVM • NVM • No moving parts and therefore no seek time or rotational latency • More reliable but may have a shorter life-span than HDDs • More expensive and less capacity than HDDs • Some busses may be slower than connecting directly to the system bus (e.g. USB bus) • Better suited for mobile devices than HDDs (laptops, phones, etc.) Chapter 11 – Mass-Storage Structure HDD and NVM • Data is read and written in "pages" (similar to the sector idea) • NVM is the most efficient storage medium for reads • Writing pages requires the existing data to be erased first • Erasing and writing new data slowly degrades the memory cell • Algorithms keep track of all pages to find free pages and evenly distribute writes Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • Disk drives are addressed as one-dimensional arrays of logical blocks. Each block is mapped to a sector. • HDDs • Sector 0 is the first sector on the first track on the first outermost cylinder • Then mapping proceeds through each track in the same cylinder • Continue from the outermost cylinder to the innermost • NVM • Simply address through each chip, block, and page Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • The operating system should leverage disks efficiently. Knowing the underlying structure helps decrease access time and increase disk bandwidth • There are many sources of disk I/O (OS, system processes, user processes) • Processes waiting for I/O move to a waiting queue • Disk requests are held in a queue and sent to the disk • Modern disks have their own queue instead of just the OS • Each request contains a number of factors (e.g. read or write, disk address, memory address, number of sectors, etc.) • Managing the queue of requests intelligently can make disk I/O more efficient Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • First come first served scheduling Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • Shortest seek time first – Select the address closest to the head's current position • Queue = 176, 79, 34, 60, 92, 11, 41, 114 • Head starts at 50 • Starvation can occur Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • SCAN scheduling (elevator scheduling) Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • C-SCAN scheduling Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • Other scheduling algorithms • Random • Last in first out • Priority • Treat reads and writes with different priority • Etc. • Scheduling selection depends on the anticipated workload • Most operating systems use a combination of algorithms Chapter 11 – Mass-Storage Structure HDD and SSD scheduling • NVM scheduling • There are no disk heads or rotational latencies • Random is the best approach • Optimizing for reads is ideal because • Reads are much faster than writes • Read times are uniform, write times are variable Chapter 11 – Mass-Storage Structure Error Detection and Correction • Detection and correction is fundamental to memory, network, storage and others • Bits can change spontaneously while stored on disk • Reserve one bit in a byte as a parity bit • Set to 0 if the number of bits set to 1 is even • Set to 1 if the number of bits set to 1 is odd • If an error occurs, the parity does not match so the user can be informed • Error-correction code (ECC) can be used to detect and sometimes correct multiple bytes • A soft error can be automatically corrected. Too many errors is a hard error Chapter 11 – Mass-Storage Structure Storage Device Management • Low-level formatting (physical formatting) – Divide a disk into sectors • Each sector holds both data and metadata (eg. Size, ECC, etc.) • The operating system will then record its own data structures on the disk • Partition the disk into one or more groups of cylinders, each treated as a logical disk (eg. C drive, D drive, /boot, /usr, /home, etc.) • Each partition is logically formatted to a file system type (eg. NTFS, ext4, zfs, etc.) • File-systems keep data and their metadata in similar sectors to reduce seek time • Partitions contain metadata including whether or not it is bootable Chapter 11 – Mass-Storage Structure Storage Device Management • A computer has a bootstrap program built into the firmware • The last thing this program does is read the first block in the first partition on secondary storage to find the OS bootloader. This is the master boot record • The boot loader passes control to a bootstrap program on the first sector on a bootable partition. This program loads the rest of the OS Chapter 11 – Mass-Storage Structure Swap-Space Management • We know that entire processes are no longer swapped out to disk • However, individual pages may be swapped to disk • Swapping and paging are interchangeable terms • Swapping may be sent to a (raw) partition or a file(s) on a partition • If a raw partition is used, algorithms that optimize for speed over storage efficiency might be used • Files can be added and removed as desired but are subject to the underlying filesystem's storage structure Chapter 11 – Mass-Storage Structure Storage Attachment • Host-attached storage • Disks are attached to the computer over a set of wires known as the I/O bus • Data is transferred on either end of the I/O bus by controllers • Host controller is the controller on the motherboard • Data controller is built into the disk • Serial Advanced Technology Attachment (SATA) is the most common I/O bus type • Other common technologies include USB FireWire and Thunderbolt • High-end workstations and storage arrays may use optical based Fiber Channel Chapter 11 – Mass-Storage Structure Storage Attachment • Network-attached storage (NAS) • Storage made available across a network (Typically the Local Area Network) • Common protocols include NFS and CIFS (UDP/TCP layer) • iSCSI presents the SCSI protocol remotely (IP layer) Chapter 11 – Mass-Storage Structure Storage Attachment • Cloud storage • Similar to NAS except provided over the Internet or a WAN rather than LAN • Due to higher latency and packet loss across the WAN, commonly presented via APIs at the application layer • Common examples include Amazon S3, Dropbox, Microsoft OneDrive, Apple iCloud Chapter 11 – Mass-Storage Structure Storage Attachment • Storage Area Network (SAN) and storage arrays • Storage arrays • custom built storage servers that manage multiple storage types, networking, permissions, etc. • Disks can be added and replaced transparently • Redundancy built in • Added features such as snapshots, clones, thin provisioning, deduplication, etc. Chapter 11 – Mass-Storage Structure Storage Attachment • Storage Area Network (SAN) and storage arrays • SANs are a private network connecting multiple hosts to multiple storage units • Typically used over short distances Chapter 11 – Mass-Storage Structure LAN/WAN storage array storage array data-processing center web content provider server client client client server tape library SAN RAID Structure • All disks are prone to error and failure • Losing data could be catastrophic • Copies of the data should be made for redundancy • Redundant Array of Inexpensive Disks (RAID) – Use multiple disks • To provide reliability and redundancy • Spreading data across multiple disks can also create parallelism which can improve speed • (Disks these days are high speed and highly reliable and therefore no longer "inexpensive", so some use "independent" instead for the "I") Chapter 11 – Mass-Storage Structure RAID Structure • RAID logic is implemented at • Hardware level (a chip dedicated to managing RAID) • Expensive. Best suited for servers and super computers • Software level (ie. By the operating system) • Inexpensive. The boot process takes some care. Best suited for desktops • Firmware level (Low-level support in the BIOS with driver support for the OS) • Depends on OS and driver support. • Also known as "Fake RAID" or "Hybrid" Chapter 11 – Mass-Storage Structure RAID Structure • There are (generally) 6 different RAID types • RAID 0 – Spread data out across two disks instead of one. This is known as striping. Double the read and write speed but no redundancy. • Suitable for systems where speed is important, but reliability is not (E.g. Gaming) Chapter 11 – Mass-Storage Structure RAID Structure • There are (generally) 6 different RAID types • RAID 1 – Write all data to two disks (mirroring). One disk perfectly mirrors the other. Reads may be improved but write performance suffers. Disk errors or failures can be tolerated and corrected. • Suitable for systems where reliability is important (eg. Mission-critical) Chapter 11 – Mass-Storage Structure RAID Structure • There are (generally) 6 different RAID types • Raid 0+1 or RAID 01 – Mirror two striped disks to two other disks • Raid 1+0 or RAID 10 – Stripe two mirrored disks to two other disks • Brings the best of both striping and mirroring • Requires 4 disks at minimum Chapter 11 – Mass-Storage Structure RAID Structure • There are (generally) 6 different RAID types • RAID 5 – Stripe data across disks. Also stripe 1 parity block across disks. • The loss of one disk can be tolerated. The missing block can be rebuilt from the parity block • RAID 5 and RAID 10 are the most common implementations. They provide efficient striping and mirroring • In the event of disk failure in RAID 5, all disks are involved in a rebuild. In RAID 10, not all disks need to be involved. Chapter 11 – Mass-Storage Structure RAID Structure • There are (generally) 6 different RAID types • RAID 6 – Stripe data across disks. Also stripe 2 parity blocks across disks. • The loss of two disks can be tolerated. The missing blocks can be rebuilt from the parity blocks Chapter 11 – Mass-Storage Structure RAID Structure • There are (generally) 6 different RAID types • There are many other variants such as RAID 2, RAID 3, RAID 4, RAID 50, RAID 60, RAID 100, JBOD, etc. • RAID cannot protect you from user error. Backups are still needed • RAID disks need to be the same size (or purposely hold as much as the smallest disk). It is difficult to add or shrink space • Multiple disks are more expensive • Hot spares can be used to provide immediate rebuilds in the case of disk failure • Rebuilds take time and temporarily affect performance Chapter 11 – Mass-Storage Structure
Chapter 13 – FileSystem Interface Fall 2023 Overview • Overview • File Concept • Access Methods • Directory Structure • Protection Chapter 13 – File-System Interface Overview • The most visible aspect of a general-purpose OS is the file system • The file system contains • Files (including metadata about each file) • Directories to organize the files • The file system is stored on storage devices as described in Chapter 11 • The operating system provides an abstraction between the physical parts of the storage devices and the logical representation of the data in files Chapter 13 – File-System Interface File Concept • A file is a named collection of related information • From the user's perspective, this is the most basic unit of data. All data is in a file. • Files can be • Binary (e.g. executable files, compressed files) • Alphanumeric or text based (e.g. source files, text files) • Since files are so fundamental, Linux uses files to represent attributes of the operating system or the system state under the /proc directory Chapter 13 – File-System Interface File Concept • Files have attributes. This metadata helps users identify information about the file Chapter 13 – File-System Interface File Concept • Basic file operations • Create – Allocate space on disk and create a new file • Read – at a read location defined by a process • Write – at a write location defined by a process • Reposition within a file (seek) – at a location defined by a process • Delete – Erase the file and the metadata from disk • Truncate – Erase the file contents but not the metadata from disk • Open/Close – Move the contents of the file in or out of memory Chapter 13 – File-System Interface File Concept • Other file operations • Rename – Update the name of the file in the metadata • Append – Write to the end of the file • Most operations can be achieved by combining the above operations • E.g. To "Copy a file": create a new file and open it for writing, open another file for reading, read the contents of the other file, write the data to the new file, then close both files Chapter 13 – File-System Interface File Concept • The operating system maintains an open-file table to keep track of all the files that are "open" by processes at any given time • What file is open? • Read or write? • Which process(es) has opened the file? • What position in the file is the process(es)? Chapter 13 – File-System Interface File Concept • Some operating systems track file locking • Shared lock – Multiple processes can read from the file • Exclusive lock – Exactly one process can write to the file • What happens in a lock conflict? • Mandatory locking – Prevent processes from sharing an exclusive lock by blocking it until the lock is released. Used in Windows • Advisory locking – Leave it up to the user processes to obtain the lock safely. Used in Linux • Refer to chapters 6, 7, and 8 for how locking must be handled Chapter 13 – File-System Interface File Concept • Some applications use file extensions to identify files. The operating system can help by associating default applications to certain extensions. Chapter 13 – File-System Interface File Concept • Some files have a rigid structure, others are completely free-form. The operating system doesn't care but the applications that use the files do. • Free-form – No structure. Sequence of characters (text) or bytes (binary) • Simple record structure – Fixed or variable length lines • Complex record structure – Control characters can be added at intentional places to a simple record structure to make a complex structure. Other approaches use XML, json, proprietary formats, etc. • If the operating system had to keep track of all the different structure types, this would add overhead. Adding new structures (e.g. new file formats) would mean an update to the operating system every time to support them. Chapter 13 – File-System Interface Access Methods • A file must be loaded into memory before it can be used. The file can then be read with • Sequential access • Direct access • Other access methods Chapter 13 – File-System Interface Access Methods • Sequential access – This is the most common method • Operations required • Read next • Write next • Reset • Skip forward or backward (on most systems) Chapter 13 – File-System Interface Access Methods • Direct access – Read and write records in any order (typically used with knowledge about where the file's blocks are on disk). Ideal, for example, with databases who know exactly what portion of the data needs to be read • Operations required • Read block N • Write to block N • Since files are scattered in blocks across the disk, N is usually a number of blocks relative to the first block. A translation table maps logical blocks to physical blocks • Sequential access could easily be simulated with direct access Chapter 13 – File-System Interface Access Methods • Other access methods • Use indexes to blocks for quick lookup. Hold the indexes in memory Chapter 13 – File-System Interface Directory structure • Files are grouped in directories • The directory typically contains all the filenames and their identifiers • The identifier is used to look up all the other attributes Chapter 13 – File-System Interface Directory Structure • Basic directory operations • Search for a file • Create a file • Delete a file • List a directory • Rename a file • Traverse the file system Chapter 13 – File-System Interface Directory Structure • Directories are organized logically • Efficiency – Quickly find the files the user wants • Naming – Easily identify the files the user wants • Grouping – Group similar files together logically (e.g. Driver files, game files, etc.) Chapter 13 – File-System Interface Directory Structure • Directory structures • Single • Two-level • Tree • Acyclic-Graph Chapter 13 – File-System Interface Directory Structure • Single-level directory • Simplest to understand and implement, but it is the least useful • Naming problem – All files on the system must have a unique name • Grouping problem – It is not possible to group similar files together Chapter 13 – File-System Interface Directory Structure • Two-level directory • Resolves the naming problem but grouping is still a problem Chapter 13 – File-System Interface Directory Structure • Tree-Structured directories • Start with a root directory and maintain files and subdirectories below it • Use a flag (eg. 0) to signify a file and another flag (eg. 1) to signify a directory Chapter 13 – File-System Interface Directory Structure • Acyclic-Graph directories • Relax the tree structure to permit file and directory sharing • Links and shortcuts allow files to point to existing files Chapter 13 – File-System Interface Protection • Files need to be protected • From physical damage • We use techniques discussed in Chapter 11 • From improper access • Authentication – A valid username and password should be provided • Authorization – If a user is authenticated, is the user permitted to use a file? • Encryption – If the drive is copied or removed, the files should still be protected Chapter 13 – File-System Interface Protection • Common protection mechanisms • Read – Can the contents of the file be read? • Write – Can data be written or re-written to the file? • Execute – Can the contents of the file be loaded into memory and executed? • Append – Can data be appended to the file? • Delete – Can the file be deleted and space reclaimed? • List – Can the name and attributes be listed? • Attribute change – Can the attributes (metadata) be changed? Chapter 13 – File-System Interface Protection • Most operating systems employ protection based on the identity of the user • Access control lists (ACLs) map users to permissions • ACLs can be very large. Classifications allow Linux to condense access • Owner – The user who created the file • Group – A set of users who are sharing the file • Other – All other users • More complex permissions can still be achieved with ACLs. • Windows uses ACLs through the GUI Chapter 13 – File-System Interface Protection Chapter 13 – File-System Interface
Chapter 14 – File-System Implementation Fall 2023 Overview • File-System Structure • File-System Operations • Directory Implementation • Allocation Methods • Free-Space Management • Efficiency and Performance • Recovery Chapter 14 – File-System Implementation File-System Structure • A file system provides an interface between users and files • The file system manages • File structure • Allocating storage space • Recovering free space • Track the location of data on disk (Logical to physical mappings) • Interface between the operating system and secondary storage Chapter 14 – File-System Implementation File-System Structure • Operating systems provide many different file systems (Linux supports more than 130!) • Which file system to use depends on need • Performance? • Reliability? • Features? • E.g. A file system optimized for temporary storage will sacrifice reliability for performance • New file systems are being created all the time. FUSE (File system in user space) provide an interface to easily roll your own file system without editing kernel code Chapter 14 – File-System Implementation File-System Structure • File systems are composed of multiple layers • Layering reduces complexity and redundancy • However, layering adds overhead and decreases performance Chapter 14 – File-System Implementation File-System Structure • I/O control layer • Consists of device drivers and interrupt handlers • Manage I/O devices at the I/O control layer • Given commands like • read drive1, cylinder 72, track 2, sector 10, into memory location 1060 • Outputs low-level hardware specific commands to hardware controller Chapter 14 – File-System Implementation File-System Structure • Basic file system layer • Uses buffers and cache to store data as it is retrieved or stored • Given more generic commands like • retrieve block 123 • This layer manages I/O request scheduling (Chapter 11) Chapter 14 – File-System Implementation File-System Structure • File organization module layer • Understands files, logical address, and physical blocks • Translates logical block # to physical block # • Manages free space, disk allocation Chapter 14 – File-System Implementation File-System Structure • Logical file system layer • Manages metadata information • Translates file name into file number, file handle, location by maintaining file control blocks (inodes in UNIX) • Maintains file control blocks (FCBs) • Directory management • Protection Chapter 14 – File-System Implementation File-System Operations • File systems provide structures and operations to manage files and directories • File systems use several on-storage and in-memory structures • Operations are performed against one or more of these structures • On-storage structures are persistent • In-memory structures last until file system dismount or system reboot Chapter 14 – File-System Implementation File-System Operations • Common on-storage structures • Boot control block – (1 per volume) contains info needed by system to boot OS from that volume • Needed if volume contains OS, usually first block of volume • Otherwise, this may be empty • Volume control block – (1 per volume) contains volume details such as total # of blocks, # of free blocks, block size, free block pointers • Directory structure – (1 per filesystem) organizes the files Chapter 14 – File-System Implementation File-System Operations • Common on-storage structures (continued) • FCBs – (Usually 1 per file, although NTFS on Windows uses a master file table) Contains details about the file Chapter 14 – File-System Implementation File-System Operations • Common in-memory structures • Mount table – Storing file system mounts, mount points, file system types • Directory structure cache – Holds recently used directories • System-wide open-file table – contains a copy of the FCB of each file and other info • Per-process open-file table - contains pointers to appropriate entries in systemwide open-file table as well as other info Chapter 14 – File-System Implementation File-System Operations • Operations • E.g. To create a new file, a process calls the logical file system layer to create • The logical file system layer will allocate a new FCB, assign the FCB and the new file to a directory in the directory structure • The file organization module layer will find logical blocks for the file • The basic file system layer will map the logical blocks to physical blocks • The I/O control layer will write the data to disk Chapter 14 – File-System Implementation File-System Operations • Operations • E.g. To read the new file, a process calls the logical file system layer to open and read • The logical file system layer will search the system-wide open-file table • If it is already open, a per-process open-file table is created pointing to this entry and the entry is incremented • If it is not already open, search the directory structure for the file and add the FCB to the system-wide open-file table • Update the per-process open-file table to include read location in the file and access mode Chapter 14 – File-System Implementation File-System Operations • Operations • E.g. To close the new file, a process calls the logical file system layer to close • The logical file system layer will remove the per-process open-file table • Decrement the system-wide open-file table entry • If the open count is now 0, write any metadata to the directory structure and remove the entry Chapter 14 – File-System Implementation File-System Operations • Operations • E.g. (a) Open and (b) Read Chapter 14 – File-System Implementation Directory Implementation • The directory structure implementation affects efficiency, performance, and reliability • Linear list – file names with pointer to the data blocks • Simple to program • Time-consuming to execute. Using a cache can help • Linear search time • Could keep ordered alphabetically via linked list or use B+ tree Chapter 14 – File-System Implementation Directory Implementation Chapter 14 – File-System Implementation Directory Implementation • Hash Table – linear list with hash data structure • Decreases directory search time • Collisions – situations where two file names hash to the same location • Expand the hash table space when a collision occurs or • Use a chained-overflow hash table Chapter 14 – File-System Implementation Directory Implementation Chapter 14 – File-System Implementation Allocation methods • The file system assigns multiple contiguous sectors on physical disk to a logical block • Files consist of one or more blocks • Free space consists of free or unused blocks • The file system must keep track of these blocks effectively and efficiently • Three approaches to assigning blocks to files • Contiguous allocation • Linked list allocation • Indexed allocation Chapter 14 – File-System Implementation Allocation methods • Contiguous allocation - Each file occupies a contiguous set of blocks • Pro • Usually has the best performance (very little head movement) • Simple to implement. You just need the starting block and the number of blocks • Con • Harder to find space on disk • The entire file size needs to be known ahead of time • Fragmentation and compaction issues again (see Chapter 9) Chapter 14 – File-System Implementation Allocation methods • Contiguous allocation • The start and length are stored in the FCB Chapter 14 – File-System Implementation Allocation methods • Linked list allocation – A linked list of blocks • Pro • No external fragmentation or compaction • The entire file size does not need to be known ahead of time • Con • A small portion of the block needs to be reserved for the pointer to the next block. Clustering blocks together and pointing to the next cluster can help. • Random access is slow. To read a portion of a file, you need to traverse the chain from the start until the block you want Chapter 14 – File-System Implementation Allocation methods • Linked list allocation – A linked list of blocks • The start and end are stored in the FCB Chapter 14 – File-System Implementation Allocation methods • Indexed allocation – Each file has an index block. The index points to all the other blocks • Pro • No external fragmentation or compaction • Random access is very fast • Con • If the number of indexes exceeds the size of the index block, you need to employ multiple layers of index blocks. A 4KB index block with 4 byte pointers can store 1,024 pointers or a file size of 4MB. Two layers can hold 1,048,576 pointers or 4GB. Chapter 14 – File-System Implementation Allocation methods • Indexed allocation – Each file has an index block. The index points to all the other blocks • The index block is stored in the FCB Chapter 14 – File-System Implementation Allocation methods • Indexed allocation – Each file has an index block. The index points to all the other blocks • Some operating systems (e.g. UNIX/Linux) will combine direct and indirect blocks. • Small files will not use an index block. Large files will use multiple layers • Increasing the size of the block pointers raises the maximum file size • Using 4 byte (32-bit) pointers, the maximum file size without layering is 232 or 4GB • Most UNIX/Linux file systems support 8 byte (64-bit) pointers. ZFS supports 16 bytes (128-bit) Chapter 14 – File-System Implementation Free-Space Management • The file system must maintain a free-space list to track available blocks/clusters • When a new file is created, blocks from the free-space list are allocated and removed from the list • When a file is deleted, blocks are added back to the free-space list • Note: The free-space "list" may be implemented as a bitmap or a true list Chapter 14 – File-System Implementation Free-Space Management • Bitmap • Simply flag every block in the system as 0 (in-use) or 1 (free) • E.g. if blocks 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, 27 are free, represent this as: • 001111001111110001100000011100000 Chapter 14 – File-System Implementation … 0 1 2 n-1 bit[i] = 1 Þ block[i] free 0 Þ block[i] occupied Free-Space Management • Bitmap • Pros • Finding a free block (or set of blocks) is simple and efficient • Easy to implement bitwise CPU instructions to find free blocks • Easy to find contiguous blocks if that is required • Cons • A copy of the bitmap must be held in memory. 1TB disk with 4KB blocks requires 32MB in memory Chapter 14 – File-System Implementation Free-Space Management • Linked List Chapter 14 – File-System Implementation Free-Space Management • Linked list • Pros • A free block can be found at the head of the list • Cons • Traversing the list can be costly but a full traversal is rarely done Chapter 14 – File-System Implementation Free-Space Management • Linked list – Some efficient modifications • Grouping – A block stores a list of n addresses. The first n-1 blocks are free. The last block has a pointer to another group of n addresses • Counting – A block stores a value n to signify "the next n blocks are free" • Freeing blocks generally does not require erasing the existing data. This would use I/O unnecessarily • File systems will generally inform the device the block is free. HDDs and NVMs will erase the data either immediately, during a quiet period, or before the block is used again. Chapter 14 – File-System Implementation Efficiency and Performance • Disks represent the most significant bottleneck in system performance (even when using NVMs). The following are important considerations. • Unix spreads inodes across the volume. Files are stored close to their directory's inode. This reduces seek time • Keeping "last modified" and "last accessed" dates can tell the OS if the file needs to be loaded into memory or to be backed up to tertiary storage • Pointer size – 32-bit pointers use less space but limits file size to 4GB. 64-bit pointers use more space but allow for larger files. • (A device capable of holding 2128 bytes at the atomic level should weigh about 272 trillion kilograms) Chapter 14 – File-System Implementation Efficiency and Performance • Disks represent the most significant bottleneck in system performance (even when using NVMs). The following are important considerations. • Use a cache both on the disk and in memory. Most operating systems combine process and file data cache in a unified virtual memory Chapter 14 – File-System Implementation Recovery • Crashes and bugs can create inconsistencies on disk. A file system must detect and correct these issues • A file system can scan the metadata on each file to verify it makes sense. • This can take minutes to hours and should only occur during boot time • A status bit can indicate whether or not the entire file system is in flux or up to date. If the system reboots suddenly, the file system is still marked as "in flux" triggering a full consistency checker such as the fsck tool in UNIX/Linux Chapter 14 – File-System Implementation Recovery • Regularly scheduled backups can protect the file system • A typical backup schedule (e.g. weekly or monthly) • Day 1 – Copy all files to a backup medium. This is a full backup • Day 2 – Compare a file's last backup date with the last modified date. If the file has changed, back it up. This is an incremental backup • Continue this process up to day N. Then run a full backup again • Watch out for daylight savings time Chapter 14 – File-System Implementation Recovery • Regularly scheduled backups can protect the file system • To restore a file system • Restore the files from the full backup • Restore each incremental backup from every day • Instead of an incremental backup, it is possible to do a differential (or cumulative) backup. This is backing up any file that differs from the full backup. When a restore is required, you must only restore the full backup and the latest differential backup • Cold storage backup – Keeping a long-term backup of your data off-site and disconnected. Useful to protect against environmental hazards or malicious attacks Chapter 14 – File-System Implementation
Chapter 15 – FileSystem Internals Fall 2023 Overview • File Systems • File-System Mounting • Partitions and Mounting • File Sharing • Virtual File Systems • Remote File Systems • Consistency Semantics • NFS Chapter 15 – File-System Internals File Systems • General-purpose computers can have multiple storage devices • Multiple storage devices can be sliced into partitions • Partitions are assigned to one or more volumes • Each volume usually formatted into a file system Chapter 15 – File-System Internals File Systems • Common general-purpose file systems • UNIX/Linux – ext2, ext3, ext4, zfs, ufs • Windows – NTFS, FAT, FAT32 • Special-purpose file systems • tmpfs for temporary I/O • procfs for presenting process information as a file system in UNIX/Linux • Other file systems for specific workloads (e.g. Google File System) Chapter 15 – File-System Internals File-System Mounting • Just as files must be opened before they can be read, a file system must be mounted before it can be used • The operating system is given the name of the device and a mount point. The mount point is a location within a file structure (typically an empty directory) • The file system may be provided, or it may be automatically determined • If the file system is already mounted, the operating system must decide whether to allow multiple mounts or not • If the mount point is not empty, the operating system must decide whether to prevent the action or to obscure the existing files and directories until the file system is unmounted again Chapter 15 – File-System Internals File-System Mounting • E.g. Mounting a file system to a directory that is not empty Chapter 15 – File-System Internals Partitions and Mounting • A partition can be • Raw – No file system. Just blocks. Suitable for swap space or custom workloads (e.g. Databases, RAID) • Cooked – Contains a structured file system • Bootable partition – Contains enough code to find and mount other file systems. If it can understand multiple operating systems, then the system can be dualbooted • Root partition – Contains the operating system and the ability to mount other partitions Chapter 15 – File-System Internals File Sharing • User oriented operating systems must accommodate the need to share files • File permission metadata is kept in the FCB • The operating system uses the same permissions across all its file systems • Care must be taken when mounting a file system to another operating system (over the network or by physically plugging disks into other systems) • E.g. What if jsmith has user id 1001 on one system but user id 1002 on another? Chapter 15 – File-System Internals Virtual File Systems • To make using multiple file systems seamless, it is useful to separate file-system generic operations from implementation details • The virtual file system will then dispatch the correct operation to the file-system Chapter 15 – File-System Internals Remote File Systems • Early computing used protocols such as ftp to transfer files between machines • Later implementations employ a distributed file system (DFS) allowing remote file systems to be visible on local machines • File transfers across the Internet are now common using the http protocol Chapter 15 – File-System Internals Remote File Systems • DFS client-server model • Client – The machine seeking to mount the remote file system • Server – The machine sharing the local file system • The server must employ a mechanism to authenticate and authorize clients • The client typically sends user id information along with standard operations • Remote file systems need to account for more failure conditions than local file systems • Keeping state on both the client and server side can help identify when errors occur. This is also more secure, but it adds overhead. Chapter 15 – File-System Internals Consistency Semantics • Remote file systems must specify behaviour when multiple users share a file simultaneously • Process synchronization techniques seen in Chapter 6 would generate too much traffic on the network. A simpler approach is needed. • File session – All the actions between the open() and the close() call • The server may block client requests until the file session completes • Alternatively, the file system could be shared read-only Chapter 15 – File-System Internals NFS • Network File System (NFS) is a popular remote file system that employs a client-server model. • Windows more commonly uses common Internet file system (CIFS) • The NFS client mounts a remote NFS share. The share appears as though it is part of the local file system • NFS is designed to work in heterogeneous environments (different operating systems, different machines, different networking protocols, etc.) Chapter 15 – File-System Internals NFS • The NFS architecture Chapter 15 – File-System Internals NFS • The NFS mount protocol • The client requests a remote directory • The server verifies the client has permission to mount the directory including readonly or read-write permissions • If permission is granted, the mount is recorded in an export table. • The export table can be used to track all mounts, notify clients of downtime, revoke access if necessary, etc. Chapter 15 – File-System Internals NFS • The NFS remote operations protocol • A set of remote procedure calls (RPCs) to handle • searching for a file within a directory • reading a set of directory entries • manipulating links and directories • accessing file attributes • reading and writing files Chapter 15 – File-System Internals NFS • The NFS remote operations protocol • NFS version 3 is stateless so all operations must provide all arguments • This requires no additional overhead on the client or server side so it is faster but less secure • NFS version 4 is stateful. It has additional overhead but is more secure • All versions must safely write data to disk so there may be delays up to seconds or minutes depending on other clients and other file sessions Chapter 15 – File-System Internals
- Assistant
I have provided an overview of various aspects pertinent to operating systems and file systems based on the chapter headings and content summaries. Would you like to proceed with more detailed analysis or focus on a specific area for your study plan? If you have a specific exam template or additional guidelines, sharing that will help in tailoring the study plan to your needs.
- User
So these are all the lecture slides I need to study for my final exam tomorrow. I need you to analyse all these slides in great detail, and the following final exam template, and give me a comprehensive list of chapters and topics and subtopics, and then give me an action plan of how should I cover all this material for the exam tomorrow. Remember, the main focus is on the different algorithms and how to solve stuff by hand.
Final exam template: The CPSC 321 final exam will cover the syllabus content, excluding the material covered in the midterm syllabus. There will be a total of 8 questions on the final exam, with 6 based on specific algorithms or techniques and 2 conceptual questions. The exam will be three hours in duration.
- Assistant
Comprehensive List of Topics and Subtopics
Chapter 6 & 7 – Process Synchronization
- Overview of Race Conditions, Critical-Section Problem, and Synchronization Hardware Solutions
- Race Conditions
- Producer/Consumer Problem
- System Calls like
fork() - Issues with shared data (e.g., bank account example)
- The Critical-Section Problem
- Entry, Critical, and Exit sections
- "Solutions" that don't work (disabling interrupts, using flags)
- Conditions for a solution (Mutual exclusion, Progress, Bounded waiting)
- Peterson's Solution
- Hardware Solutions (Memory barrier, Atomic variables)
- Mutex Locks
acquire()andrelease()mechanisms- Spin-lock concept
- Semaphores
- Binary and Counting semaphores
wait()andsignal()concepts- Issues and usage examples
- The Dining Philosophers Problem
- Race Conditions
Chapter 8 – Deadlocks
- System Model (Resources, allocation, request/release methods)
- Deadlock Characterization (four conditions for a deadlock to occur)
- Methods for Handling Deadlocks (ignoring, preventing, avoiding, detecting and recovering from deadlocks)
- Deadlock Prevention Strategies (breaking the four necessary conditions)
- Deadlock Avoidance Algorithms (resource allocation graphs, banker's algorithm)
- Deadlock Detection (wait-for graphs and detection algorithm frequency)
- Recovery from Deadlock (process termination, resource preemption)
Chapter 9A – Memory Management (Basics)
- Background (Roles of memory management)
- Basic Hardware (CPU access, cache levels)
- Address Binding (Logical vs. Physical Address Space, Memory-Management Unit (MMU))
- Dynamic Loading and Linking
- Contiguous Memory Allocation (fixed and dynamic partitioning, fragmentation)
Chapter 9B – Memory Management (Paging)
- Basic Method (Frames, Pages, Page Table)
- Hardware Support (Page-table base register, Translation Look-aside Buffer (TLB))
- Protection (read-only, read-write)
- Structure (Hierarchical, Hashed, and Inverted page tables)
- Swapping
Chapter 10 – Virtual Memory
- Demand Paging and page replacement strategies
- Page Replacement Algorithms (FIFO, Optimal, LRU, LFU, MFU)
- Allocation of Frames
- Thrashing
Chapter 11 – Mass-Storage Structure
- Overview (disk structure and operation)
- HDDs and SSD/NVM comparison
- HDD Scheduling Algorithms (FCFS, SSTF, SCAN, C-SCAN)
- RAID Levels (0, 1, 5, 6, 10)
- Partitioning and Mounting
- Swap-Space Management
Chapter 13 – File-System Interface
- File Concept (attributes, operations, locking mechanisms)
- Access Methods (Sequential, Direct)
- Directory Structure (single, two-level, tree-structured, acyclic-graph)
- File System Protection (access control lists, permissions)
Chapter 14 – File-System Implementation
- File-System Structure (layers, types)
- File-System Operations (creating, reading, writing, deleting)
- Directory Implementation (linear list, hash table)
- Allocation Methods (contiguous, linked list, indexed)
- Free-Space Management (bit vector, linked list)
- Efficiency and Performance (caching, transfer speeds)
- Recovery (consistency checking, backups)
Chapter 15 – File-System Internals
- File Systems and Mounting (multiple volumes, file systems, mounting points)
- Partitions and Mounting (raw/cooked, boot/root partition)
- File Sharing (protocols, access control)
- Virtual File Systems (abstraction layer)
- Remote File Systems (client-server, DFS, NFS architecture and operations)
- Consistency Semantics (session, statefulness)
Action Plan
Day Before Exam
-
Review the Algorithms:
- Prioritize understanding over memorization. You should be able to demonstrate each algorithm by solving problems by hand.
- Practice Peterson's Solution, Banker's Algorithm, Page Replacement Algorithms (especially FIFO, LRU, and Optimal), and HDD Scheduling.
-
Understand Key Concepts Conceptually:
- Ensure you understand different memory management techniques, deadlock prevention, and file system operations.
- Review RAID levels and their use cases.
-
Practice by Solving Previous Exam Questions:
- If past exams or sample problems are available, use them to practice, especially focusing on solving problems related to algorithms.
Day of Exam
-
Quick Revision:
- Glance over your notes, especially formulas and key steps in the algorithms.
- Try not to learn new material, as it may overwhelm you.
-
Strategize for the Exam:
- Allocate the first few minutes to read through all the questions. Prioritize the ones you are most comfortable with.
- Keep track of time. Allocate it according to the weightage of the question.
-
Rest and Stay Calm:
- Ensure you are well-rested and hydrated for optimal performance during the exam.
Good luck on your exam!
- Overview of Race Conditions, Critical-Section Problem, and Synchronization Hardware Solutions
- User
from these slides, explain all the different types of algorithms to me with detailed examples.
- Assistant
Given the breadth of content covered in the lecture slides, it would be too extensive to provide detailed examples of every algorithm in a single response. However, I will discuss a few key algorithms from the topics provided:
Peterson's Solution (Process Synchronization)
Peterson's Solution is an algorithm used for achieving mutual exclusion in concurrent programming. It is a software-based solution and can be used for two processes. Here's a simplified explanation with an example:
Let's have two processes, P0 and P1, which share two variables:
int turn;// Indicates whose turn it is to enter the critical sectionboolean flag[2];// flag[i] indicates whether a process is ready to enter the critical section
Example code for two processes:
// Process P0 flag[0] = true; // P0 is interested turn = 1; // Set turn to the other process while (flag[1] && turn == 1) { // wait - do nothing } // critical section ... flag[0] = false; // P0 leaves the critical section // Similar code would be used for Process P1 with indices invertedExplanation:
- When P0 wants to enter the critical section, it sets its flag to true and gives the turn to P1.
- P0 will enter the critical section only if P1 has not raised its flag indicating interest, or if P1 did raise its flag, but the turn is given to P0 (P0 patiently waits if P1 is currently executing in its critical section).
- Mutual exclusion is assured as both processes can't be in the critical section simultaneously.
Page Replacement Algorithms (Memory Management)
Several page replacement algorithms determine which page to swap out when a page fault occurs, and the required page is not in memory.
FIFO (First In, First Out)
The FIFO algorithm is similar to how people queue for service - the one who came first is served first. The oldest page in memory is the one that will be replaced.
Example:
- Memory has 3 frames, and a program accesses pages in this order: 1,2,3,4,1,2,5,1.
- Initially, all frames are empty. We fill them with pages 1,2,3.
- When page 4 is accessed, a page fault occurs, and we replace page 1 (the oldest).
- The order of pages in memory is now 2,3,4. When the program accesses page 1 again, another fault occurs, replacing page 2, and so on.
LRU (Least Recently Used)
LRU tracks page usage over time, and when a replacement is needed, the page that has gone the longest since last use is replaced.
Example:
- With the same frame and page access order as before (1,2,3,4,1,2,5,1), LRU works like this:
- Start with empty frames and fill them: 1,2,3.
- Access 4, replace the least recently used (in this case, 1): 2,3,4.
- Access 1, replace the least recently used (in this case, 2): 1,3,4.
- Continue in this pattern for subsequent accesses.
Banker's Algorithm (Deadlocks)
The Banker's Algorithm is a deadlock avoidance method that simulates the allocation of resources to processes, ensuring a safe state.
Example:
- Suppose you're a banker with customers (processes) and units of cash (resources).
- When a customer enters, they declare the maximum units they might need.
- The banker only allocates resources if doing so leaves the bank in a safe state (i.e., they can still serve all customers, even in the worst-case scenario where all customers suddenly ask for their maximum needs simultaneously).
RAID Levels (Mass-Storage Structure)
RAID levels combine multiple disks into a single logical disk for redundancy or performance.
RAID 0 – Striping
Spreads data evenly across all disks without redundancy; if one disk fails, data is lost. Best for performance.
RAID 1 – Mirroring
Each disk has a duplicate copy. If one fails, its pair has the data.
RAID 5 – Striping with Parity
Data and parity (used for recovery) are spread across all disks. One disk can fail, and its data rebuilt from the remaining ones.
RAID 6 – Striping with Double Parity
Similar to RAID 5, but with two parity blocks. Two disks can fail without data loss.
If you need a more in-depth understanding of any particular algorithm or want to know about an algorithm that I haven't covered, please let me know, and I can provide a more detailed explanation.
- User
explain all of the page replacement algorithms in detail
- Assistant
Page replacement algorithms decide which page in memory should be replaced when a page fault occurs, and there is no room for the new page. They are crucial for the operation of virtual memory in operating systems. Here is an overview of several common page replacement algorithms:
FIFO (First-In, First-Out)
FIFO is the simplest page replacement algorithm. It maintains a queue of pages in memory in the order they were loaded. When a page fault occurs, FIFO replaces the oldest page in the queue.
Example: Assume a memory system with 3 page frames and the following page reference string:
Reference String: 1, 3, 0, 3, 5, 6
- At start, all frames are empty.
- Page 1 is loaded into frame 1, page 3 into frame 2, and page 0 into frame 3.
- When page 3 is accessed again, it's already in memory, so no replacement happens.
- Accessing page 5 causes a page fault; FIFO replaces page 1 (the oldest), so memory now holds 3, 0, 5.
- Next, page 6 causes another fault and replaces page 3 (next oldest), resulting in 0, 5, 6 in memory.
Optimal Page Replacement
The optimal algorithm replaces the page that will not be used for the longest period in the future. It is the algorithm that produces the fewest possible page faults. However, it's mostly theoretical since it requires future knowledge of the reference string.
Example: Using the same reference string and frame size:
Reference String: 1, 3, 0, 3, 5, 6
- Initially, frames are filled with 1, 3, 0.
- The next access is 3, which is already present.
- For the next fault (accessing 5), we replace page 1, because it won't be needed soon.
- Accessing 6 results in replacing page 0, because 3 will be used next.
LRU (Least Recently Used)
LRU tracks when each page in memory was last used and replaces the least recently used page upon a page fault. It is based on the locality of reference principle.
Example: Using the same reference string and 3 frames:
Reference String: 1, 3, 0, 3, 5, 6
- Start with 1, 3, 0.
- Accessing 3 is a hit. The LRU order is now 1, 0, 3.
- Accessing 5 replaces page 1 since it's the least recently used. New state: 0, 3, 5.
- Accessing 6 replaces page 0. New state: 3, 5, 6.
LFU (Least Frequently Used)
LFU keeps track of how often pages are accessed. It replaces the least frequently used page upon a page fault.
MFU (Most Frequently Used)
Based on the argument that the page with the smallest count was probably just brought in and has yet to be used, MFU replaces the page with the highest frequency count.
Clock (Second Chance)
Clock is a compromise between FIFO and LRU. Pages are kept in a circular buffer similar to FIFO, but each page is given a second chance before being replaced.
Example: Using a reference string and 3 frames with a "use bit":
Reference String: 1, 3, 0, 3, 5, 6
- Start with 1, 3, 0 with use bits set to 0.
- Accessing 3 sets its use bit to 1 instead of replacing it.
- On next fault (accessing 5), the clock algorithm looks for the first frame with use bit 0. It finds page 1, replaces it, and sets 5's use bit to 1.
- For the next fault (accessing 6), the first page with use bit 0 is page 0. It's replaced. If all use bits had been set to 1, the algorithm would clear the use bit and move on, essentially giving each page a second chance.
In practice, operating systems often use combinations or variations of these algorithms. LRU is very common for its balance of performance and practicality, although it requires additional tracking of page references. Algorithms like Clock and LRU-approximates can deliver near-LRU performance with less overhead, making them suitable for real-world systems.