CMSC 412 Introduction: TA: Yezhou Yang UTA: Keven McGehee Style: - vocabulary. much of education is about being able to talk to other educated professionals. - whiteboard and emacs console. loosely set schedule. - diagrams from the whiteboard will not appear in course notes. - course notes are intended to help refresh memory, distinguish important from not; *not* to replace class - cell phone quiz threat. maybe I'll make good on it. - if you do not complete all the assignments, you will fail (have failed). - it's an observation, not a rule. - late policy: 3 days, 30%. your responsibility: - slow me down; connect what you understand to what I'm trying to explain. - read the textbook, cover to cover. (think about it) - start assignments early. - ask for help from me or the TA's before you're in too deep. syllabus project - allegedly brutal. - debugging difficult. - linuxlab might be necessary. (working to make it easier to run on your PC/Mac) - C. unauthorized and unfair collaboration policy - don't share code. - don't print it. - don't mail it. - don't show it. - xlock your screen. - wikipedia is legal; not always right, paraphrase and be sure to answer the question I ask, not the question the text you read answers. textbook - s.g.g. dinosaur, 8th ed. I'll assign exercises from the book. Find the current edition or a friend with it. - ignore value judgements: the authors seem to use "rich features" in lieu of actual description. - ignore microsoft windows sections unless you're interested (I don't care). - why? "undocumented" calls. the "registry". legacy ugliness. you'll learn it if you need to. it isn't free (as in beer, speech, or lunch) - challenge: separating invariant concepts from specific implementations. - read summary section twice (don't highlight in the text). - skim first chapters; it gets covered again. Operating systems. what they do - manage devices. resources, disk blocks, memory, all hardware bits. - serial ports, network adapters, display adapters, - disk adapters, tape drives, keyboard, mouse, - using DMA, interrupts, programmed I/O, depending on the device. - manage processes. communication, syncrhonization between them. scheduling. preemption. - locks (semaphores and mutexes), shared memory, pipes. - priorities, I/O. interactive and background applications. - provides applications with an abstract interface to the machine: isolated, easier to program. - as if memory is infinite and contiguous. - as if the app is the only one on the machine. - as if disks had files and folders. - as if character-at-a-time devices took buffers at a time. what's exciting - most important piece of software on the machine. it fails, BSOD. if buggy, all security is lost. - an infinite loop in the OS makes it go poof. - most powerful piece of software on the machine. it can do anything. - write anywhere in memory, write any device. - lots of choices for how to maintain the illusions: - which processes go first, which disk blocks are first, how much memory to allocate, - tricky problems - priority inversion. deadlock. atomic actions. using SMPs, multi-core. what we won't talk about - GUIs. X, Windows, Cocoa are all nice libraries, but the OS usually hands the display over to the gui shell (xserver, window manager) and tells it to have fun. Folders and finder windows are pretty representations of directories and files. programming assignment zero (PA0) grades.cs.umd.edu -> doles out class accounts ### maybe: submit.cs.umd.edu -> accepts tunins. https://scriptroute.cs.umd.edu/412s11 forum System call description - needs help from the os === lecture 2 system call vs. calling system() theyre different. system() is ironically not a system call. what is a *process* ? running instance of a program things it has - memory / address space - text segment (where the code goes) - heap - shared libraries - threads - stack - registers - eax and other general purpose registers. - stack pointer - instruction pointer / program counter - may have user-level and kernel-level threads. - kernel-level threads will have some help from the operating system at splitting memory. - user level threads have to save register state manually using setjmp / longjmp. - resources - files and sockets - allocation of cpu time What is a *file*? - named array of bytes, likely stored persistently. - with associated metadata like access time, creation time, etc. owner / permissions likely. What does a *real-time operating system* do? - processes consist of tasks that have deadlines - scheduler runs tasks in order of (earliest) deadline (earliest deadline first) - you might not be able to run stuff What is a *shell*? - program that interpret commands, often to execute programs - start and control jobs. - manage stdin / stdout / stderr. What happens when a device receives data - for example, a network interface card receiving a frame - nic will collect the data into a buffer (it comes fast) - nic will trigger an interrupt to inform the processor (alternative, you could poll) (alternative, the nic could coalesce interrupts) - interrupt causes processor to transfer control (ultimately) to the driver - driver talks to device to read the data (as many packets as there are) (may split handling of an interrupt into top- and bottom- half) - return to whatever was going on before the interrupt. Aside: in the context of GeekOS - disabling interrupts ensures that you code runs atomically (but may diminish responsiveness) --- Lecture 3 Review - interrupts analogous to signals. programmed io operations analogous to system calls interrupts are asynchronous notification, just as signals are asynchronous interrupts may be blocked, just as signals may be blocked. interrupt handlers should be short, just as signal handlers should be short (not invoke system calls) interrupts are many (one per "device" of sorts), just as signals are several (one per event) man 2 sigaction describes signals (q: why the 2?) - processes and files (and many other operating system concepts) are mere data structures to the running program that is the kernel. processes have associated memory, resources, and one or more contexts (threads) files have associated names, backing storage (e.g., disk blocks), and other metadata Homework grading Please be patient as I break-in the TA with the new system. In particular, grading of one question may not represent "complete" grading of an assignment, so if you're wondering why you "have a zero" it may be that. If something looks dumb, feel free to tell me, but I may just say "yeah". Project issues Be careful to initialize all variables. The submit server is unforgiving of uninitialized variables that might go unnoticed on your machine. The rules: - statics and globals are initialized to zero by the compiler. - stack variables and malloc'd structures have whatever happened to be in memory last, unless you explicitly initialize. Some secure services (those without a real budget) use certificates signed by the department. To trust the department as a whole: http://www.cs.umd.edu/faq/rootcert/ Batch vs. Timesharing batch: run to completion or - efficient in that you don't have to switch - you don't have to hold more than one process in memory at a time. - modern batch systems manage clusters of pcs. timesharing: run a program for a little while, then switch to the next one. - advantage: interactivity - can take better advantage of idle resources. performance isolation - hard to keep processes separate in terms of performance (sometimes there are lots of processes competing for disk/cpu, sometimes not). resource limits - may decide how much of a resource can be consumed by a process in advance. Microkernel Mach is the ideal form of microkernel. Darwin (OS X) tries to do microkernel things. Kernel modules where do they hook in? system call table, interrupt table, maybe a kernel process. what can they provide? filesystems, protocols, device drivers... Virtual machine - software that provides an interface of a physical machine (without being a physical machine) - privileged instructions trap and are emulated. - non-virtualizable instructions have to be rewritten. Also, paravirtualization - virtual machine where the physical doesn't really exist (fake devices with simple interfaces or complex behavior) Blocking vs. Non-blocking IO what happens to a process tiny dumb web server bind listen while(1) { accept // blocks until a client connects read (the request) // blocks until a client sends a request write (the response) close } what happens when you have more than one client at a time? - screw em, they can wait. - fork - thread pool - select/poll - ask the kernel which sockets won't block. - use non-blocking calls what happens when you block on one of these calls? the process data structure goes into a different queue than the run queue. it goes into a list of processes waiting on *something* to happen. case-by-case what that something should be. Diagnostics strace / dtruss as in homework 1. might use strace to determine when malloc shifts from calling brk() to calling mmap() ulimit core (and resource limits in general) -- Lect 4 (2/8) P0 - Please have a reasonably responsive email on file. (in the univ db) - Difficulty in P0 is a bad sign. Find a scheme to be prepared for the rest of the projects. P1 - I (personally) have a deadline on 2/18. Set your own deadlines. Process states running runnable (ready) waiting (stopped) zombie (terminated) running to runnable processor is interrupted. timer interrupt - "8259 chip" that the operating system configures to send an interrupt on a periodic basis. at some point in the handling of the interrupt, (optionally the scheduler decides in what order to run the tasks) the dispatcher sets a new process onto the processor. the old one goes back into the run queue. running to waiting blocking read. blocking write. blocking anything else. sleep (nanosleep, usleep). wait, (waitpid) running to zombie exit(). distinction between scheduler and dispatcher. scheduler has the brains. dispatcher does the work. The PCB Holds everything. linux-kernel include / linux / sched.h has struct task_state.... many many fields. - pid (process id) - parent pid (or a reference to that) - memory / address space - threads and their register state - resources, incl file descriptor table. - scheduler data, (how many cycles has it used... stuff to compute priority) Scheduling and Preemption. short term - of the processes in memory, who gets the processor. medium term - kick some processes out of memory, so that the ones that remain can make progress. long term - decide which processes can even start. (batch processing like) Why have more than one process "running" at a time? (or have more active processes than processors) - ridiculous cpu-bound process that will take forever, and you want to do little tiny tasks at the same time that won't really affect the overall runtime of the behemoth process. -> preview of multi-level feedback queue scheduling. - different processes are likely to use different resources... by running them at once, each can fill in -- one uses the cpu while the other waits on a disk. While in the space of processes, how are they created and destroyed? means by which a process can create a new process: Spawn / Sys_Spawn (geekos) fork() what is the first process? shell.exe init - starts the daemons - processes that need no console, that run in the background. - among those daemons is getty - binds a tty (the kernel's representation of a console, which may be virtual) to a login/shell process. - inherits orphans - processes that have no parent to wait() on them. implementation of system() int system(const char *command) { pid_t pid = fork(); // basically an int. if(pid == 0) { // child // using system, we exec /bin/sh to run the command. char *arguments[4]; arguments[0] = "sh" arguments[1] = "-c" arguments[2] = command; //the argument to system arguments[3] = NULL; execv("/bin/sh", arguments); } else if(pid > 0) { // parent int exit_status; waitpid(child, &exit_status, 0); return exit_status; } else { // oh noes! return -1; } } === Lecture 5 (2/10) svn diff | less ^^^^ so that you do not hate yourself. which is a lovely segue into pipes! IPC, pipe, popen, ... Interprocess communication basics we want separate processes to: - isolate faults. - having many threads take advantage of extra cores / resources, provide responsiveness. - don't need to restart all (including unrelated) stuff for an update. - add features (new programs) - privledge separation - some processes might be run "as root" or unrestricted. - special process to manage resources... accept requests from short-lived clients why share between processes? - potential for a process (active entity) to guard access to information being shared between two users. - compose functionality between programs to suit the user. - unix philosophy is that the programs do something very very small, and that the user can compose what the user wants from that. - an example would be 'grep "1" /etc/services | awk '{print $2}' | sort | uniq' - less in keeping with the philosophy 'grep "1" /etc/services | awk '{print $2}' | sort -u' sharing probably requires synchronization why not just use threads? - threads won't give us the composition / update or the isolation why not just share files? - they are a means of exchanging data between programs - potentially less efficient - semantics involve writing to the disk, which might be unnecessary (maybe not always or immediate, but very likely at some point) - space on the disk / cleanup - still need to figure out synchronization - not really clear what happens when someone read()s a file you're writing to. - really unclear what happens when more than one process writes. - probably not good if immediate interaction is expect - doesn't isolate the processes from others / keep the communication secure. - need a system call to read and write (though pipes and sockets will have the same) Methods x lame (file) shared memory need help from the kernel because the kernel is in charge of our address space. need extra help from the kernel because we're going to have to make these pages special (pinned) (probably). some memory pages are already (sort of) shared read-only. shm{get,at,dt,ctl} system calls. have to be concerned with synchronization if there are multiple writers. message passing elaborate scheme generally associated with microkernels in which the kernel routes messages, potentially to multiple subscribers so that contained messages can notify other processes. pipe two endpoints. mostly one-direction (but not necessarily) - if you created the pipe, and then had fork fork, each byte would still only be read once. - pipes are byte-oriented, not message-oriented, so the size of the write does not influence the size of the read. - and you might be screwed because it's unlikely that the message remains whole. pipe() Lecture 6 (2/16) --- announcement: HW3 due thursday 2/24 announcement: Midterm tuesday 3/15. it's just a midterm. // in progress... // return a file descriptor for reading. int popen_r(const char *command) { int fds[2]; pipe(fds); // no error checking for me. // Data written to fildes[1] appears on (i.e., can be read from) fildes[0]. (from the man page) pid_t pid = fork(); // basically an int. // both parent and child have the same file descriptors if(pid == 0) { // child // using system, we exec /bin/sh to run the command. close(STDOUT_FILENO); // 1. close(fds[0]); // we will not need this. // int dup2(int oldfd, int newfd); // finish here. dup2(fds[1], 1); close(fds[1]); // we don't need another one here. char *arguments[4]; arguments[0] = "sh" arguments[1] = "-c" arguments[2] = command; //the argument to system arguments[3] = NULL; execv("/bin/sh", arguments); } else if(pid > 0) { // parent close(fds[1]); // we don't need the child's end of the pipe. return fds[0]; // return the reading side of the pipe. } else { // oh noes! return -1; } } popen() implementation (look up) what happens if the parent stops reading? child blocks in the call to write. what happens if the child writes to a dead parent? sigpipe. write will fail. EPIPE fd is connected to a pipe or socket whose reading end is closed. When this happens the writing process will also receive a SIGPIPE signal. (Thus, the write return value is seen only if the program catches, blocks or ignores this signal.) Sockets and additional challenges of communicating across machines. Unix sockets overview man 7 unix endpoint identifier is a path name. IP sockets overview man 7 ip endpoint identifier mostly an ip address, usually with tcp or udp port. Why one or the other? unix socket will be quicker ip will let you communicate across different machines. - but then you have to worry about data (integer) representation. unix socket will do crazy things like pass file descriptors. Basic functions. socket() <- allocates a new socket (can be either unix or ip) if server (accepting incoming connections) bind() <- assign yourself an endpoint. in IP - I want to be port 80, i.e., be a web server. in unix domain sockets, that will be a path that your clients know about. listen() <- say you want to listen for incoming connections (prepare to accept... let others connect to you. accept() <- actually get a new connection as initiated by the client. if a client: connect() <- connect to the server at the designated endpoint. then: read/write: - generally for byte-oriented protocols send/recv - something in between. (I don't use.) sendmsg/recvmsg - generally for message/datagram-oriented/connectionless protocols and usually, since you'll have so many clients to talk with or something else to do: select() or poll() - wake me up after so long or when any of a set of sockets is ready. and my personal favorite: shutdown() - like close, only you get to choose whether to close just for reading, just for writing, or both. (but the fd isn't reclaimed.) You can, but probably shouldn't, call fdopen to create a FILE * from an fd. that lets you call fread, fwrite, fgets, fprintf... but... cause havoc with select(), because of the interaction with buffering. (e.g., there can be data to read, but fread() may want to read more data than is available.) There are sockets that are: datagram - sort of like messages, sometimes unreliable. stream - like an (ordered) array of bytes, usually reliable. Threads Why use threads? exploit the parallelism within a program. (use more processors or more resources if there's a mix of requirements.) don't want the isolation of separate processes have lots of shared state between different contexts. would just waste performance to interact all tasks have the same text segment (same program) If you kill a process, does that kill all the threads? - kills all the threads? yes, because it's the same process, and you don't want to have to whack every thread in the process individually when your process goes haywire. - kill()s all the threads? no. signals are delivered just once to one thread. which thread is up to the os, and it's probably not what you wanted... unless somebody called sigprocmask a lot. - so be afraid. User threads - setjmp, longjmp. options - many user threads, and just one kernel-level thread / process. many user threads, and multiple kernel-level threads / processes. (as many processes as processors, but yet more concurrent tasks) Thread pools An attempt to fix the number of threads, reuse them. - belief that thread creation is somewhat expensive. don't want to do it all the time. (still cheaper than forking a process, but still) - belief that too many threads is a really bad idea. (thrashing) (so you don't want arbitrary discretion on forking a thread for every little new task) Lecture 8 2/22 0.) signals in geekos (quickly) 1.) review of 7 with Hollingsworth. concepts and terminology round robin multi level feedback queue goals: fairness (or priority) "predictability" responsiveness (response time) utilization / efficiency (use all the resources) / performance / throughput round robin is relatively poor for responsiveness. demoting compute-bound processes in multi-level provides responsiveness / limits response time long quanta for these long running jobs. in the long quantum, the processor-bound task can (maybe) get a lot done. multiple processors: pretty much the same *except* processor affinity - desire of a process to stay on a processor. example - several long running jobs on two processors: likely partition the set so that each process has a preferred processor. example - one long running and several interactive ones... long running guy is going to settle on a processor and the interactives will probably take the other one just by what's available at the time. priority inversion jobs with low priority beat those with high priority. in general, whenever a low-priorty job gets in the way of a high priority job. usually in the context of synchronization operations. e.g. low priority job holds lock, med priority job runs, high priority job blocks on the lock. typical solution is for the low priorty guy to (temporarily) "inherit" the high priority of the guy waiting on him. lottery scheme. high priority guys get more tickets. shortest job first scheduling "algorithm" unattainable ideal / "optimal" for response time. 2.) continued threading Scheduler activations Want the flexibility of user-level threads, but the parallelism of kernel-level threads. Scheduler activations are a scheme for c ooperation between a user-level thread scheduler thread and the kernel so that both can do their jobs efficiently. Threads on linux clone flags in the clone man page. relevant / notable ones: clone_vm clone_fs clone_sighand clone_files pthread creation on linux, courtesy strace: mmap(NULL, 8392704, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_32BIT, -1, 0) = 0x48010000 mprotect(0x48010000, 4096, PROT_NONE) = 0 clone(child_stack=0x48810260, flags=CLONE_VM|CLONE_FS|CLONE_FILES|CLONE_SIGHAND|CLONE_THREAD|CLONE_SYSVSEM|CLONE_SETTLS|CLONE_PARENT_SETTID|CLONE_CHILD_CLEARTID, parent_tidptr=0x488109e0, tls=0x48810950, child_tidptr=0x488109e0) = 18964 Threads elsewhere (fancy names for thread pools): Mac "Grand Central Dispatch" setup "dispatch queues" that include queues of tasks that will be executed, the underlying library will take care of the machinery to execute a bounded number of threads to handle your tasks. Windows "IO Completion Port" same thing, except the new tasks are i/o events. (data being ready for reading). Synchronization 1.) avoid Race conditions 2.) avoid deadlock in the process. What's a race condition? two threads attempt to modify the same resource... undesirable outcome caused by a non-deterministic ordering of concurrent operations, at least one of which is a write (or a side-effect, like printing output to a device) Why do we care about race conditions? because they're bad. because they're hard to debug. because they happen. (except when run under the debugger) because they can emerge under heavy load (with many concurrent tasks or when tasks take longer than normal) Geekos disables interrupts to provide critical sections. BEGIN_INT_ATOMIC / END_INT_ATOMIC DisableInterrupts() / EnableInterrupts() Why is this lame? hard to understand / follow -- have to remember what state you're in at the time (some are called with them enabled... some disabled...) can't be preempted. interrupts that occur get posted but not handled... so your device could be unhappy by being ignored. The CRITICAL SECTION PROBLEM - a) only one program can be in its critical section at a time. b) "progress" - processes outside their c.s. can't block those that are waiting. c) bounded waiting - can't have to wait for an indefinite amount of time to get the lock. d) can't assume anything about speed of cpus. Lect 9 2/24 HW due. volatile keyword in C - don't optimize loads and stores, make sure this variable has a place in memory and that that place is kept current. (and you load from it whenever you want to read) register keyword - hint to the compiler to do the opposite... this variable doesn't need a place in memory, won't last long, etc. Two more reasons disabling interrupts is lame: a) can't do it in applications. (lest it be abused.) b) useless for multi-processor kernels. (the other proc keeps going regardless) Simplistic epic fail scheme for locking: a "lock" variable. lock = 1 if it is held lock = 0 if it is not. to acquire the lock: while(lock != 0); lock = 1; to unlock: lock = 0; Thread A: Thread B top: load lock into eax load lock into eax bnz eax, top bnz eax, top store lock, 1 store lock, 1 Alternation scheme for locking, sort of works: turn = 'A' Thread A: lock: while(turn != 'A') unlock: turn = 'B' Thread B: lock: while(turn != 'B') unlock: turn = 'A' a thread not waiting can prevent a thread that is waiting from entering its critical section. but otherwise kinda works. Peterson's solution: int turn bool flag[2] lock: me = 0 him = 1 (would be flipped? reversed? for the other guy) flag[me] = true turn = him while(turn == him && flag[him]); unlock: flag[me] = false Peterson's solution doesn't work for more than two. Bakery algorithm: (wikipedia-based) // declaration and initial values of global variables Entering: array [1..N] of bool = {false}; Number: array [1..N] of integer = {0}; 1 lock(integer i) { 2 Entering[i] = true; 3 Number[i] = 1 + max(Number[1], ..., Number[N]); 4 Entering[i] = false; 5 for (j = 1; j <= N; j++) { 6 // Wait until thread j receives its number: 7 while (Entering[j]) { /* nothing */ } 8 // Wait until all threads with smaller numbers or with the same 9 // number, but with higher priority, finish their work: 10 while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { 11 /* nothing */ 12 } 13 } 14 } 15 16 unlock(integer i) { 17 Number[i] = 0; 18 } 19 20 Thread(integer i) { 21 while (true) { 22 lock(i); 23 // The critical section goes here... 24 unlock(i); 25 // non-critical section... 26 } 27 } Hardware help: tsl and xchg xchg - exchange. (atomically) swap register value with value at an address in memory tsl - test and set lock. (atomically) set the value in a location in memory to 1, return the value that it used to have. (if it was zero, that means you just acquired the lock... if it was one, you didn't do anything.) if you xchg with the value of 1, you get the same behavior as tsl. Spinlock using xchg (wikipedia based implementation using atomic xchg instruction) lock: # The lock variable. 1 = locked, 0 = unlocked. dd 0 spin_lock: mov eax, 1 # Set the EAX register to 1. loop: xchg eax, [lock] # Atomically swap the EAX register with # the lock variable. # This will always store 1 to the lock, leaving # previous value in the EAX register. test eax, eax # Test EAX with itself. Among other things, this will # set the processor's Zero Flag if EAX is 0. # If EAX is 0, then the lock was unlocked and # we just locked it. # Otherwise, EAX is 1 and we didn't acquire the lock. jnz loop # Jump back to the XCHG instruction if the Zero Flag is # not set, the lock was locked, and we need to spin. ret # The lock has been acquired, return to the calling # function. spin_unlock: mov eax, 0 # Set the EAX register to 0. xchg eax, [lock] # Atomically swap the EAX register with # the lock variable. ret # The lock has been released. Semaphores - P and V operations decrement and increment wait and signal down and up proberen and verhogen Semaphore has a value (or a counter) and a queue. Your model can be that the counter never becomes negative. Or that the counter attains a negative value based on the number of threads that are waiting. (each seems fine to me) basic concept version of the semaphore (won't work literally.) signal / V: counter++; wait: atomically { while(counter <=0); counter--; } --- not busy waiting scheme. wait: (may totally not work.) if(sem->counter>0) { /* we're good, it's ours */ counter--; } else { /* we must block. */ Add_To_End_Of_Thread_Queue( sem->queue, g_currentThread ); } signal: if(counter == 0) { /* maybe somebody is waiting! */ look at sem->queue. if there's something there move the head of sem->queue into the runnable queue... else counter++ } else { /* nobody is waiting */ counter++; } producer / consumer problem. a.k.a. bounded buffer. roughly two processes: producer creates data into a buffer of finite size consumer eats data from that buffer. producer blocks if buffer is full. consumer blocks if buffer is empty. three semaphores likely. (or two semaphores and a mutex) one for the producer to block on one for the consumer to block on one to guard concurrent access to the shared data structure. buffer empty. producer is ready to go... consumer is blocked. Semaphore_Of_Empty_Buffers.counter = 10 empty buffers! Semaphore_Of_Full_Buffers.counter = 0 full buffers. consumer: do { wait(Semaphore_Of_Full_Buffers) wait(Semaphore_Of_Buffer_Access) i = get_thing_from_buffer() signal(Semaphore_Of_Buffer_Access) signal(Semaphore_Of_Empty_Buffers) do our thing with i. } while(I'm hungry) producer: do { i = make_our_thing() wait(Semaphore_Of_Empty_Buffers) wait(Semaphore_Of_Buffer_Access) put_thing_into_buffer(i) signal(Semaphore_Of_Buffer_Access) signal(Semaphore_Of_Full_Buffers) } while(I have stuff to produce) Semaphores do not care who calls wait and who calls signal. Reader-Writer locks. want to permit concurrent reads. (shared read access) but a write should have exclusive access. two options. 1 readers can't be stopped by a waiting writer. 2 writers can't be stopped by an endless stream of readers. two semaphores. S_writing_mutex - the "exclusive" access. either the writer holds it or the readers (collectively) hold it. S_reader_mutex -- held by the readers when updating the count of active readers. num_active_readers -- the readers will keep track of this counter. writer operation: wait(S_writing_mutex) do the write signal(S_writing_mutex) reader operation: wait(S_reader_mutex) num_active_readers++; if (num_active_readers == 1) wait(S_writing_mutex) signal(S_reader_mutex) perform our read wait(S_reader_mutex) num_active_readers--; if (num_active_readers == 0) signal(S_writing_mutex) signal(S_reader_mutex) option 2 variant (writer can't be blocked by an endless stream of readers. S_extra - one more semaphore that a blocked writer will hold while blocked so that the reader gets stuch. writer operation: wait(S_extra) wait(S_writing_mutex) do the write signal(S_writing_mutex) signal(S_extra) reader operation: wait(S_extra) wait(S_reader_mutex) num_active_readers++; if (num_active_readers == 1) wait(S_writing_mutex) signal(S_reader_mutex) signal(S_extra) perform our read wait(S_reader_mutex) num_active_readers--; if (num_active_readers == 0) signal(S_writing_mutex) signal(S_reader_mutex) Condition Variables (and then shortly, Monitors) adds a "signal all" operation everybody who is waiting wakes up. Monitors based on the assumption that synchronization is hard and programming languages make things easy. guard functions/methods with a wait and signal. function() { grab mutex do stuff release mutex } -- Lect 10 Mar 1 HW 3.5, the cpu scheduler, due Mar 11. Handout online. Site needs a rewrite... should be up thursday. May add -pg to the compile line for profiling... if you want. No crazy data structure libraries (though a different data structure for the run queue could help) HW 4 (short) due Mar 15 and midterm day. beware. (the ides of march) Monitor- and Condition-Variable-based Producer/Consumer monitor TheMonitor { function() { grab mutex do stuff release mutex } function2() { grab mutex do stuff release mutex } } monitor TheBoundedBuffer { int count_of_buffers_used; int number_of_buffers_total; condition_variable cv_not_full, cv_not_empty; put_something_in_buffer( thing ) { # want to wait if all the buffers are full. while( count_of_buffers_used == number_of_buffers_total) wait(cv_not_full); buffer_of_things.add( thing ) count_of_buffers_used += 1 if( count_of_buffers_used == 1 ) signal(cv_not_empty); } take_something_from_buffer() { while( count_of_buffers_used == 0) wait(cv_not_empty); thing = buffer_of_things.remove count_of_buffers_used -= 1 if( count_of_buffers_used == number_of_buffers_total - 1) signal(cv_not_full); return thing } } signal-and-wait - when you signal a condition variable, the other guy gets to run (and you wait for him to finish. signal-and-continue - when you signal a cv, you get to finish out your execution, and then the other guy gets to wake up. Implementation of monitors using semaphores. small challenge: have a queue of threads that have called signal() and are in a signal-and-wait mode. the guy who signaled will wait on a "next" semaphore. Procedure() { semaphore_wait(mutex) [[ body of the procedure ]] if( count_of_threads_waiting_on_next > 0) semaphore_signal(next) else semaphore_signal(mutex) } cv_wait { cv_count += 1 if( count_of_threads_waiting_on_next > 0 ) semaphore_signal(next) else semaphore_signal(mutex) semaphore_wait(cv_sem); cv_count -= 1 } cv_signal { if cv_count > 0 { count_of_threads_waiting_on_next += 1 semaphore_signal(cv_sem) semaphore_wait(next) count_of_threads_waiting_on_next -= 1; } } Deadlock more than one thread, stuck... one thread gets a lock and never gives it up... or stupid thread shoots itself in the foot. Four conditions of deadlock 1. mutual exclusion - can't share, if you could share, no one would ever have to wait. 2. hold and wait - you're getting a set of resources, and get them one at a time. 3. no preemption - OS can't take your resources away. 4. circular wait - there's a cycle in the "waits for" graph. Three ways of fixing deadlock: prevention - get rid of one of the four conditions avoidance - ridiculously complicated reservations. detection - recognize circular wait when it happens... (kill one of the tasks involved.) March 3 Prevention circular wait - total order scheme. (or just one lock.) hold and wait - 1) if you have multiple locks, cool, but no process can have more than one. 2) if you need more than one resource, get them all at once. no preemption - add preemption. if your resources can be stolen, might do so. (maybe the resource involved is memory, and the kernel tries to provide a successful return from malloc. if it tries to provide this success at the cost of maybe blocking the process, we could imagine it doing this for two processes, both interested in the same resource (a page of memory), each preventing the other from making progress. if, otoh (on the other hand), we can steal a page back from the process, (maybe by paging it out to disk), then we can give a page to (a) waiting process. mutual exclusion somehow make the resources sharable. dunno how. Avoidance recognize "safe" state - in which every process can finish. every process could acquire all the resources it will need. or at least, there's a way out (an order over the processes that can finish.) imagine processes P1 and P2, resources R1 and R2 P1: acquire(R1) ... acquire(R2) release(R2) release(R1) P2: acquire(R2) ... acquire(R1) release(R2) release(R1) If P1 and P2 both take their first steps, i.e., P1 has R1 and P2 has R2, then we're unsafe... (and will be officially deadlocked once acquire(R2) happens) Banker's Algorithm (note: not the same as Bakery!) we're going to make a decision to not give resources if that would put us (the OS) in an unsafe state. Even if that resource is "available". variables - Available[resource] -- what the machine has left (given the current state of the processes and machine) Max[process][resource] -- what the process could possibly want Allocation[process][resource] -- what the process has Remaining = Max - Allocation -- obvious, right? Is_Safe_State # set the initial state Work = Available -- we're going to modify "Work"... foreach process_id: Finish_able[process_id] = false # and now simulate. loop: find first process_id where Finish_able[process_id] == false and Remaining[process_id] < Work: -- array comparison.. cool, right? Finish_able[process_id] = true -- Work += Allocation[process_id] -- reclaim. repeat if there's no such process: if Finish_able for all process ids: we're safe! hooray. else (something wanted resources that aren't available): we're unsafe! boo. When a process asks for something Is this going to give them more than their Max? if so they're miscreants. Is this resource available in the first place? if not, block as normal. Will giving this resource lead to an unsafe state? if so, block. (not really sure for how long.) Detection Look around and see if anyone is stuck. If so, build the waits-for graph. If the graph have a cycle: a) kill a process involved in the cycle. - which? b) confiscate the resources. How would you implement deadlock detection in geekos (over semaphores) Could look in the queues... but you don't technically know the "owner" of the semaphore, because a semaphore has no owner. (it just has a process that may, at some point, call V().) Similarly, not clear if the kernel can just call V() on a semaphore after killing the "owner" Conversely, if you had just plain mutexes... maybe. Lecture 12 Mar 8 Project 2: 1. (somewhat common issue in getting compilation on the submit server) ../src/user/bgost.c: In function `main': ../src/user/bgost.c:5: warning: implicit declaration of function `Print' ../src/user/bgost.c:5: error: too many arguments to function `Spawn_Program' make[1]: *** [user/bgost.exe] Error 1 which of these is a problem? 2. usrState->espUser -= sizeof(struct Interrupt_State *); two possibilities for the declaration of a User_Interrupt_State ulong_t espUser; // the idea is to prevent you from using user addresses as pointers. ulong_t *espUser; usrState->espUser -= sizeof(struct Interrupt_State *); 3. Do all copies of shell.exe use the same space in memory? fun with nm. cd build nm -n user/shell.exe nm -n user/b.exe nm user/shell.exe | grep Return nm user/b.exe | grep Return nm -n geekos/kernel.exe | less geekos basic memory scheme is segmentation. it is a type of virtual addressing in which the processor implicitly adds a base pointer to memory addresses. 1. Do not hack at adding/removing *'s and &'s. 2. Please doubt the success of functions. - Check return values, even if it's just to print. - If you have no doubt it will work, then kassert. - I ask this not for your software engineering credentials. Dining Philosophers with monitors round table, n philosophers, fork between each pair. (or chopstick) each philosopher is eating, talking, or hungry. want each philosopher to grab forks, not starve (deadlock) strawman (no monitors) treat each fork as a semaphore. acquire right fork acquire left fork eat release left fork release right fork monitor solution test( philosopher_idx ) if philosopher_idx + 1 is not eating and philosopher_idx - 1 is not eating and philosopher_idx is hungry then set philosopher_idx to eating signal philosopher_idx # use condition variable in some way to awaken philosopher_idx. end end pickup(philosopher_idx) # when a philosopher stops talking and becomes hungry set philosopher_idx to hungry test(philosopher_idx) # two outcomes - neighbors are eating (you are not) or # you are eating (your neighbors are not. if eating, return if not eating, wait # condition variable style wait. end putdown(philosopher_idx) # eating -> speaking set philosopher_idx to speaking test(philosopher_idx - 1) test(philosopher_idx + 1) end Transactions / ACID. scheme for getting many little tasks done; those tasks may be executed concurrently, and the result has to remain durable (stored forever) despite disks being way slower than memory. atomicity - either the group of operations all happened or none did. consistency - the odd one; there are rules that are enforced (e.g., your balance isn't negative) isolation - each transaction has the impression that it runs alone durability - once the transaction happens, it is permanent. commit and abort. recall that deadlock detection would just whack processes. Two-phase locking. keeps transactions safe in terms of isolation. phase 1 - acquire locks (growing phase) phase 2 - release locks (releasing phase) goal: prevent any transaction from seeing the effects of a not-yet-committed (or not yet aborted) transaction. T1: read balance write balance commit T2: read balance write balance commit lock_for_reading(balance) read balance lock_for_writing(balance) commit release_all_locks lock_for_reading(balance) read balance lock_for_writing(balance) commit release_all_locks lock_for_writing(balance) write balance commit release_all_locks why fail to get a lock? someone else has it. would you abort? if you knew you had deadlock... or you'd waited for too long... if you knew you were going to write... lock_for_writing(balance) read balance write balance commit release_all_locks can you put the release before commit? commit operation generally writes something to the log. it returns when the write completes. the atomic action that defines whether the transaction completed is whether that entry made it to the log. Midterm review. vocabulary list online. Sample questions (omitted) Lecture 13 Mar 10 Midterm tuesday. Notes: Programming assignments 0-2 are fair game. Paragraphs have topic sentences. "Coding" is allowed. Scheduler due tomorrow. (easy.) PA3 due next friday. Memory - chapter 8 (delays paging to disk "demand paging" to ch 9, iirc) von Neumann code and data are in the same memory. contrast: Harvard architecture in which code and data are separate. hierarchy registers l1 cache l2 cache (levels of cache are optional) main memory optional: non-volatile cache disk tape money, space / density, power consumption, speed, want some stuff that's permanent Operating system will want to buffer reads from and writes to disk. - hold on to previously read stuff so that another access is not required - hold on to recently written blocks since the rest of the block may be written shortly. (until the os gets around to writing, or until the file is closed, when the buffer flush is likely synchronous) Would like to avoid thrashing. - would like to avoid spending lots of time swapping processes out to disk and bringing them back in for little forward progress. Goal: provide each process with the illusion that it has: - 4GB (some large amount... maybe not all addressible memory... but a lot.) - even if the machine doesn't have that much - even if the process's pages aren't all in memory - Isolated memory, in that no other pesky process can mess with its memory. (protection) base+limit in geekos for each memory access, the processor first checks that the address is < limit. the processor will add "base" to determine the correct physical address. then fetch. in the kernel: base, limit = 0, \inf what could possibly go wrong? maybe you don't allocate enough for a process. can't dynamically allocate more (unless...) and its stack is at a fixed location you could imagine it difficult to run processes with sum(memory requirements) > phy memory. (but possible if you swapped a process out before loading or reading another one) cant have a process with more address space than physically available on the machine. (which can be nice to do if you don't want to think about available memory while programming) fragmentation external: space in between the things (memory allocations) are too small to be useful. internal: space within the allocation that is wasted. you might over-allocate for a process so that it has space for a stack. virtual address vs physical address physical is actual. what the processor has to send on the memory bus. virtual is what the program knows. Linker and loader Swapping is not paging. There is a little device that translates virtual addresses to physical addresses. The Memory Management Unit. This includes the TLB: Translation Lookaside Buffer What does the TLB do? maps from virtual addresses to physical addresses... What is the TLB? fully associative cache of virtual page numbers to physical page numbers. - fully associative: any entry can go into any location.. - fully associative: typically expensive or slow... and we don't want slow here. On a TLB miss, consult the "page table" which is the authoritative place where the virtual to physical page translations are stored. An entry in the page table includes (generally): ( all pages have the same length. ignoring PAE and similar superpages ) physical page number (necessarily) whether the page is dirty. dirty means written to. whether the page is valid. and more! Lecture 15 Mar 17? 1) schedtest. it's kinda mean. - don't make really large quanta. (kills interactivity) the default is 4... so staying close to there may be smart. - g_needReschedule (can improve interactivity) - 3 can't appear too early (see the semaphores) - you're not obligated to use "your scheduler" from the web turnin. 2) 20 semaphore limit is there to make your life easier. you may make your life as hard as you like. 3) an object can be on only one "list.h" style list at a time (unless it's another list, e.g. allThreadList). Other lists are possible. --- page table... virtual page -> physical page, ... page on intel - 4k. 4k = 2^12. in that space of 12 bits that are associated with the page but not needed for the association... valid bit. trap if accessed without valid set. the "physical page" that's stored in the entry shouldn't be interpreted as an actual physical page. dirty bit. on a write, processor sets the bit. permissions info, incl whether write permitted. "copy on write" behavior can be emulated if writes to read-only pages are trapped. page replacement policies. the problem -- all pages are allocated. some process wants a page. dirty pages cannot be claimed until they are clean. of the clean pages, want to choose the page least likely to be accessed soon. could imagine least recently used... except then you'd have to track timestamps on each page access and then sort. or move things through a heap. either way, lame. and not that useful. first in first out. relies a bit on the idea that important pages will come back. keep a list.. easy to implement. Placeholder. first in first out plus second chance. "evict" a page. but don't actually evict it. it's still there. keep a list of guys in second chance land. that list should have some pages in it -- Lect 14 Mar 29 No class thursday. Please make progress on PA4a. Or sleep. Midterm; CDF on forum. Big question 1, Big question 2. Selected MCs. Review of semaphores, monitors, condition variables. Previously discussed VM page replacement policies FIFO - when you need another page, kick out the oldest page. OPT - when you need another page, look into the future and find the page that will be accessed as far in the future as possible. LRU - figure out what was least recently used (track the age of the last access) FIFO+Second chance - Have a list of nearly evicted pages that can be rescued. Random - screw it. just choose any page. Clock - fancy metaphor for fifo+second chance. Page references - 1 1 2 1 1 3 4 1 Additional VM page replacement policies. Random Clock LFU, MFU least frequently used - could imagine that these are the useless ones. harvest the accessed bits periodically (perhaps on a trap or on a timer) and increment counters based on those accessed bits. most frequently used - maybe you're done with these. Working Set set some explicit time \tau and decide that anything older than \tau can be evicted. - might use working set assumption to stop the thrashing. Working Set + Clock - use clock for the cleaning of dirty pages and working set for the selection of pages to evict. Can you think of others? might have pages that are only really accessed once. (and pages that are accessed a lot). maybe code pages are different from data pages? seems like fun to think about. What does linux do? Working set + clock at least until recently. (?) Policy: when do you clean a dirty page? when should you not clean dirty pages? maybe not if the page is going to be written again real soon now. maybe do so eagerly if the page is a memory-mapped file. clean more pages if you need the space. and they haven't been accessed recently, so they might be good candidates to be reclaimed. - conversely, relax if you don't need the space. when told to by the app calling msync(). if it's read only, it's always clean... no need to worry about cleaning it. if you're bored and the disk isn't doing anything... might clean some pages just so that they're clean. Allocation of pages to processes. Option 1 - indifferent allocation... just treat all the pages and all the processes alike. Thrashing OOM Prepare for files, which we are likely to start next week. Reminder, no class thursday. Lect 15 April 5 QEMU - try having bounded memory using the -m flag. (I believe tests use -m 10.) Review of virtual memory paging physical memory broken into page frames virtual addresses map into these physical page frames. demand paging defined load a page only when you need it. lazy loading of pages. e.g., stack. e.g., code. e.g., mapped files. swapping defined want to find the authoritative scheme from the book.. something to do with taking application pages, putting them on disk, likely wholesale. (the application in its entirety) page replacement want to find the best candidate to remove... LRU, MFU, Clock (FIFO with second chance) dirty, valid, accessed bits LRU and second chance / clock. page directory... how many are there? one per process page table entries. using bits for referencing the page file when valid = 0. - can't get more than a gig of phy memory for a memory hog process on neil's laptop. OOM policy don't kill system processes root high priority find the guy with lots of memory don't kill xlock. Thrashing Belady's anomaly For some page replacement policies, adding a frame can result in more faults. Book's example: 123412512345 in three frames to four for fifo replacement. 123412512345 three frames - 9 faults. f1 1 4 5 * f2 2 1 * 3 f3 3 2 * 4 123412512345 four frames - 10 faults! wow. f1 1 * 5 4 f2 2 * 1 5 f3 3 2 f4 4 3 Which scheduler could be involved to suspend processes when thrashing in memory? mmap / mincore experiment: homework/mincore/a.out 100... 300000 (takes about a minute) Buffer cache (it's not virtual memory, but it has a relationship in that memory is used to shadow / cache disk blocks. Buffer management is explicit.) Lect 16? apr 7 Files array of bytes with a name and metadata: permissions, creation time, access time, size type, owner, may have internal structure, but file systems never care about the file's internal structure (headers, compression, etc.) possibly non-volatile... survives loss of power, crash. unless the file system isn't backed by non-volatile storage... operations: open/create, read, write, close, seek, mmap delete/remove/unlink, rename, chmod, chown, copy can be implemented in terms of the other calls. move you'd rather implement as an operation to save the copy; copy-on-write tends not to be supported... unless you're in some sort of compressed file system that looks for redundant data. how to erase data (three(?) overwrites with random data, depending on your paranoia level.) how to destroy your hard drive... (microwave, stake, thermite) operations on directories and directory entries: mkdir, rmdir, enumerate all the entries: opendir, readdir, closedir, seekdir. len = strlen(name); dirp = opendir("."); while ((dp = readdir(dirp)) != NULL) if (dp->d_namlen == len && !strcmp(dp->d_name, name)) { (void)closedir(dirp); return FOUND; } (void)closedir(dirp); return NOT_FOUND; open files as stored in the kernel what does the kernel have to store for each file that the app has open? position in file. as altered explicitly by seek. implicitly advanced by read / write. some reference to the inode (the metadata of the file) how it was opened (was it read-only) (mode) what happens if you call seek( value, SEEK_SET )? all it does is change the position in the file. (could treat that as a hint that a read at that location is imminent) is it legal to seek to a position after the end of the file (larger than the size of the file) yes. but if you made a really large file with open, seek, write... a file so large that there aren't enough free disk blocks for all the blocks of the actual file to be stored, when will it break? - expect that it would fail on the write. the inode. indirect access. the structure that holds the metadata about the file (except its name(s)) and indexes of blocks that hold the data. there's an array of these inodes in each file system, the index into that array is a (short) identifier of the file: inode-number likely to be reference counted. sync. once upon a time, if you really wanted your stuff saved, you'd go to the command line and type "sync; sync; sync" "sync" should flush all dirty buffers to disk. sync can take a very long time if the machine is unhappy. disks. platters: have a stack of these magnetic things heads: one read/write head per platter... floating of the platters. idea: patent having another head on the opposite side. nevermind, they're probably not going to be aligned well. cylinder: intersection of (all) heads on all platters track: cylinder on one platter sector: part of a track. Lect 17? apr 12 File systems... split files into blocks. what is the n'th block of a particular file? FAT. Strawman model. Directory will bind a name to a start block. Every subsequent block is linked off of the previous block. FAT makes it efficient. (obviously not as efficient as later file systems) Take all the next pointers, and put them into a table. Ideally, the entire FAT will fit in memory You're worried about O(n) operations that require disk reads. Directories. File name bound to size of the file (and other meta data) and to the first block. Free space. Separate table? hrm... First fit scheme based on having zeroes or some other invalid entry in the FAT. Defragmentation The scheme: load files, write them back in contiguous blocks. The joy of btrees. based on the expectation that memory accesses are relatively free compared to disk accesses... so you try to get as much out of each disk block read as possible. (big fan out) that insight is relevant for file systems where our performance is determined by how many accesses are required. FAT16 and FAT32 ... number of bits per block Why does FAT suck? Limits on the size of the file? if someone was dumb and put a 32 bit size field in the metadata. (people were dumb) If one of the FAT blocks gets busted, you're screwed. maybe there's a backup copy? (probably, check...) Consume memory proportional to the disk, not what you're actually using. (which is unfortunate... disks get big.) Unix File System. (Indexed) Model. inodes in an array. include pointers to data blocks. Indirect blocks. if the file is big, inode includes the number of a block that itself references blocks. Doubly-indirect blocks. if super big file, inode can include a doubly-indirect block, which includes references to blocks.... Sparse file. only need to allocate blocks when those blocks are written, even if the writing happens deep into the file. Free space. Simple scheme: one big bitmap. (there are alternate schemes in the book) Store the bitmap in a (special) file! Fast File System. Cylinder groups. some inodes and data blocks are closer to each other, prefer to allocate disk blocks and inodes that are nearby. Tail packing. collect the "tails" of multiple files into a single block. Inconsistent file system state Remember the buffer cache. In FAT. What could go wrong? In Indexed. What could go wrong? Metadata written before data blocks... Superblock - data about the file system... how big the blocks are... where the inodes are, maybe how much free space there is... Formatting Journaling order writes of metadata into a journal. idea is that the order of operations is preserved in the journal, so that if a failure occurs, a defined set of operations have happened and others have not. ----- Lect 18? apr 14 P4. nm review page faults in kernel mode minor p4 spec wordsmithing edits maybe don't comment out todo()s until you've todone. Log - Structured File System disks have changed. (technology trend) bigger, spin faster,... more bits go underneath the head faster (bit density is high) seek time hasn't moved (becomes relatively high) since the head movement is physical. memory is bigger / cheaper -> caches got bigger. big cache -> fewer reads. potential: read performance doesn't matter... write performance does. how? avoid seeks. create a file (e.g., echo "hi" > hello) write the block containing "hi" create an inode associated with the file (and write that inode block) (so that the inode has the block number of "hi") append the directory entry for "hello" into the current directory (write that block) may update the inode of the directory (mtime, maybe another block) update the free block bitmap (or whatever structure that is) and write that block. goal of log structured file system is to avoid all this. commit all writes to the same "segment" "segment" is of fixed length (e.g., 1MB) partially filled / empty segments are possible. read performance be damned. update a file: block changes... write the changed block in the segment, rewrite the inode to include this block, update the ifile (which maps inode number to location on disk). - all these writes will happen in one segment. - ifile writing can happen at a checkpoint. (when correctness matters, if we're not overwhelmed with writes) each segment is linked, so that the log can be replayed each segment has a checksum, so that a fault in the middle of writing a segment can be detected. The cleaner. Read old, partially occupied segments, and write the (live) stuff right back. Ideally taking two or three or four segments at a time, and writing one. Generational (hopefully): the cleaned segment will ideally last a long time. Access time tracking. in a normal file system, atime is in the inode, which means that for ~ every open or read there is a write. in a log structured file system, if not smart, can waste more write throughput. because you'd be writing the inode and the ifile have the access times as a separate file. (an array of access times) or just disable access time tracking. http://www.cs.berkeley.edu/~brewer/cs262/LFS.pdf http://www.eecs.harvard.edu/~margo/papers/usenix93/paper.pdf Could you put the inodes on an SSD instead? Failure model of ssd's suggests no. Blocks wear out. What would you do if you had an SSD? Has worked for lowering boot time, app launch time. Write performance is not quite so good, once you're moving. You'd use battery backed ram if you wanted to get high random access performance and durability at the same time. Features. Extents - extra-large contiguous regions. imagine RLE over the inode structure. (NTFS, HFS, HPFS, ...) -- Lect 19 Apr 19 P4 post mortem. P5 format tool (src/tools/gfs2f in tools (not yet)) goal of the format project is to help you build helper functions. ... and to understand the format of the filesystem. fake-blockdev.c may help write reusable don't need to boot off gfs2 filesystem frob the makefile "run" and "dbgrun" rules (to run with -hdb gfs2-XxY.img) p5test not yet ready the battery of file system operations... diagnostics: hexdump -C gfs-XxY.img | less I *may* add an unmount() call. Virtual File System layer http://tldp.org/LDP/tlk/tlk.html the problem of intermittently appending to files -> (file system) fragmentation explicit "defragmentation" preallocation - mark blocks as "used" even though they're not. Disk IO Scheduling: intro: many processes -> likely many concurrent requests -> we have a queue of requests! what do we do with queues (like the queue of runnable processes)? we order them to improve the (apparent) performance of the system, measured in some way. we are assuming that we have a queue of requests to deal with. if they come in one at a time, we have nothing smart to do. can we assume that disks are cheap enough to have 20 of them mirrored? 1. power 2. heat 3. I don't have that many sata ports 4. stuff to store gets bigger all the time. (movies) 5. and this only really helps reads, since you'd have to apply writes 20 times. FIFO/FCFS why good? ez. no math for the poor processor (?) fair. (whoever asked first gets to go first...) the order of operations from the higher level is (likely) preserved (unless the disk does something mean to you)... which could yield more reliability if the machine were to crash. why bad? could be slow. time spent moving the disk head is time not spent reading... and you could jump all the way across the disk just because the requests arrived in a bad order. no consideration for important, interactive processes... the disk hogs get their entries in the queue, likely ahead of your important, interactive thing. SSTF shortest seek time first. seek can be replaced with access or positioning find the request that requires minimal motion of the head. greedy. why good? less time seeking. why bad? totally unfair. disk head may stay close to where it is, preferring a series of reads in a neighborhood, causing STARVATION for requests at the edges of the disk or requests far away from some dominant accesses. tends to prefer access to the middle of the disk. SCAN / LOOK / Elevator go one direction, take care of all the accesses in that direction, reverse. what's the worst case access time? have to wait until the head goes all the way to the other side and back. LOOK and SCAN -- SCAN goes to the end even if there's no request out there. LOOK looks first. C-SCAN only read in one direction, warp to the beginning after done in one direction. Lect 20 LOOK/C-LOOK make the obvious optimization over SCAN. Distinction unimportant. Deadline http://en.wikipedia.org/wiki/Deadline_scheduler want to avoid having requests stuck in the queue for a long time. probably requests from little interactive processes that just want one teeny-little block, competing with a big process trying to index the disk, backup, or something. normal processing is c-scan. BUT: each request has a deadline... 0.5s for reads, 5s for writes. if you miss the deadline, issue the request out of c-scan order. possibility that if you're way overloaded, this is a bad bad idea, choosing an inefficient scheme (FCFS-like) to replace a somewhat efficient scheme (C-SCAN) Anticipatory http://portal.acm.org/citation.cfm?id=502046 based on the idea that the processor is way faster, and the program that's handling the data is pretty fast, and that the file system is laid out so that consecutive blocks in a file are nearby, just let the disk head hang out where the last request finished, betting that the program will ask for the next (few?) block(s?). Completely Fair. http://en.wikipedia.org/wiki/CFQ split up the request stream by process that issued the request, those processes with few requests have short queues. one queue per process. the code in charge of keeping the disk busy fetches from these queues, presumably a group of them large enough to sort by address (do C-SCAN) to recover some throughput. not clear how the process id is tracked through the disk requests not clear whether process id is the right thing to generate a new queue (uid? process group?) RAIDs. premise disks are cheap, but unreliable. store data on more than one disk, maybe get more performance, for all levels (but zero) get more reliability. hardware vs software raid. typically have hardware for a "real" system (less true over time) can cache, have battery for the ram,... controller can fail. typically have software for a piece of crap system that you have at home. "levels" 0 stripe not redundant even blocks to disk A, odd blocks to disk B. (also generalizes to more than two disks) write performance better (double the throughput) read performance better (double the throughput) 1 mirror replicate a disk entirely. write both (no performance benefit) can read from either (some performance benefit) 1+0, 0+1 combinations possible/common. 2 ecc mirroring just seems so redundant. store codes on the redundant disks instead of complete copies of the data. more efficient redundancy. error correcting code example (2-d parity!) 1011 1 1101 1 0011 0 1111 0 1010 0 1011 1 1o01 1< 0011 0 1111 0 1010 0 ^ 1011 1 1101 o 0011 0 1111 0 1010 0 3 bit-interleaved parity don't store error correcting data, just store (plain old) parity. 4 block-interleaved parity every write requires updating the parity disk. now the parity disk is a bottleneck for write performance 5 block interleaved distributed parity scatter the parity blocks across all the disks in the set. no write performance benefit (and you have to write twice) no read performance benefit (just one disk has your stuff.) drawbacks To get performance, disks have to be the same. same access time, rotation speed, size.... they likely have the same life expectancy at birth. In the same box, in the same room, at the same temperature, same power supply, same pepco, Weakens the expectation that disks will fail independently... and you need the disks to not fail all at once. If a disk fails, a human must replace it. If the raid is working, unlikely humans notice... in time to fix the disk. The controller can fail too. Expensive, low-volume product... Lect 21 4/26 P5a: Debugging in file systems. Fail nicely. Not silently. Don't assert things that can't be asserted. Assert things you assume to be true and need. e.g., don't assert that block_with_inode_zero is 3 and fail if you see an otherwise valid file system that says "5". however, feel free to assert that a block referenced in an inode is not free. getting that wrong would be bad. ... though a "real" fs would just remount itself readonly and prevent any further damage, rather than crash the OS. Print when something seems wrong. There are few enough things that can be wrong. Be careful with recursion. Double check that you call a recursive (directory traversing) function with a parameter closer to terminating the recursion. The kernel's behavior on stack overflow is unlikely to be friendly. Don't load everything at once. Watch out for Malloc failure. If you're in the habit of loading the whole file, note that the malloc that fails might not be the big one, but one after the big one. Ensure balance between enable_interrupts and disable_interrupts. Interrupts will have to be enabled for devices (like disks!) to do their work. (large) Reads and writes need not be atomic. Beware 8192 block filesystem on 512-byte blocks: two blocks are needed for the free blocks bitmap. NFS Any time* there's a file system call, that call is bundled up into a remote procedure call and invoked on the server. What are the challenges of remote file service? Single server could get overwhelmed. Latency? not very long to send a message across a local network, relative to disk access. Maybe high relative to cache. Loss: your request might be dropped, requring retransmission. have to make sure your (destructive) operation isn't repeated. If the server / connection goes down, no one knows what to do. The file system interface sort of expects the disk to be ready to read/write whenever the machine is up. Maybe just a reboot? Permissions / users. Should the machine asking for this file be provided the file? Should it be allowed to write? Stateless model Handle an RPC, done. Idle client would be unlikely to notice if a server rebooted. Busy client would just try again... It will try and try and try (and be locked and unhappy and probably need a reboot itself) if the server takes a while to come back up. Server knows, remembers nothing about your open files, file positions. (might have to be involved in locks... I'd have to look that up.) So the file pointer stuff is still just associated with the PCB on the client machine. Server still has the state that's on disk... still can have buffer cache to keep from having to read frequently. Can (but probably shouldn't) say "done" before the disk block makes it to disk. Authentication Assumes friendly network, single administration, authorize IP addresses, and global user identifiers. (both considered to be bad ideas). There are programs, e.g., arpwatch, that will try to figure out if someone is stealing an IP address. Unencrypted. so you can use wireshark... except you can't since you're not root on a network that's trusted like this. make on the linux kernel is a reasonable file system benchmark. NFS tends to use UDP (User datagram protocol), which tends to be unreliable, unordered. Recent versions can use TCP instead. FUSE / sshfs http://fuse.sourceforge.net/ module that runs inside the kernel and shoves the file system request up to user space so that you can implement the FS logic at user level. canonical example is sshfs, uses ssh (sftp) to provide a file system interface. might use it for a bizarre file system... if the user process can read and write a block device. might use fuse for semi-transparent encryption LVM http://en.wikipedia.org/wiki/Logical_Volume_Manager_(Linux) Comparable to virtual addressing for disks. software. Enables coolness: grow/shrink logical volumes, snapshots, replication. Indirection solves problems. why check a file system? don't check a mounted file system. a (read/write) mounted file system (pretty) necessarily has inconsistencies. somebody tripped over the power cord. the disk is dying. what could be wrong? inode thinks a block is in use, free block bimap thinks the block is free. dirent points to an inode with zero reference count replica superblock is busted. (real filesystems have more than one replica.) what will the file system checker do when it finds such an error? (a) it will ask the user. so annoying. pretty hard to know what to do. (b) guess that the data is still supposed to be there. lost+found might be able to recover data. e2fsck -y is a bit dangerous. If you care that the file you just wrote is actually written, run "sync". if sync takes a really long time... your disk is dying. Security / Authentication bits. crypto for dummies. public signatures take a message, (securely) hash it, encrypt the hash with the private key, any holder of the public key can verify that you attested to this message in some way. certificates signature on a public key. (from someone "trustworthy") whole internet will explode unless they remain trustworty. CRL - certificate revocation list. If a key is compromised, there's a way to cause a certificate to be invalid (revocation). secret Diffie Hellman way to construct a secret from messages visible by anyone. everyone agrees on a generator g. alice comes up with a number a (keeps that secret) bob comes up with a number b (keeps that secret) alice sends g^a mod p to bob bob sends g^b mod p to alice alice can construct g^(ab) bob can construct g^(ba) no one else can. downside... alice doesn't have any reason to believe it's bob. need more stuff if you don't want someone snooping in the middle. Lect 22 4/28 Course evaluation stuff. Did you know that courses get evaluated? :D How should the OS store a password? cf. Sony's screwup. http://arstechnica.com/gaming/news/2011/04/sony-admits-utter-psn-failure-your-personal-data-has-been-stolen.ars http://arstechnica.com/gaming/news/2011/04/sonys-black-eye-is-a-pr-problem-not-a-legal-one.ars My favorite line: "To be fair, Sony does apologize for the inconvenience." "encrypted" hashed with a salt. possibly done again? different salt per password (i.e., per user). alternative: zero knowledge proof. (I don't know anything about this... so y'all in the security class know stuff, awesome.) alternative: magical incantation or sword of excalibur. So why did Sony (apparently) store passwords unencrypted? laziness? bad software engineering practices? storage? time? seems unlikely. support calls? can tell a user their password. (hashed, you wouldn't be able to know). protocol might be more resilient to sniffing of the channel between client and server. Tenex: (neato timing attack based on page fault) 1972. (aside from inefficiency, and from storing the password unencrypted) What's wrong with: for (i = 0; i <= strlen (directoryPassword); i++) { if (directoryPassword[i] != passwordArgument[i]) { /* the password is wrong. */ sleep (3); return EACCES; } } return 0; (code snipped from David Mazieres, then fixed by kit) Can tell by fail time when it's wrong... the time for a page in is significant beyond the 3 Unlike geekos, the kernel doesn't do a complete copy_from_user. it just accesses the user address directly. /etc/passwd, salt list of usernames, user ids, hashed passwords, default shell, home directory. why does /etc/passwd no longer have passwords? a) it's super useful information for many programs to have (so it can't be protected from prying eyes) (e.g., for finding things in ~otheruser) b) hashed passwords aren't all that secure. (could be copied elsewhere and then broken.) /etc/shadow stores the actual hashed passwords. readable only by "root" or the login program. Replay generally: you don't have to break the message's encryption, you just have to know what it does. if you can intercept it and replicate (replay) it, you can trick the recipient into doing something you weren't supposed to be able to tell it to do. example: there's an attack on a precursor to kerberos (needham schroeder) that uses this type of attack. nonce ensures that the message is fresh. (new, not replayed.) timestamp could be used as a type of nonce. (picture of today's paper) ordinary encrypted messages just mean that the sender "once said" the contents of the message. if they include a nonce that you came up with (so you know it's fresh), then they "believe" it right now. freshness is contagious. dictionary attack guess that people use words or w0rdz as their passwords. and try every one. ssh-keygen, ssh-agent, ssh-add. what does a passphrase do on an ssh key? encrypts the private key (identity file). someone who hacks your machine can't get access to the other machines you can access. someone who sniffs the network can't find your ssh key transmitted via nfs. ssh-agent stores the unencrypted key in memory so that you don't have to type in your passphrase fifty billion times. (ssh-add inserts the key into ssh-agent) Lect 23 5/3 Project 5. any dirent may span blocks. directories are implemented as if they were files... files are arrays of bytes. the existence of blocks doesn't matter (i.e., no one needs to know how big the blocks are; no application knows how big a block is. the only padding (unused stuff) in a directory is to ensure that the inode is word (four-byte) aligned. (or to permit quick deletion) you're going to need a function that reads X bytes from a file at the current position anyway. Get_FS_Buffer should have a matching Release_FS_Buffer... otherwise things will block. Kerberos What if you wanted to authenticate and authorize users without the benefit of public/private keys to identify each user? mutual authentication server should know who the client is. client should know who the server is. establish shared keys between a central authority (KDC) and each server. (and each client... though with each client, that secret is closer to a password that can be presented on login) the task of the kdc is to act as matchmaker. vouch for client and server to each other, using the secrets kdc<->client and kdc<->server to set up client<->server keys. KDC = AS + TGS (key distribution center, authentication server, ticket granting server) AS, given user/password, provides TGT (ticket granting ticket) TGS, given TGT and server desired, provides a ticket. SS (service server), given ticket, decides what to permit the client to access. Only the KDC has your passwords. The compromise of other machines doesn't matter as much. The bad: If the KDC fails, can't authenticate any more, so nothing can be done. DoS target? KDC compromise would be a disaster. Alternatives to hacking the machine (the four B's) burglary, bribery, blackmail, bludgeoning irrelevant detail for this class is the distinction between burglary and robbery, but the four b's above remain orthogonal. unix file system perms user, group, other; read, write, execute; setuid, setgid, sticky. third parameter to open(filename, flags, mode) mode comprises many little flags. lowest 9 bits are the product of {user, group, other} x { read, write, execute } triplets of bits, which means that modes are expressed in octal. hex: four bits (nibble) per character. 0x prefix in C. octal: three bits per character. 0 prefix in C. 0444 user read, group read, other read. (all read) 0220 user write, group write, other nothing. 0755 user everything, group read/execute, other read/execute. - would be good for a directory, since access to a directory requires "execute" permission. (and reading its contents requires "read" permission.) 0644 ^--- user. 4 and 2. 4=read, 2=write, 1=execute ^-- group. ^- other. chmod 644 foo # because a parameter on the shell, leading # 0 not required. chmod("foo", 0644); in C. but wait there's more! setuid bit - permits that program to change the userid associated with the process to the owner of the file. setgid bit - when set on a directory, encourages files created in that directory to be owned by the group. sticky bit - on a directory, user can remove/rename only his own files. and I believe there's even more "wheel" is a group for admins (who can typically become root.) Reflections on trusting trust Ken Thompson's Turing award lecture. How do you know your machine doesn't have a back door? Look at the login source code, right? But what if your compiler is busted, and inserts the backdoor into the login source code? Look at the compiler source to make sure it doesn't do that. But see above, your compiler was busted. Morris worm Sendmail, fingerd buffer overflow vulnerabilities on BSD and SunOS systems Am I already running on this machine? If so, maybe don't run another copy of myself. with some small probability, run (infect an infected machine again) anyway. unfortunately, this small probability was still too large. rfc1135 Return to kernel memory allocation Buddy allocator Goal: contiguous allocation. Start with one big block of memory (geekos's big block is 1MB in the 1-2MB range of addresses) Allocation: round up each allocation to the nearest power of two. look for an allocation on the free list of exactly that size. if nothing free, look for one that's the next larger size, then break it in two. - (one for you, one for the free list) repeat / nest / whatever. Free: put your allocation on the free list. look for your buddy on the free list... if found, merge. your buddy is the one with a common prefix... only one bit changes. 1MB - 2MB 100000000000000000000b 1MB 100000000000000000000b 512kB : 110000000000000000000b 512kB 100000000000000000000b 256kB 101000000000000000000b 256kB : 110000000000000000000b 256kB What was the goal? big, contiguous memory. What are the disadvantages? external fragmentation - you could have unused spots of small size that prevent you from allocating a larger block. internal fragmentation - you didn't likely ask for a power of two bytes. small allocation quickly freed might mean a lot of splitting up of blocks followed by a lot of merging of blocks. Have to figure out the accounting. header space... Slab allocator Observation: the kernel has lots of little, uniformly sized structures. PCBs per module kernel structure buffer cache struct Page might be one of these small structures. (geekos allocates this as a big array) not the page table will be outside thi Strategy: allocate a page, treat the page as an array of objects of a specific type. (some objects used, some objects free) could even initialize the objects in the slab. Slabs can have states: full partial empty Empty slabs may be reclaimed. Reuse initialized objects. - common technique outside OS too. What's the advantage of the slab over the buddy allocator reduced fragmentation. efficient, since small, short-lived blocks are not expensive to free. What are the disadvantages? if you only need one object of a type, then you end up allocating way too much memory for it (a whole slab / page) and have only one object in it. Lect 24 cinco de mayo. Project 5 deletion - must ensure that no version of ls will list the file. (that the file is deleted cannot rely (entirely) on a "special" inode value) test stuff - yes, the submit server uses a modified gfs2 that doesn't create stuff. network byte order is big endian. little endian machines must convert. which means most software has htonl calls (host to network long, performs a byte swap) annoyance: bsd machines leave the size of the packet in the packet in host byte order until the last moment, then convert. when writing raw packets, (which is something you can do as root), the length is in host byte order alone. Return to memory allocation. "SLUB" allocator (current linux(?)) move slab metadata (e.g., in-use counter) to a separate location, overriding unused fields in the struct page. mixes object types, as long as the size is the same. (why good? why bad?) good because there's potentially less fragmentation: more full, fewer partial slubs; weird types might be included in a slub with other objects, not on its own consuming a page. bad because some dumbass's allocation is right next to yours, and if his code is buggy and overruns his allocation, your data structures will get corrupted. you would be unhappy. Wait or fail? in the kernel: wait (maybe 10ms?) if you can. fail if you can't enable interrupts. wait for pages to be evicted, unused slabs to be confiscated, maybe buffer cache to shrink. so when a kmalloc happens, it make be GFP_ATOMIC (must happen now, or fail) or GFP_KERNEL (can wait). http://www.linuxjournal.com/article/6930 in a user-level process.... hrm. I think you'll fail when at the resource limit (at the max memory that the kernel will give you)... fail when there's no chance you'll get the memory. Basic distributed system highlights Two generals - impossibility of agreement with finite messages messenger captured (and message divulged) not part of the model/problem. smoke signals would give your presence away to the enemy (bad) the day is cloudy and foggy, and it's dark. birds are equally vulnerable. (ip over avian carriers) receiving general sends a messenger back, saying, check. but this messenger could be captured... and the recipient needs to know 20 messengers, repeat until no army. Byzantine generals want agreement among several generals/armies and at least one is evil (making it a problem) he could follow the protocol and lie (let's not attack) and equivocate (alice, let's attack; bob, let's go home) he could arbitrarily deviate from the protocol (not send messages at the right time). how do you get the good generals to agree despite the existence of the bad general? the evil guy is not a newcomer... he's been in secret. a piece of many solutions is to rebroadcast what you've heard. bad general could (potentially) claim that alice said 'let's attack' to you, falsely implicating alice. a piece of many solutions is that messages are signed, so that you can't go back. the evil guys can collude. good guys inherently collude. (but don't know who's good or who's bad.) Lamport clocks - (causal) ordering of events advance some shared state machine. to make any sense of the distributed operation of these machines, want to have some idea of the order in which these events occurred. could think about real timestamps. (satellite gps doesn't work indoors) each operation gets a (sequence) number, each message gets a number. increment this number on every operation you do, on every message you send, and advance to the latest number you've seen from anyone else. these are not (necessarily) unique numbers: the order is only partial. Two-phase commit - making atomic updates across machines everybody's good, they just might fail. want the atomic operation (atomicity) for transactions. two phases: prepare, commit. prepare: ensures that all operations, all effects of the transaction are "on disk" - in the log. commit: coordinator (one central machine writes to disk that "it's committed!" and tells everyone else involved.) if anyone fails before prepare, commit doesn't happen. if the coordinator fails before the thing is committed, it didn't happen. if the coordinator fails after the thing is committed, it did happen. and anyone who failed after prepare could ask the coordinator about any transaction not resolved in the log. the central atomic action is the disk write. anyone who recovers (when in the prepared state) can ask about the fate of the transaction. two-phase locking is distinct: acquire, release... as long as you don't release before acquire, keep isolation. (not a way to prevent deadlock... review the four conditions of deadlock) Broader (possibly review) questions: how might an operating system (help) save power? turn your computer off. or hibernate your computer. solutions not involving turning off the whole computer, or refusing to perform work, or not running processes, or telling you to get a better machine, funny schemes to use two graphics cards: one that's good, one that is low power. disk - not write to the disk as often? - spin down the hard drive. - avoid reading (read everything useful into memory early?) throttle the cpu. avoid context switches? - seems like you might keep the machine up longer not doing anything useful.... annoy the user.... power down the supermouse? (don't know how much power idle devices use) sleep the screen definitely saves. slow down devices? (unlikely that taking longer to transmit / receive data will be a win, though) offload across the network? (communication is pretty expensive, though.) fans Review 0) p5 - read zeroes in the middle of a sparse file. (either by initializing and committing blocks, or by noticing how the block wasn't allocated in the inode and returning zero... though I don't believe there are tests for this.) p5c can (mostly) redeem the lateness of p5a and p5b. 1) simple concepts I forgot to talk about. soft and hard links. more than one path name refers to the same file. soft = special file that contains a path of a referenced file. hard = another name for the same inode. (just another dirent with the same inode number). - lndir is a tool that will make a shadow copy of another directory and all its files using symbolic links. sequential and random access. how to make sequential access faster. (read ahead) random access. (don't read ahead... maybe file system layout can help.) capabilities - realization of authorization. separate from the user id, separate from the filesystem, bunch of bytes that represent access rights. maybe can be delegated. likely for systems where crazy security people want fine-grained policies to keep the bad guys from getting any more access than they're entitled to. Sun's ping of death - fragment with a long length at offset really close to 64k (the max size, also likely the reassembly (of fragments) buffer size) Review-like discussion questions... how long does it take to seek on a disk? depends on the distance, depends on the rotation speed. 10ms-ish. what differs in the os on a mobile phone? apparently a lack of security related to the gsm interface. no hard drive, probably flash. don't care about many users. there is only one... power consumption matters? crappy processor in apple's world, background stuff doesn't matter. (low priority) also in apple's world, applications are isolated on the file system. maybe a little defensiveness against "bad" application writers. how would you hide a process in geekos (rootkit style) keep it out of allthreadlist. could be on the runnable queue anyway... or on a device queue... just not in allthreads. which problems in 412 were solved (initially) with fifo? what happens after that? cpu scheduling in geekos was fifo... paging in virtual memory (first thing is fifo... then fifo + 2nd chance) (block allocation? ... preallocation would be different than plain first available block first) disk block scheduling (eventually C-LOOK... then deadline / anticipatory.) how would you make file locks (flock) in geekos? where would the data structure lie? step 1) implement reader/writer locks. (with a couple of semaphores, probably) step 2) find the reader/writer lock by full path (hashtable?) or maybe reference it in the VFS File structure. what features are necessary in the operating system? which must be in the kernel? how might you support 10 gigabit transfers (thunderbolt) on a 3 gigahertz processor? bypass the cpu / dma super-fast-interrupt-level-stuff(?) interrupt coalescing - behavior of fast networking cards to reduce the interrupt load on the processor by only interrupting after several packets come in or after some delay. is 10ms a good quantum size on a machine with an SSD? why does linux use a swap device while geekos uses a swapfile? because memory is so big, what would be advantages/disadvantages if we decided to make virtual memory pages 8192 bytes instead of 4096? Further reading: http://www.makelinux.net/ldd3/ or http://lwn.net/Kernel/LDD3/ http://www.kernel.org/doc/ Research papers in operating systems: http://sosp.org/ , e.g., http://labs.google.com/papers/gfs-sosp2003.pdf, a file system for append throughput. http://www.usenix.org/event/bytopic/osdi.html , e.g., http://www.usenix.org/events/osdi10/tech/ http://www.usenix.org/events/hotos11/tech/ (generally cool, unfinished ideas) http://www.usenix.org/events/atc11/tech/ (generally lower level, practical stuff) Review List from a prior semester: Study your popen. Semaphores and monitors. File system differences. Everything is a data structure. Some data structures are on disk. Some data structures are shared with the processor. Know some key contents of the data structure for every object. what is an operating system? what illusions does the operating system provide to applications? how do devices tell the processor there's something to do? how does the processor get information from devices? what's a pipe? a named pipe? a socket? what's the difference between a system call and a library call? what's a microkernel? what are the challenges with a microkernel? what are the advantages of a microkernel? what's an interrupt? how does it differ from a trap? how do interrupts help with preemtive multitasking? what's a real time system? what characterizes the apps in a real time system? what characterizes the scheduling in a real time system? every task has a deadline. assuming your tasks don't have your proc oversubscribed, earliest deadline first. what's a file? a file descriptor? a file system? what is the interface of a file system? file descriptor definition from open(2): (a small, non-negative integer for use in subsequent I/O as with read, write, etc.) what's a shell? how does a shell start (not on geekos)? what's a process? contrast thread. what does a process have? what are its states? what is stored in the PCB? what's a pid? what's a zombie? how much state is needed by a zombie? where are page tables stored? how does a context switch happen? why not switch frequently? what's thrashing? what's a quantum? what are short, medium, and long term scheduling? what distinguishes dispatcher from scheduler? which processes live forever? what does "init" do? what is a daemon? how does a process become a daemon? how is system() implemented? pipe()? how does a shell implement the | operator? why separate processes by pipes not threads? why use shared memory? what is sigpipe? what's the diference between UNIX domain sockets and Internet protocol sockets? why use one over the other? (unix domain is not udp.) know the socket system calls. accept, bind, read, write, close, shutdown, connect, listen. user level threads. what that means. what process is required to create a user level thread, and what (arch-dependent) calls are involved in creating a new user level thread. distinguish from kernel thread. scheduler activations. what and why. thread pool. what and why cpu scheduler goals. types: FCFS, SJF (SRTF), MLFQ. adjusting quantum. detecting i/o bound. what it means to block on i/o or give up the quantum. is fairness good? reentrant functions. don't hold state across invocations. what does signal() do? contrast kill(). alarm(). multiprocessor scheduling: affinity, load balancing. SMT. memory stalls. synchronization, race conditions, locks. reader/writer locks. starvation for whom? the critical section problem: four goals/criteria. Peterson's solution. Applicability. Insight. Bakery algorithm. metaphor. insight. key mechanism. test-and-set/TSL. how to implement lock and unlock. swap/xchg/swp. how to implement lock and unlock. why these primitives aren't enough. semaphores. P/V proberen/verhogen wait/signal how implemented (you know this well.) implement producer/consumer bounded buffer. what does the producer wait for? what does the consumer wait for? implement reader/writer locks. who starves? condition variables and monitors condition variable operations motivation for monitors. implementation of semaphores with condition variables and monitors. implementation of monitors and condition variables with semaphores. producer/consumer with monitors. signal-and-(continue vs. wait) dining philosophers solution with condition variables. transactions: ACID. name each, what they mean, how they are ensured. two-phase locking. what it's for, how it works. when locks can be released. undo and redo logging. deadlock: four conditions. prevention, avoidance, and detection. mechansims for each. incl. banker's alg. how to decide which processes to kill == end of pre-midterm content == memory management: stall, protection, address space. overlays (old school) contiguous allocation, limitations. fragmentation: internal, external. segmentation vs. paging. process address space layout. page table. multilevel page table. page directories. page table bits. TLB. what it does. why page size matters. inverted page tables, hashed page tables. PAE. position-independent code. relative addressing, indirect addressing. why have PIC? what's a page fault? what's the task of te pager? page replacement strategies: FIFO, OPT, LRU, Second chance, Clock, MFU, LFU, working set contrast insight, goals, weaknesses. page buffering, how to decide when to write dirty pages out. page allocation, minimum pages required, global allocation, fairness, proportional, priority. memory mapped files. kernel memory allocation: buddies and slabs. three states of a slab. prepaging: what it is, how it helps. contrast medium-term scheduling. OOM. file systems: interfaces. disk geometry, performance properties. file metadata. berkeley study conventional wisdom about files. contiguous allocation, linked allocation, FAT, indexed allocation, multilevel indexed, early unix file system (very gfs2), fast file system and what made it faster. ext2. NTFS and extents. understand a File Allocation Table. Free blocks bitmaps. why they're good. preallocation. the buffer cache. contrast unified buffer cache, page cache. the log structured file system: motivating insight(s). implementation issues: cascading changes to update a block of data. the ifile and storage of atime. the cleaner. journaling file systems. insight. writeback, ordered, data. redo/undo distinction to log structured. i/o scheduling: FIFO, SSTF/SATF/SPTF, SCAN/Elevator/LOOK, C-SCAN, deadline, anticipatory. what each is good for. what can go wrong. does it help to have deeper queues? what makes more than one block show up on the queue? RAID: levels 0, 1, 5. cost. mirror, stripe, parity. NFS: RPC, XDR, statelessness. access control (uid reporting, exports file) operations. rfc 1094. Security: Thompson, Tenex, /etc/passwd salt. public/private keys, signatures, certificates. Nonce, dictionary, replay. Two-phase commit. ---