cmsc 412 spring 2013 TAs: Justin Wagner, Donald Carnohan 1 - always there. while(1) is not dangerous in user code. - can do anything! - illusion provided by the OS. - options for policies what's a process? running instance of a program with its own: memory - stack threads - (their stacks, registers) resources: file handles environment process control block "PCB": - process id - priority (should call it niceness) - "owner" in geekos is the parent process id. - user who ran the program -> has some rights to files. - also effective user id -> acutal permissions The real user ID is that of the user who has invoked the program. As the effective user ID gives the process additional permissions during execution of ``set-user-ID'' mode processes, getuid() is used to determine the real-user-id of the calling process. - resource consumption / process accounting - resource limits - max cpu time allowed, - max memory allowed, - other limits... `man limit.. or ulimit..` - process state - running / waiting. (which queue is the process on) - Zombie! terminated program, has an exit code, parent has not asked for it yet via wait(). # lecture 2 Additional Unix and C review Unix Pipe ifconfig | grep -i bcast cat /var/log/messages | less shell will pipe, fork, close extra sides of the pipe. Conditions of SIGPIPE reader has gone away, writer is writing strace yes | less how big was the buffer? write returns an error SIGPIPE kills the process Semicolon if you want two commands to be on the same line, you use the semicolon: - you like using the shell's history (e.g., up arrow) - chain with "cd", e.g., cd ../../build ; make mkdir really_long_path_name ; cd !$ - sleep 300 ; mail me@there -s 'wake up!' - sleep 300 ; echo ^V^G Logical operators: &&, || && if you only want the second to run if the first succeeded. || if you only want the second to run if the first failed. cd ../../build && make test -d really_long_path_name || mkdir really_long_path_name make && make run /bin/test program -d if the named thing is a directory. /bin/true and /bin/false Environment: $PATH .profile or .tcshrc not (.login or .bashrc) C typedef (purpose, abuse, best uses: stdint, function pointer) declare something that looks like a variable, becomes a type typedef unsigned int uint; typedef struct _ll_never_use_me { struct _never_use_me *next; int n; } LinkedList; reasonable uses for typedef. stdint.h - declare types with a specific representation. u_int32_t, int64_t. <- specific types, specific lengths char is signed on 386, unsigned on arm. int8_t unambiguous. printf relies on the actual type. there's no glorious scheme for printf to figure this out. there is a less than glorious scheme. size_t-like variables are unsigned long or unsigned long long printf() a size_t, you have to say %lu or %llu in the string. #define SIZE_T_PRINTF_THING "%llu" printf("The size of thing is " SIZE_T_PRINTF_THING, thing->size); function pointers for casting. see man signal. pointers and memory allocation struct linked_list *ll; who knows what ll is, I did not initialize it. let alone allocate memory for it. ll->foo = 7; /* best case, I seg fault */ struct linked_list l; struct linked_list *ll = &l; if I return ll, horrible. if I put ll anywhere (e.g., append it to a list) horrible. there is virtually no reason to do this. exec functions (which is the system call, what do they do) execv - v => vector for program arguments. just like you get as argv as a parameter for main. execl - l => list for program arguments. looks like printf. execve - v+e => e = environment. rather than allow the replacement to inherit, we give it a new environment. *** this one is real *** execvp - v + p => p = path. search PATH for the program before execution. user process does the search, then invokes a "real" exec. exec as applied to geekos exec as a system call: trap, kernel pushes regs onto kernel stack for process eax identifies Exec in Sys_Exec Load the new program -could you reuse the old segment, it would save max memory. -creates trouble (fragmentation, what happens if it goes wrong) -in the land of paging virtual memory, reusing resources is less relevant. the pre-exec program is probably using pages shared by another process, so we can't reclaim them. if we Fail to load, return (e.g., program not found) rewrite state stack pointer instruction pointer. free old progarm copy fd table don't inherit libraries. so if the new program links libraries into its address space, that happens as it starts. # lecture 3 I posted a version of project 1. GeekOS processes Kernel stack Kernel_Thread and User_Context overview. Kernel stack pointer see end of Handle_Interrupt in lowlevel asm for swap of esp owner and joinQueue Every thread waits on some queue (or is the one on the processor) All Thread List. include/geekos/list.h Contrast generic PCB above. Interrupts and locking. - 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) - "top half" of a handler, does the bare minimum. - "bottom half", finishes off the handling process. interrupts are many (one per "device" of sorts), just as signals are several (one per event) Interrupts interrupt. Tension: need interrupts OFF to manipulate shared data structures: e.g., process list, allocated memory. else other threads or processes may try to manipulate the same structure. need interrupts ON to use devices like the disk. interrupts must be on while the user code is running, obviously. Functions Enable_Interrupts - sti instruction will complain if already enabled! Disable_Interrupts - cli instruction will complain if already disabled! Begin_Int_Atomic - return a flag if interrupts are enabled, and ensure that they're not. End_Int_Atomic - use the flag to decide how to return to the prior state In practice: System calls start with interrupts disabled. This is not necessary or even "good", it just is, and kind of simplifies. Functions will tell you what they expect via assertion failure. Because geekos is for teaching. IRL, the extra calls to check interrupt state would likely be avoided. In reality: Disabling interrupts doesn't work on multi-processors. - multi-core is just multi-processor where they figured out how to manufacture processors on the same die. - doesn't stop the other processor from running - if it did, you'd kill performance. Other instructions are used instead. - smaller locks - lock the memory bus to set the lock variables Locks lock everything; any piece of shared data e.g., the file position, list of free blocks for malloc. Context switch. A periodic source of interrupts from the 8250? PIC chip. I want you to send me an interrupt every 10ms. At the end of that 10ms, the kernel can decide whether to continue running that process, or switching to another. BUT, fairly likely that any other interrupt could cause the same change, CERTAINLY if the process has to block. Processor scheduling Goal: create a responsive system despite potentially excessive demands. Three tiers of scheduling short term scheduling - which of the runnable processes shall I run? medium term scheduler - which of the processes should I keep in memory? long term scheduler - which processes should I even start? Also exists a "dispatcher", which is the thing that methodically applies a schedule, without necessarily the same logic as the "scheduler". Mix of processes with various resource requirements - the guy that just burns cpu we don't mind very much taking the cpu from him. - the guy that's always blocked on the disk we don't mind giving him cpu when he asks for it. - scheduling disk requests is an entirely separate thing. for platters - cscan for ssds - fifo GeekOS has a round robin scheduling policy with priorities. (GeekOS higher priority means run first, it is priority not niceness.) # lecture 4 Fork & Exec on submit. forkexec, forkpipe, fork-p1 Pipe clarifications - Start with fd 0. Free() your Malloc()s. Memory protection, processor registers. http://www.intel.com/design/processor/manuals/253668.pdf (redirects to...) http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-vol-3a-part-1-manual.pdf Fig 3.1 relevant (more relevant for p4) Paging advantages - address space appears infinite: can set the stack to start at an incredibly high address, so that you'd run out of memory before overflowing the stack. - fine-grained multiplexing: can evict unused pages, keep more programs in memory, allow programs to use more address space than the machine has space for. - stuff not in the working set can go away - different data in physics simulations - initialization code - leaks - fork support: mark pages copy-on-write so that they're not actually copied (particularly if you're going to exec). - less fragmentation: less unused space in the middle of a segment; no unused space between pages as might be between segments. - sharing - can be done with segments too, but obvious in paging. everybody could use the same address to refer to the shared memory region. Why do we want walls between processes in the first place? Security passwords in memory: don't want bad processes to read em too. don't want bad processes to overwrite code don't want bad processes to overwrite return addresses (cause a jump) Fault isolation: don't want mistakes in pointers to cause a disaster. Independent resources: e.g. file descriptors Limit abilities of different processes resource limits, file permissions, etc. compare against DOS. compare against lots of threads. (parallelism from the threads) threads don't give us the ability to compose different programs. Simplest way of sharing data between programs / processes Read and write the same file. EZ. Why not do it? Disks are slow. File descriptors. (unless you have a lot of files to write, might not be so bad) Synchronization not EZ. (can use file locks. might end up with inconsistent file) Per-process permissions at least fairly hard / cumbersome / requires setup. - third program might maliciously edit your file. Files might get big... and somebody has to delete them. - compare to a pipe, which destroys the data on a read. Every read or write can lead to a system call. The pipe Anonymous pipe. Has no name. - Only processes to have access to the pipe are the descendants of its creaor. - Synchronization should be mostly taken care of (writers won't overwrite, readers won't get duplicates) - Still some system calls (not a big deal). Named pipe. pipe has a reference that is a name (rather than open file descriptions) name exists somewhere in the hierarchy of the file system. largely unused. The shared memory same memory referenced by 2+ address spaces. maybe at the same place. somebody can write to it. (even though memory can be "shared" in the sense that code pages can be the same physical pages for more than one process, we don't call that shared memory) to set up this shared memory, we need help from the kernel. shm* system calls. at = attach, get = get, ctl = contol. can you do shared memory with segments? sure, but geekos won't do it. (unless you spend a bit of time rewriting the memory subsystem) Message passing Canonical IPC mechanism for a microkernel. Philosophy: Implement traditionally kernel-ish things as processes, Consequence: need fast IPC. need fast synchronization. --- Piazza Anonymity Revised policy; I will no longer answer anonymous posts. If your ignorance embarrasses you, drop. Nothing will be better specified in this class than Exec. --- # lecture 5 Continued IPC. Review - plain old files, shm*, pipe&mkfifo, message passing Next - Sockets: TCP (IP) & UNIX; Signals. Sockets. man 7 unix (section 4 on mac for some reason) man 7 ip (section 4 on mac for some reason) unix: quick, local, special powers. ip: across machines, but that leads to troubles. four bad things that can happen to your data across an IP network. loss: data might not make it. corruption: bad data might make it instead. delay/reordering: might take extra long for some data duplication: network might try too hard TCP solves all these things. UDP solves none of them (corruption a little bit) need an external data representation. decide, e.g., little endian or big endian... or text. e.g., use htonl() Interface (set of system calls) largely similar. Also, datagrams are more like messages. send a datagram of 20 bytes, receive a datagram of 20 bytes. streams like our pipe interface. writes of (1,2,3,4) bytes and a read of ten bytes. Sockets have no open(). They have socket(). socket - we tell it what type (ip/unix, stream/datagram) returns a file descriptor. - server side functions (receives the connection setup) bind - assigns a local endpoint to the socket. - in a web server, I want port 80. - ssh server, I want port 22 - unix socket, 250-ish byte name, iirc. - fails if someone else has that endpoint. listen - sets the socket to receive incoming connections accept - takes a listening file descriptor - returns a new file descriptor for a new connection (conversation with a specific other endpoint) (each conversation is made unique by the combination of endpoints, we can use port 80 for each of our conversations, because the other end will always be distinct) - client side, initiator, connect - after calling socket to get an fd, use that fd to initiate a connection to a specific (remote) endpoint - write - same as in files and pipes read - same as in files and pipes send / recv - works on both streams and datagrams [citation needed] sendmsg/recvmsg - typically datagrams. - select or poll - I'm interested in all these file descriptors. Please tell me when any of them are ready (and which one is), so that I can go to sleep until then (or until specified time elapses). can (but I haven't seen anyone do it) use signals instead. - close - I'm done, go away. shutdown - Can say I'm done in only one direction. (without explicitly writing "I'm done" in your transmission; instead, implicit, other side reads 0 bytes, i.e., end of file). Tiny web server functions l = socket() bind(l, port 80) listen(l, backlog = 5) while( c = accept(l) ) { read(c, request) write(c, response) close(c) } Everything blocks (unless otherwise specified...) Our pipe implementation is weird. Less tiny web server: l = socket() bind(l, port 80) listen(l, backlog = 5) while( c = accept(l) ) { if(!fork()) { read(c, request) write(c, response) close(c) exit(); } } Why good? - can respond to all requests independently. - accept gets called again fairly quickly. Why bad? - - epic use of resources (a whole process!) per request. - and its implications for "security" - might run out of processes. We could do threads? Same advantages, Smaller resource consumption (no whole new address space) potentially can have many more threads than processes. Predictive? web server: l = socket() bind(l, port 80) listen(l, backlog = 5) while( c = accept(l) ) { read(c, request) if( request is not a big deal || !fork()) { write(c, response) close(c) exit() if I'm a child; } } Solves the long write problem, not the slowly-incoming request problem. Start of old apache-like. l = socket() bind(l, port 80) listen(l, backlog = 5) fork(); fork(); while( c = accept(l) ) { /* there's more here in real apache */ read(c, request) write(c, response) close(c) } Can rely on the kernel to give the connection to only one of the processes. Yay: Get some parallelism, without unbounded resource consumption. Can ALSO try the non-blocking versions of the calls. l = socket() bind(l, port 80) listen(l, backlog = 5) fork(); fork(); while( 1 ) { if c = accept(l) nonblocking { add c to our list of connections (per process, not shared) } foreach c in list of connections /* there's more here in real apache */ read(c, request) nonblocking if we need a request. solve tsp. write(c, response) nonblocking if we have a response. close(c) if we're done } This non-blocking system call solution requires CPU load of 400% while doing nothing. while(select( all the reading fd's I care about + the accepting one, all the writing ones I care about, 10 seconds )) { for all the reading ones, read (or accept on that one), for all the writing ones, write, close em if they should be. } Unix sockets Contrast with anonymous pipes - can bind (use a name) (anon can't / don't) - any one can connect - typically anon pipes have one direction Contrast with named pipes (pretty similar) - allow only one other endpoint to open. Signals kill() - send the signal. signal() - defines a handler sigaction() - defines a handler, nicer interface. sigprocmask - helps block (suspend) specific signals. Typically used signals (class participation!) SIGIO - would not otherwise be here, but we looked it up a minute ago as a signal delivered when a specifically configured file descriptor is ready. SIGSEGV - you used memory wrong. usually results in the process being terminated for its misbehavior. SIGHUP - the terminal session disconnected maybe they should die - e.g. mutt (mailreader), maybe they should save and quit: editor if there's no possible terminal (daemon) convention is to trigger a reload of config files. SIGINT - ^C. probably want to quit. SIGPIPE SIGUSR2 SIGUSR1 SIGKILL SIGTERM SIGILL SIGFPE SIGSTOP SIGCONT SIGCHLD # lecture 6 Editor Olympics; I apologize for giving you an assignment that turned out to be outside your ability. I tried it out, Justin tried it out, and we roughly halved the number of errors before creating the version for your assignment. The learning curve tends to start with the toughest errors, such as missing parens in include files, to fix first. I thought getting through project 0 would be enough preparation for this, and that turned out to be optimistic. This quiz will not count as a quiz; it will convert to homework for you to complete by feb 22. We are likely to revisit this exercise as a quiz in late April. Why this matters. .) I want you to recognize that the compiler can only complain when it realizes there's a problem, not where the mistake actually occurs. .) I want you to recognize that small edits without breaking the build, or which can be reviewed in case an error shows up in a bizarre location, are better than trying to write a large feature at once. .) I want you to complete the assignments this way. Edit a tiny bit. Compile. Fixup errors. Compile. Run. Test. See the next error. Repeat. Compile often. .) I want you to be able to someday decide in someone else's code that, e.g., a float should be a double, or a char * should be a const char *, or a function pointer should take an extra argument, or a class member variable should have an accessor, or..., then make the change by cleaning up what the compiler complains about. .) I want you to develop a bond with your editor, like a soldier with his or her rifle or a chef with his or her knives. The editor is your most important tool. Lessons in general. .) We fixed at least a few environments so that "make submit" works. I'm happy about this. .) Maybe flailing at the error messages for 30 minutes, knowing that the mistake is not on the line given, will prevent you from later staring at one specific line. .) Several people used google and found stackoverflow pages; I suspect these were entirely unhelpful. .) Surprisingly, no one (that I know of) commented out blocks of code temporarily to see what would happen, or added braces or parens in potentially the wrong place. Justin demo'd a vim-based edit. Let me run an emacs-based version now. - note the syntax highlight. the parser underneath the syntax highlighting can catch some issues. - note the ability to jump to an error. - M-x compile with command : "cd ../../build && make" or (less happy about finding the file with an error:) "make -C ../../build" - C-x ` is next error http://www.gnu.org/software/emacs/manual/html_node/emacs/Compilation-Mode.html http://nolandda.org/pusite/emacs.html You may use Eclipse, I guess; it seems like too much dashboard and too little windshield to me. Xcode might work. TextMate: open up build/Makefile and hit command-B. -- Getting all user-printed strings out to a console somewhere. make dbgrun make dbg break Put_Buf continue (just 'c') display buf c -- Signals cont'd. list above. reference material (more detail than I know) http://www.gnu.org/software/libc/manual/html_node/Signal-Actions.html#Signal-Actions void siginit_handler(int signum) { done = 1; Print("ack!"); } main() { signal(SIGINT, sigint_handler); while(!done) { something important, digits of pi } print out the result so far. } Two delightful functions "setjmp" and "longjmp" - at user level, store the current state of registers or load a stored state. - permits user-level threads. Danger: A signal may interrupt a system call. EINTR is returned. Danger with threads . Implementation challenge in geekos: process has two contexts! # lecture 7 Reference counting basics. Problem: Must use explicit memory management in the kernel, and typically use explicit memory management in C. CANNOT stop the world to collect garbage. The interrupts continue. When objects float around in a shared memory space, they may acquire references. Malloc() an object, then insert it into a data strucutre,... who is responsible for free()ing? Goal: Permit objects to acquire references, know when to free or destroy (or sigpipe, for example). Method: We will use a reference count: an explicit count of the number of (long term) incident pointers on an object. We will maintain the count ourselves. Alternatives: One could establish a protocol for who is responsible for free()ing an object, maybe remove_from_list should do it. This works for simple problems. Concretely: fd_table -> File -> Pipe. File has one reference. pipe has one reference. fd_table1 -+> File -> Pipe. fd_table2 / File has two references. pipe has one reference. Do we need to increment a reference count in the Pipe? no. Should we increment a reference count in the Pipe? no. Is it bad if we do increment a reference count in the Pipe? only if you don't decrement it where needed. So what should Close() do now? Note: Geekos may not be very good about maintaining reference counts in general. In particular, each thread has an "owner", and references from children do not actually count as a reference enough to keep the parent object around, which means that the owner pointer could become "dangling", which means that using it could cause trouble. You could fix. Compare to Objective-C retain - increments the reference count release - decrements the reference count also autorelease release, but wait to free until... sometime. Implication for p1. setjmp/longjmp, quoth the man page: The sigsetjmp(), setjmp(), and _setjmp() functions save their calling environment in env. Each of these functions returns 0. The corresponding longjmp() functions restore the environment saved by their most recent respective invocations of the setjmp() function. They then return, so that program execution continues as if the corresponding invocation of the setjmp() call had just returned the value specified by val, instead of 0. What does this mean? This is the engine for a user-level fork(). The registers are stored once, and brought back twice. Behind the scenes, longjmp alters the environment while restoring to return a particular value. The Point. (a) there is such a function at user level; this is part of the standard c library, right next to strlen(). It is a function that returns twice. This is not fork() that returns twice, because fork() returns in two different processes. setjmp() can return twice typically to init a new thread or to handle an exception (longjmp to the top of a rescue or catch block) (b) there is no such function in the kernel. It is your task to construct it, and possibly to construct it a few times. Your advantage is that the .asm files in geekos do an admirable job of copying the register context off the registers and onto the current thread's kernel stack whenever an interrupt occurs. -- Threads. Can do threads at the user level. Many threads, but just one process, kernel recognizes only one thread. Advantage: - have control. app can choose which thread goes next, whether to switch. - switching can be fast. can just load the new ip and esp and be switched. - creation can be fast. don't need to tell the kernel. Can do threads at kernel level. Many threads, kernel knows about each. Advantage: - a blocked kernel thread means you go to the next one. (user level threads set i/o to nonblocking, or guard reads with select.) - can use all the processors. but be careful, that means race conditions, or locking, which can be tricky, and can also require kernel help when you have to block. How many threads should you have? # threads = # processors # threads = # processors + # expected blocked threads extra threads may not pay off. - more threads consume more memory - want locality: want to keep just a few threads running so that the cache gets used, so that we stick to the same stack, so we have fewer page faults. - time to switch (don't want too many active threads) - subdividing the job into too many workers means they don't do enough to be worth the cost of switching, or the just block all the time. - programmer hassle Can be tempting to create one thread per operation you might want to complete. e.g., per request to service. - seems like a good idea, until you get a lot of requests. Thread pool. requests go onto a shared queue, idle threads wait for requests, grab them, service them, return to idle. - don't waste time creating them or joining them IOCP as if there is an underlying shared queue, only the requests (receipt of message on a socket, new connection received) map to handlers much like signal handlers. Kernel threads on linux: underneath pthread_create() and fork(), is a system call called "clone()". preserve/share some set of attributes. e.g. file descriptors; address space for thread. Race condition (close) two threads accessing same data at the same. two threads might write in different orders, changing what you might read. multiple execution orders can have multiple outcomes. execution of a program depends on the schedule program loses correctness because some data is incremented incorrectly. can't tell in advance what the outcome is going to be. undesirable, inconsistent result caused by non-deterministic ordering of concurrent operations, at least one of which is a write (or side-effect) Disable_Interrupts and Enable_Interrupts. In this class, when in doubt, keep the interrupts disabled. --- Exceptions: Exception 13 received, killing thread 0x00032000 eax=00000000 ebx=00000000 ecx=00000000 edx=00000000 esi=00000000 edi=00000000 ebp=00000000 eip=00025825 cs=00000008 eflags=00000012 Interrupt number=13, error code=0 index=0, TI=0, IDT=0, EXT=0 cs: index=1, ti=0, rpl=0 ds: index=0, ti=0, rpl=0 es: index=0, ti=0, rpl=0 fs: index=0, ti=0, rpl=0 gs: index=0, ti=0, rpl=0 --- eax=00000000 ebx=00000000 ecx=00000000 edx=00000000 esi=00000000 edi=00000009 ebp=00000000 eip=00001009 cs=00000007 eflags=00000246 Interrupt number=6, error code=0 index=0, TI=0, IDT=0, EXT=0 user esp=00000000, user ss=0000000f cs: index=0, ti=1, rpl=3 ds: index=1, ti=1, rpl=3 es: index=1, ti=1, rpl=3 fs: index=1, ti=1, rpl=3 gs: index=1, ti=1, rpl=3 --- Exception 13 received, killing thread 0x0000f000 eax=ffff081e ebx=00006000 ecx=00000009 edx=00002930 esi=00006000 edi=00000000 ebp=343b3733 eip=00003fbc cs=00000007 eflags=00000296 Interrupt number=13, error code=0 index=0, TI=0, IDT=0, EXT=0 user esp=00003e05, user ss=0000000f cs: index=0, ti=1, rpl=3 ds: index=1, ti=1, rpl=3 es: index=1, ti=1, rpl=3 fs: index=1, ti=1, rpl=3 gs: index=1, ti=1, rpl=3 --- qemu: fatal: Trying to execute code outside RAM or ROM at 0x031ccba6 EAX=00000000 EBX=0000286d ECX=00000008 EDX=0000285a ESI=00000012 EDI=00000000 EBP=00005f98 ESP=00005f48 EIP=03021c0e EFL=00000202 [-------] CPL=3 II=0 A20=1 SMM=0 HLT=0 ES =000f 001aaf98 00006fff 00c0f31a CS =0007 001aaf98 00006fff 00c0fa1a SS =000f 001aaf98 00006fff 00c0f31a DS =000f 001aaf98 00006fff 00c0f31a FS =000f 001aaf98 00006fff 00c0f31a GS =000f 001aaf98 00006fff 00c0f31a LDT=0038 001dad7c 00000010 0000821d TR =0018 00030a00 00000068 00008903 GDT= 000308e0 00000100 IDT= 0002f3e0 00000800 CR0=00000011 CR2=00000000 CR3=00000000 CR4=00000000 DR0=00000000 DR1=00000000 DR2=00000000 DR3=00000000 DR6=ffff0ff0 DR7=00000400 CCS=00000044 CCD=00034fec CCO=EFLAGS FCW=037f FSW=0000 [ST=0] FTW=00 MXCSR=00001f80 Aborted -- "The critical section problem" - only one program can be in its critical section at a time. - "progress" - processes outside their critical section cannot block those that are waiting to enter. - "bounded waiting" - can't have to wait an indefinite amount of time to enter. - cannot assume anything about speed of cpus. Dumb initial thing: a "lock" variable (not gonna work) lock = 1 if held, lock = 0 if not. acquire the lock (enter critical section) while(lock != 0); lock = 1; release the lock: lock = 0; bunch of problems. two threads could leave the while loop at the same time. y86 version of the while loop/acquire. While: mrmovl %eax, $Lock andl %eax, %eax ; I don't add zero because that ; instruction is longer or requires ; a register having zero. jne While irmovl %eax, $1 rmmovl $Lock, %eax -- Two keywords that instruct the compiler where to leave a variable: "volatile" - ALWAYS go to memory. "register" - probably just keep in a register. -- Alternate (if you have only two) turn = 'A' Thread A: lock: while(turn != 'A') ; /* spin */ unlock: turn = 'B' Thread B: lock: while(turn != 'B') ; /* spin */ unlock: turn = 'A' Safe: two threads won't hold the lock at the same time. If it's B's turn, but B doesn't want to take it, A will just wait forever. (missing "progress" requirement) Peterson's solution volatile int turn; volatile bool flag[2]; lock: flag[me] = true; turn = him; while(turn == him && flag[him] == true); unlock flag[me] = false Bakery algorithm: // 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 } -- Spinlocks lock that does what we wanted with that initial while loop want the ability to claim a lock atomically. two instructions enable spinlocks. xchg (exchange) - swaps a register with memory atomically. tsl (test and set lock) - sets the memory value to one, providing a zero if it wasn't one already. (if xchg with value "1", you get tsl) atomically: pretend the world stops for this instruction to execute to completion. cannot observe partial completion of the instruction. instruction does a lot. (expensive in what it does to the hardware, caches, memory bus, etc.) -- implementation of spinlock 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. --- you could do the while test without xchg so as not to burden the hardware, then when the while test suggests it's unlocked, do the xchg. maybe it works, maybe someone else grabbed the lock. restart if so. If you have to spin for a long time, you're doing it wrong. --- Two operations on a semaphore: acquire/P/wait/proberen/down/decrement release/V/signal/verhogen/up/increment P operation: if value is zero, block (else) if value positive, decrement. V operation: if anyone blocked, awaken one. (else) if no one blocked, increment "block" means waiting on a queue. i.e., your kthread is on a queue. i.e., not while(value == 0) -- feb 21 Signals project. "Background": ignore for the most part, though you may alter the shell to interpret a trailing "&" on the command line as preventing the call to Wait(). (thus creating the background process) (Then do what you like with the zombies... there is WaitNoPID.) If you care: fork()ed children inherit signal handlers. exec()'d programs reset signal handlers to the default. (because the handlers aren't there anymore) You need not care; all (or all but one) tests use Spawn() No signals to kernel (non-user) processes. Return EINVALID. My (mac) sigaction man page says: When a signal condition arises for a process, the signal is added to a set of signals pending for the process. If the signal is not currently blocked by the process then it is delivered to the process. Signals may be delivered any time a process enters the operating system (e.g., during a system call, page fault or trap, or clock interrupt). If multiple signals are ready to be delivered at the same time, any signals that could be caused by traps are delivered first. Additional signals may be processed at the same time, with each appearing to interrupt the handlers for the previous signals before their first instructions. The set of pending signals is returned by the sigpending(2) system call. When a caught signal is delivered, the current state of the process is saved, a new signal mask is calculated (as described below), and the signal handler is invoked. The call to the handler is arranged so that if the signal handling routine returns normally the process will resume execution in the context from before the signal's delivery. If the process wishes to resume in a different context, then it must arrange to restore the previous context itself. My (linux) fork() man page says: The child's set of pending signals is initially empty (sigpending(2)). Which one first? likely undefined. accidentally works by ordering lower numbers first? - but that doesn't quite apply to kill -9 on unix. If sigusr1 handler was running and not very smart (infinite loop), would sigkill get processed? - can't handle sigkill anyway Three sigchlds at precisely the same time would cause the handler to be invoked only once. -- Producer / Consumer problem. Have (at least) two processes producers create things, put those things into a buffer of finite size consumers that use/eat those things, clearing space in that buffer. Producers and consumers can act at different rates. Goal: producers block when the buffer is full. consumers block when the buffer is empty. How many semaphores do we need? Three - one for the shared data structure one to stop the producers one to stop the consumers Initial condition: buffer is empty. buffer has (empty) space for 10 produced things. consumers are blocked. (how many of the little cells in the buffer are:) Cells_Full_Sem should have value 0 Cells_Empty_Sem should have value 10 Mutex should be unlocked (have value 1) consumer: while(1) or while not satisfied { wait(Cells_Full_Sem) (aka P(Cells_Full_Sem)) wait(Mutex) i = get_thing_from_full_cell_in_buffer() signal(Mutex) (aka V(Mutex)) signal(Cells_Empty_Sem) -- tells a producer that it can make more things. eat(i) } producer: while(1) or while not done making { i = make_a_thing() wait(Cells_Empty_Sem) wait(Mutex) put_thing_into_empty_cell_in_buffer(i) signal(Mutex) signal(Cells_Full_Sem) } Reader / Writer locks. goal: permit concurrent reads but prohibit writes while anyone else does anything (read or write)) read access is shared write access is exclusive can set it up so that either: readers aren't stopped by a waiting writer writers aren't stopped by an endless stream of readers. option one: need two semaphores One semaphore represents the exclusive access (writer or group of readers) Second semaphore guards the count of readers. Initial value of both semaphores is 1. writer: wait(exclusive_sem) perform write signal(exclusive_sem) reader: wait(readers_sem) num_readers ++ if num_readers == 1 wait(exclusive_sem) signal(readers_sem) perform read /* might do a lot more while holding a read lock. foreshadowing transactions */ wait(readers_sem) num_readers -- if num_readers == 0 signal(exclusive_sem) might be a different reader from the one that waited. signal(readers_sem) option 2 may add a semaphore to ensure that a blocked writer-in-waiting blocks further readers from starting. writer: wait(extra_sem) wait(exclusive_sem) perform write signal(exclusive_sem) signal(extra_sem) reader: wait(extra_sem) wait(readers_sem) num_readers ++ if num_readers == 1 wait(exclusive_sem) signal(readers_sem) signal(extra_sem) (rest of reader unaltered: in particular, cannot require the extra_sem to unlock) Condition Variable add a "signal all" operation. *everybody* waiting will awaken. have a "signal" operation awakens one currently waiting thread. signal has no effect if no threads are waiting. have a "wait" operation that always waits. Monitors include synchronization in the programming language to guard functions/methods with the same wait and signal. Producer / Consumer in a monitor context that third semaphore doesn't have to be there (because shared access is dealt with by the monitor) but we still need two condition variables: monitor thebuffer { int cells_in_use const int cells_in_total condition_variable cv_not_full, cv_not_empty; produce_into_buffer(thing) while(cells_in_use == cells_in_total) wait(cv_not_full) <- can only be awakened by a signal add_thing_to_buffer(thing) cells_in_use ++ signal(cv_not_empty) <- if no one waits, signal goes poof consume_from_into_buffer while(cells_in_use == 0) wait(cv_not_empty) thing = get_thing_from_buffer cells_in_use -- signal(cv_not_full) } wait() operation will give up the monitor Tue Feb 26 Signals various p2 tests were written by one of your predecessors a few tests provide bad input to check that you reject it. e.g., reject attempt to signal a kernel process. default signal handler is to: ignore sigchld die on all other signals. "ignore" signal handler allows you to: ignore all signals except KILL. (without providing an empty function signal handler) I/O (p3) devices operate somewhat autonomously programmed io / port-based io outb outw write a byte or word out to a specific "port" inb inw device is on a bus set the address bits on the bus to be the port address set the data bits to be al or eax. (or read the byte(s) in) set some bit that says whether we're reading or writing what happens after an "out" might configure the device send a byte to a peripheral more(?) basic. if you wanted to do everything with this, it would be tedious. (unless very slow device) every device should have a unique address. memory mapped io (we won't do) burn memory address space to talk to devices. device will watch your "store" instruction or rmmovl instruction to see if you're writing to a specific region. If so, you might be trying to manipulate the pixels on the screen. somewhat faster, potentially a little wasteful of address space. direct memory access wire up a device to read from or write to an area of memory, directly. offload the task of shuttling bits to the direct memory controller at the end of the DMA transfer, device might issue an interrupt. hardware interrupts (controller that must be managed) As applied to sound driver: play sound don't want it to stop don't want it to skip don't want to get the sampling rate wrong One way to have no interruption: load the entire song into memory tell the device to DMA the entire song. (not allowed) Apparent scheme (double-buffer-like) Have a fixed size buffer. (page aligned) Split it in half. While the card works on one half, we can write the other. When the card is done with a half, it will generate an interrupt. Small buffer may be better for sound effects. Large buffer easier for music. Deadlock threads stuck waiting on each other. Four conditions of deadlock: 1) mutual exclusion (finite resouces). there's something to fight over. 2) hold-and-wait. threads hoard. 3) no preemption. locks / resources cannot be confiscated. 4) circular wait. a cycle in the "waits for" graph. graph where nodes are threads, directed edges represent a depency where a thread is waiting for a resource held by another. Three ways to deal with deadlock: prevention - get rid of one of these conditions avoidance - stay out of unsafe states detection - find it and terminate Prevention: Circular wait: order your locks. Hold and wait: a) new rule: can hold only one lock at a time. b) hard-to-implement feature: grab all resources at once. c) easy-to-implement: have only one lock. (kills parallelism) No preemption: Have preemption. Maybe some resources can be stolen. Memory pages might be possible to "steal". Mutual exclusion: Maybe if the resource is actually sharable but you're being conservative about it, you could relax this. Reader/writer locks... not actually exclusive for reading. Deadlock is not starvation: starvation is just that a thread doesn't get to make any progress in practice (because of timing). There is a way out, you just have to wait a while. In deadlock, there is no escape. Deadlock avoidance: Stay in a "safe" state. Deny access to resources, not because they're all allocated, but because doing so would lead to an unsafe state. "Safe" state means that all the threads can finish, even if they ask for everything they could possibly ask for. Assume that we know the limits on what a thread can ask for. Super trivial deadlock example: T1: wait(s1) wait(s2) signal(s2) signal(s1) T2: wait(s2) wait(s1) signal(s2) signal(s1) T1: wait(s1) deadlock! T2: wait(s2) T1: wait(s1) wait(s2) signal(s2) signal(s1) T2: wait(s2) wait(s1) ... Deadlock avoidance prevents T2 wait(s2) from happening in order to ensure T1 has a path to termination. Deadlock avoidance will require knowledge that T1 may wait for s2. (and that T2 will do the same). If I allow T2 to get s2, what happens? If T2 could finish with just s2, we would be okay (but T2 may still need s1) T2 could finish, then allowing T1 to finish. Since T2 might also need s1, and T1 might also need s2 unsafe! to give T2 s2. Banker's Algorithm Goal of the bankers algorithm is to ensure that every thread can finish. what it has plus what it could possibly want is still available. (possibly by the completion of other threads.) (temporarily skip deadlock detection) Transactions little tasks, executed concurrently, fine locking, durable result. think big database systems. (can apply same lessons to OS resources.) ACID properties. Atomicity - either all operations happen or none do. Consistency - rules are enforced (don't break the database) Isolation - each transaction runs as if independent, serializable Durability - once complete, results are stored forever. one can commit or abort (and you might have to try again). if in deadlock, can just abort. provides preemption. - have to recognize that we're in deadlock. (also postponed: two-phase locking.) Thu Feb 28 Outline: Project 2 issues, if any. - bug in Wait that manifests when called twice before thread is completely destroyed. (I'll fix, eventually.) - with fork - copy handlers, clear pending for child. - with exec - handlers not valid across exec. (see line 1180) Project 3 posted. - and on submit. No "scheduler due" deadline on march 8. Banker's algorithm (deadlock avoidance) Two phase locking Deadlock Detection Processor Scheduling (out of order from the schedule) Banker's algorithm 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.. 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. Will giving this resource lead to an unsafe state? if so, block. (not really sure for how long.) "pretend" we've provided the resource, invoke is_unsafe_state helper. while it returns "unsafe", block on a condition variable. Is this resource available in the first place? if not, block as normal. (optional, I think - getting a resource that's not available should trigger the unsafe state) Two Phase Locking Feature for isolation (in the ACID list). No other thread should be able to see the partial results of a transaction. (because a transaction happens as an atomic unit at one point in time). growing phase, shrinking phase. acquire all locks, then release all locks. (no acquire/release/acquire/release) transfer money from account a to account b unguarded(bad): a += 100; b -= 100 guarded(good): lock(a), lock(b) a += 100; b -= 100 unlock(a), unlock(b) awful: lock(a), a += 100; unlock(a) lock(b) b -= 100 unlock(b) (why? permits someone in the middle to see "a"+"b" with extra balance) typically, you'd commit() to disk before releasing a lock, unless you're really eager for performance and want to tolerate the complexity of undo()-ing transactions that depend on the results of an aborted transaction. Deadlock Detection Dining Philosophers. Forks. Deadlock is possible. everybody asks for left fork first, nobody gets right fork. everyone hungry. no one eats. Can prevent deadlock by not doing hold and wait: get left fork. if right fork available, get right fork. else, release left fork, wait(rand(1000)) (* generally discouraged to have a random wait time, at least in OS. *), retry. monitor-based solution: test( philosopher_idx ) if philosopher_idx + 1 (% table_size) is not eating and philosopher_idx - 1 (% table_size) is not eating and philosopher_idx is hungry set philosopher_idx to eating! signal_all() end end pickup(philosopher_idx) set philosopher_idx to hungry test( philosopher_idx ) while(philosopher_idx is not eating) wait() end put_down(philosopher_idx) set philosopher_idx to speaking test( philosopher_idx - 1) test( philosopher_idx + 1) end end Deadlock detection. Waits for graph. edges represent ownership of resources and waiting for those resources Then what? in transaction land, you abort (easy) in, say, geekos, terminate a process. reclaim its resources (have to find them all) pray that doing so doesn't leave more inconsistent state. choose which process to kill out-of-memory killer - some process has to die. which one? policy decision: new (hasn't done anything)? old (likely to be at fault)? has few resources (less to undo?) has many resources (most likely to solve the problem?) most recent request (?) least privledged process (?) Review: four conditions of deadlock four components of the critical section problem deadlock prevention vs. avoidance vs. detection. condition variable signal vs. semaphore signal condition variable wait vs. semaphore wait Tue Mar 5 Project 3 "initial work" Goal - determine whether the sound card is present. tests look for: SB16 found: version %d.%d - or - SB16 not found Find in the docs the "reset" sequence. "version" query command. Look in the C++-based example Poke around in another driver that uses Out_Byte to determine the specifics. If section happens tomorrow: due that evening (7pm) If section does not happen tomorrow: due friday evening (6pm) What's due: test-detect-true, test-detect-false You know how to frob [make small alterations to] .submit. Processor scheduling Goals / Metrics: waiting time: time spent ready but waiting turnaround time: execution plus waiting time (to completion) response time: time to first results (which may == turnaround) ratios: maybe execution time / turnaround time is what matters. Two idealized schemes: FIFO (first in, first out), SJF (shortest job first). or FCFS (first come, first served) FCFS one cashier at CVS (before the automated things) it means you stand in line forever despite having only a tiny thing to buy because someone wants who-the-hell-knows what. An individual, long task can create waiting time for every short job that follows. SJF reorder the queue so that the longest task runs last. might even preempt assumes magic / oracle knowledge of how long any task will take. advantage: short jobs don't have to wait for longer jobs to get out of the way. disadvantage: long jobs may starve. might not want that. Round-Robin (an actual scheme, though not necessarily good) Run each task for a *quantum*. e.g., 10ms or 100ms Long task gets a quantum, and we move to the next task. Short tasks should finish. Advantage: some level of fairness. Disadvantage: if you give up your quantum for I/O, you don't get that time or priority back. context switching - stop the processor, save the registers, performance from cache is likely lost. might prefer to just finish some process, rather than give each process roughly equal waiting time. (might be a general problem for all our scheduling algorithms). -> medium term scheduling : try to swap out processes so that there's more room for processes that are likely to finish. -> or bump up the priority of chosen processes Want to support a mix of I/O and CPU-bound processes. Another near-impractical scheme: Max-Min fairness. Goal: provide the largest minimum allocation possible. (make the CPU-poorest job as CPU-rich as possible) (don't really care so much about the rest, as long as the CPU is busy) Maintain counters of how much cpu each process has used. At each point where we can make a scheduling decision, provide the cpu to the process that has used the least. (Probably recompute over some interval to ensure that the scheduling doesn't get stuck if a process's I/O-bound-ness changes.) Multi-level feedback queue: Instead of just one RR queue, we have several. Highest queue is for the processes that don't use the CPU (don't use up their quantum) Lowest queue is for the processes that only use the CPU (use up even a large quantum) Can have several levels. Assumes that processes that have blocked recently will block again soon. Could try to trick the MFQ scheduler: Run until just before your quantum expires, then block. (can't ask for something that the OS can just give you from its cache... that wouldn't count) Why a longer quantum for the lower levels? If we're running a low-level, cpu-bound process, then maybe he needs the cache, and the only other processes we'd want to run are the same. (and we can always switch to an interactive job if we see an interrupt) Starvation possible. Can combat starvation by increasing the priority of processes that aren't getting a fair share of the processor. Suggestion: If a particular (high) queue is using up all the actual cpu time, then go down to later queues. Directions: multiple processors, multiple users. Multi-processor. Could have a simple version where some processors handle the long running stuff and other processors handle the short-running stuff. Don't *have* to interrupt the long running task to schedule the interactive tasks. Each processor has its own cache. Individual processes can gain "affinity" for a processor (want to stay there). Would rather leave processes on the same processor. Set of ready processes is shared. To grab a runnable process, OS running on a core has to grab the lock on the runnable processes, make sure that the run queue is in memory (not in some other processor's cache) and then pop off the next runnable job. -> per-processor queues (saves us this problem, but can create unfairness if some processors are overloaded.) say one processor becomes idle, may have to steal from another processor. Multi-threaded programs - You were probably hoping that each thread would go on its own processor. All sorts of other crap running. Short interactive tasks might delay one of the threads by a bit, causing the rest of the threads to go idle for a while. Also: if one of your threads holds a lock, then gets evicted, maybe all your threads will have to block. Goal: co-scheduling: all tasks like these scheduled together. Scheduler activations: idea is that we have the "problem" of processors becoming available, and we want kernel level threads (because we want all the processors) but we want to use the application knowledge to decide what to do with the new processor. SIG-I-have-a-cpu-for-you, which task do you want to run. Multiple users you might want to keep certain users from too much cpu utilization. - maybe system users that shouldn't need cpu in the first place. - maybe other students with runaway QEMU processes on linuxlab. there exist rlimits (resource limits), so you can set a cap on total cpu time of a process. CPU time - time on the cpu. Wall-clock time - actual, real time on a stopwatch. Thu Mar 7 Midterm Tuesday Format: ~30 MC, 4 short-answer, 2 longer or themed questions. Expect long answer question on the use of synchronization primitives: e.g., semaphores, condition variables, reader/writer, or spinlocks. Expect questions on programming assignment 0-3 content. (background on 3) As in every class, expect repeats from homework assignments and quizzes. P3 SB16 found: version %d.%d - or - SB16 not found ide.c Out_Byte(IDE_DEVICE_CONTROL_REGISTER, IDE_DCR_NOINTERRUPT | IDE_DCR_RESET); Micro_Delay(100); Out_Byte(IDE_DEVICE_CONTROL_REGISTER, IDE_DCR_NOINTERRUPT); ... Out_Byte(IDE_COMMAND_REGISTER, IDE_COMMAND_DIAGNOSTIC); while (In_Byte(IDE_STATUS_REGISTER) & IDE_STATUS_DRIVE_BUSY); errorCode = In_Byte(IDE_ERROR_REGISTER); floppy.c /* * Wake up any threads in the floppy wait queue. */ static void Floppy_Interrupt_Handler(struct Interrupt_State* state) { Begin_IRQ(state); Wake_Up(&s_floppyInterruptWaitQueue); End_IRQ(state); } screen.c /* Set the high cursor location byte */ Out_Byte(CRT_ADDR_REG, CRT_CURSOR_LOC_HIGH_REG); IO_Delay(); Out_Byte(CRT_DATA_REG, (characterPos>>8) & 0xff); IO_Delay(); linux sb_common.c int snd_sbdsp_reset(struct snd_sb *chip) { int i; outb(1, SBP(chip, RESET)); udelay(10); outb(0, SBP(chip, RESET)); udelay(30); for (i = BUSY_LOOPS; i; i--) if (inb(SBP(chip, DATA_AVAIL)) & 0x80) { if (inb(SBP(chip, READ)) == 0xaa) return 0; else break; } snd_printdd("%s [0x%lx] failed...\n", __func__, chip->port); return -ENODEV; } I don't necessarily recommend looking here for a lot of guidance, since the architecture is factored differently and the function calls are all different, but running code is often the best documentation. ** cite all sources (particularly sources with crappy code) ** Midterm Review PCB and contents Process states Distinguishing features of a process (vs. thread) Pipes, SIGPIPE, differences between P0 and reality. Also exist named pipes. Shell operations: ;, &&, ||. The test program. C: typedef, #define, const, function pointers, GeekOS list exec family functions, differences between P1 and reality. exec implementation, what is inherited / discarded fork, differences between P1 and reality. fork implementation, what is inherited / discarded Kernel stack and user stack Interrupts: traps, handlers, disabling Scheduling: short, medium, long, SJF, RR, FCFS, Multi-level feedback Segmentation and paging Interprocess communication methods: pipes, shm*, messages, sockets Sockets: streams/datagrams, functions, servers, select/poll Signals Threads, thread pools Critical Section problem Petersons Bakery, Semaphores (P and V) Condition variables and monitors. Producer/Consumer bounded buffer Bankers Dining philosophers Four conditions of deadlock (list not exhaustive.) Mar 14 Project 3 Midterm review. Review individual exams with TA's. Collaboration policy reminder. Two key features: take home exam, cite all sources, including discussion with other students. Virtual memory overview / P4 Standard mapping memory hierarchy: registers (fast, $$, small) L1 cache L2 cache L3 cache (if there is any) memory ssd? disk cache? disk - could be page-file/swap, could be files cloud? tape? what does this tradeoff make us do? - have to transfer data from slow to fast for processing - spend time on prediction algorithms to exploit: - spatial locality - likely to access an object close in location in memory/storage. - temporal locality - likely to reuse objects soon. - also programmer needs to know how to iterate through data so that requests hit in the cache. - compiler optimizations frustrate debugging opportunity to give processes the illusion that the machine has as much memory as there is disk, dedicated to that process. if we want to do this (hold more stuff "in memory" than we actually have memory for), how? (there once was a scheme where a little program would temporarily compress your code in memory) 1. copy the whole segment to disk, release the segment, run another program by loading it into memory. 2. "overlays" allowed programs themselves to load different pieces of their code. 1. init code 2. teardown code 3. exceptional code (assumes an individual process can and wants to manage its own memory) 3. paging. keep all of the processes running by having at least what the process needs to make progress. Need help from the processor: Processor has to identify memory references from the process that cannot be satisfied immediately. - cold miss (maybe the first instruction to run) Page directory base register. Identity mapping March 26 Paging Give every process the illusion of its own memory Allow sparsely used address space Page out unused parts of the address space better than (just) segmentation. The bits Present/Valid - if not present, changes the meaning of the entry. (we can use it) - can keep track of where the page is on disk in these 31 bits. Dirty - if we've written to the page (since copying the page to disk, assuming we've done that at all). Accessed - our one hint from the processor to help pick a good page to evict. Hierarchical Pageable TLB Page replacement Optimal (impossible) policy: The best possible choice is to evict the page we're not likely to use again for the longest possible time. LRU the page we haven't accessed for the longest time. (expecting that this will predict the page we won't access for the longest in the future) - would need at least enough bits to keep track of order. - maybe enough bits to keep track of timestamp. - or some sort of list / heap (maybe) HOWEVER: bad enough we have to do one memory access, do not want to compute things on each access. Not MRU (invention in 412.) what's the last page accessed, evict on that's not that one. Random Not MRU without keeping track of most recently used. FIFO Evict the page that's been there the longest. Nothing to do with accesses. FIFO + Second Chance. (\approx "Clock") Same FIFO queue, except when an entry reaches the front of the queue, check the accessed bit. If set, move to the end of the queue, if not, evict. Clock - Same queue like behavior, just don't think of it as a queue, instead think of advancing hand(s) of a clock. Working Set algorithm. "WS+Clock" Define a time \tau for which pages accessed within that time are in the "working set", and are thus important, and pages outside the working set are not. -> while advancing the clock and clearing the accessed bit, remember what (actual) time it is. (the "time" on the clock is just what page you're on.) What does it mean when your clock is moving too fast? using a lot of memory - not only is it all allocated to things, but these pages are getting touched. - could be thrashing. - or all the pages are dirty and we need to spend time cleaning them NOTE: clock hand advances when we need a page. (not on its own) Cleaner hand vs Evictor hand - want the cleaner far enough ahead of the evictor so that clean, not accessed pages will be available >= 15ms - want the cleaner hand far enough behind the evictor so that the processor has a chance to access pages again and we dont unnecessarily clean a soon to be dirty again page. - and there's a lot of time to dirty the page again. opposite? IF we have a "cleaner hand" -> could use idle disk time to make sure there are enough clean pages around. This structure could be kind of big - maybe use the 4MB pages more? "Demand Paging" - additionally implies that you don't generally give a process a page until that page is referenced. - if you have a page fault handler, use it. (don't add pages to the address space any other way) What do we do when we're really out of memory? - kill a process. options: - one using the most memory - the one asking for memory - youngest process - oldest one (likely not good, since oldest process is init...) - oldest (non-root) user process (probably not that good either, since that's probably gdm/xdm...) - return malloc() failed? - we've actually oversubscribed the memory by using thee virtual address. - banker's algorithm-like: suspend the guy until someone else finishes and leaves us with enough memory to continue. (or medium term scheduler like) (we haven't done any banker's like accounting, so it might be too late) Mar 28 Clarifications from last time: a) the clock algorithm runs over the pageable pages in the system, while the page table is a per-process structure i.e., to find the accessed bit, the pageable page structure has to know to what process(es) the page is mapped and its virtual address. b) (system-wide) out-of-memory isn't just a problem of refusing malloc() because malloc mostly just maps addresses for you, it does not (necessarily) commit pages to your use. Refusing malloc() might help, since odds are some programs will crash and give up their memory because of it. i.e., the OS provides an illusion of 4GB of independent address space memory per process, in the hope that no process actually uses all the memory to which it's entitled. If the processes actually use it, trouble. Additional stuff. c) Recognize that disk access latency is approximately quantum sized. While a page is fetched from disk, must suspend the program that caused the fetch to happen, and move on to the next process. can't leave the processor idle for 10ms! - so this happens for all disk accesses too. d) What pages of memory aren't pageable? page directory? if you're not going to run the user process, then you could probably put its page directory down to disk for a while. current/active page directory. (impossible to have on disk. processor would explode.) any memory a device is going to use (DMA buffer) either you have a region that doesn't get used this way (e.g. for the display) or you "lock" the page so that it must stay in memory. e) What about the 4MB pages? - kernel has to keep them, aligned and ready. - programs have to use them well, not sparsely. - think "PAE" acronym f) Belady's For some page replacement policies, more memory can lead to more page faults. using fifo replacement: 123412512345 f1 1 4 5 - f2 2 1 - 3 f3 3 2 - 4 9 faults. 123412512345 f1 1 - 5 4 f2 2 - 1 5 f3 3 2 f4 4 3 10 faults the system call: mincore() memory -> files transition. we have memory, we don't let it go to waste. - typically all the idle memory will be consumed by the buffer cache. It's okay! That's the kernel trying to speed up your actual I/O can map files into memory: means that the backing store is not the page file but is instead an actual file in the file system. Should commit changes to the file whenever the pages are dirty. memory-mapped files can be the mechanism that fopen/fread uses. - probably not a good scheme for massive files, since 32-bit address space is pretty limited. Files named array of bytes, probably on disk and persistent. attributes/metadata: access permissions: owner, group, read/write/execute, visibility, append-only, sticky bit! (sticky bit on a directory like /tmp allows anyone to create files (write to the directory) but not delete other people's files (which is also a write to the directory) size, timestamps! creation, access, modification. Operations: open and create, close, read, write, seek, mmap mess with the metadata: stat, touch, chown and chmod unlink/remove/delete, rename, Directory operations. mkdir, rmdir, opendir, readdir, closedir, seekdir. Because the file system may implement directories differently, we need the file system code to interpret that and hand the user code entries in the "file" that is a directory. The inode structure that represents a file on disk (but no bytes) each inode has a number that is the unique identifier of the file on the file system. the inode holds the metadata. inodes are reference counted. the blocks are referred to by this inode. indirect, doubly-indirect, triply-indirect access. inode directly refers to the block large and small files both referred to by a fixed size inode. April 2 project 4: intel manual section 4 has the good stuff, revised. stack can grow, use the rec.exe command to blow the stack. 3 page tables for 10MB. pagefile size issue (just use what's there) 20 bits identify the page, 12 bits pass through - must deal with shifting the 20 bit values to use them as pointers. Disk cylinder - all stuff reachable at the same position of the arm track - combination of a cylinder and a head/platter heads - number of read/write heads (twice the platters, assuming two-sided platters. sector - piece of the circle defined by a cylinder. What takes time? spinning - could have to wait nearly an entire rotation for data to reach the head. 10,000 RPM - 6ms max, 3ms expected. moving the arm - accelerate, decelerate, stabilize, longer to move the arm farther. actually reading or writing - assuming you're in the right place, have to have the data pass under the head. way slower than a processor (processor can do lots of other things while waiting for the disk) can make a group of disk requests take less time by scheduling them can also prefetch - e.g., just read the whole track outer edge might have the highest number of bits per unit time. read/write throughput. inner edge might be closest to the head parked location, which might make accesses from idle fast. keep data together to enable the prefetch. data in a middle cylinder would be quickly accessed by limiting the distance the head has to travel when trying to access that data. File Allocation Table (FAT) table that collects oll of the next pointers. allows us to seek without loading all the blocks to find the next pointers. allows us to have fixed size directories. one place to know what the state of all the blocks is. best case: table fits in memory. directory: array of fixed size structures (because filenames are fixed size) that reference the start block of the file. free space: can track as a big file. files can get "fragmented" (not external or internal fragmentation, just that file contents can get scattered; free space can be scattered. leading to more file contents being scattered) what else is not good about FAT? fixed limit on the size of a file. (fat16 and fat32) fixed size name. limited size volume. consume memory for the file allocation table. (based on the size of the disk, not the size of the stuff you're actively looking at.) P4b - So... the tests for paging to disk aren't discriminating at the moment. "Oh noes! test transcript entry" - send me a note. Next week, Aaron Schulman. Filesystem - data structure that lies on disk. have to decide about all the data types in all the structures so that other machines can read the same file system. ensuring the data structures have just one representation that does not vary by architecture: stdint.h - file that defines integer types by size. uint32_t directory. in implementation, a directory is pretty much a file. fat: array of file structures that maps fixed-length name to the start block, size, date, etc. unix file system: concatenation of variable length "dirents" that map a name to (the index of) an inode (in the array of inodes). allows the unix file system to have "hard links" which are multiple names for the same actual file. contrast the "soft link" which uses a name -> name mapping. opendir, readdir, closedir when formatting a filesystem that uses inodes, decide at the start how many blocks will be used by inodes, and how many blocks will be there for data. inode: direct blocks (some number) indirect blocks doubly-indirect blocks triply-indirect blocks more? minor goal: ensure that inodes don't span block boundaries. can create sparse files. i.e., blocks I haven't written yet in the middle of my file are provided to me as zeroes. how do we keep track of free blocks when using inodes? what are the entries in a free block table? ranges? free block bitmap? ranges as RLE version of a bitmap... might be able to do best-fit placement easily with an RLE. RLE = run length encoding "fast file system" cylinder group - find a way to split the inode array so that the inodes are near the data that they reference. function(inode number) -> start block of that cylinder group. "tail packing" - scheme for sharing the 'last' block of a file. NTFS "extents" kind of like segmentation for your file system. almost just RLE compression over the blocks in the list of blocks referenced by an inode (with the exception that the expected value of the next block is previous + 1) April 9 - Aaron Schulman lecture I. 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. LOOK/C-LOOK make the obvious optimization over SCAN. Distinction unimportant. April 11 - Aaron Schulman lecture II: Intel arch. April 16 Project 4 cleanup "Clock" is an instance of FIFO + Second chance; there is one global pointer that is the "clock hand", it advances only when needed (when Find_Page_To_Page_Out is called). Pseudo-LRU is likely what you implemented: record the time when the access bit was cleared, evict the one with the longest time. Project 5 a: format b: read (most) c: write Observe pfat.c Use hexdump -C image | less 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) scenario: two request-heavy processes. what do you do? could do nothing (would likely bounce around between expired requests) (seems bad.) could set all the deadline-expired requests into another C-SCAN-managed queue. (seems good... though you might just overpopulate the second C-SCAN list) could increase the timeout/deadline. (might not be allowed.) could start increasing the timeout for processes with many concurrent requests (only). (probably really not done). how many requests can a thread have? you can request all of the disk sectors associated with a file system block at once. (e.g., 512 bytes * 2?) you can read-ahead: ask for the whole small file at once assuming it will be read in its entirety. you can have a bunch of pending writes (dirty buffers in the cache). you could use non-blocking i/o. read() is associated with a file descriptor. file descriptor has a "readiness" associated with it. can check that state with select() or by polling (calling read() again). "ls" could read all the blocks associated with the inodes of the directory. (might not actually do it.) if you imagine, though, that each process would most likely only have one pending request: 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?). augments another scheduling scheme, in the Anticipatory paper using the Stride scheduler, where each process gets a virtual clock of requests and the OS tries to keep each process advancing reasonably fairly. limit the number of waits before reading operations? (likely: have to prevent mischief/abuse) 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. those processes with a low or high rate of requests may not be obvious from the length of the queue. 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?) could prioritize "interactive"-like requests by penalizing processes with sustained high disk activity. (suspect not done) File system material cleanup: Superblock a record placed at known locations on the disk to maintain global data about the file system. Don't have - indication from the OS about how big the disk is that we then apply some formulas to to determine file system properties. All those properties are recorded on the disk. When you mount() a file system, you can check that the file system is the one you think it is. (won't treat a fat-formatted device as an ext3-formatted device, or an ext3 device as an ext2 device). If the superblock is corrupted: (a) aren't you glad you had a backup plan. (b) other blocks are probably corrupted too. (c) replicas! the superblock gets stored in several places on the disk. Superblock used in pfat to store where the FAT is and where the root directory is. April 18 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. digression - generational garbage collection imagine you do mark and sweep. imagine that you promote anything that was marked into another space representing objects that appear persistent. (where the old objects go) may only clear out this old space occasionally. want to create segments that are either full of long-lived persistent data or full of short-lived stuff ready to be reclaimed. (relationship between short-lived file-system objects and short-lived memory allocations) lfs: 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. checkpoint - requires a complete version of the inode map. from this checkpoint segment, can advance through the rest of the segments. know which segment has a checkpoint by reading the superblock. 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. April 25 - Midterm Review - not quite graded yet. (code takes a while to grade) - Q3 discard. P5 - distributed images may differ somewhat from equally reasonable designs. they are mostly to express what I had in mind if you have questions about blocks vs. sectors, indexes (e.g., what to do about inode zero). - inode zero invalid (do not use) but present. wastes all of 32 bytes. RAID premise: disks are cheap (inexpensive), but unreliable. - exploit the cheapness to solve the unreliability problem. disks are kinda slow, if more than one copy, can read from any copy... double the read throughput! halve the latency(?) "hardware RAID" involving a specific controller device that provides the single-disk interface to the OS, then does all the work talking to the drives. Likely to also have battery backed ram to buffer writes. Likely limited in the number of SCSI / SATA / SAS ports. "software RAID" that requires the OS to do everything, has no hardware. no proprietary hardware controller to replace when it fails. Likely less limited in the number of concurrent drives. RAID Levels 0 - provides 0 redundancy "Stripe" potentially double the read throughput potentially double the write throughput potentially drop the access latency a bit (if heads are independent) 1 - "mirror": replicate all. write is slower or the same - must write to both. potential improvement on the read throughput - don't have to decide on a stripe size at format time. "1+0" 2 - error correcting code. 3 - bit-interleaved parity - 4 - block parity 5 - shuffle the blocks to avoid write bottleneck damage: disks have to be the same. but given environment, they are likely to fail not-independently. generally need a human to notice the broken disk and replace it rebuild process can stress a disk. April 30 P5b will not perform the write tests - should slightly speed the submit server. be careful of recursion - stack overflow in the kernel is not nice. kernel stack is small! one page! you can maybe get away with a little overflow because the tiny little kthread structure is allocated using Alloc_Page just before its stack gets allocated, so they're likely to be right next to each other, meaning that it will take ~ 7K to overflow, and then, you'll overwrite the kthread! oh no! use the buffer cache! you give it a size, it reads the sequential blocks. so you don't have to! beware of failed Malloc() - check the return value. seek : if you read the gap in a sparse file, it should give zeroes. (pretty much impossible to do otherwise, since you'd have to track which specific bytes were valid/written in order to provide an error for reading uninitialized/unwritten bytes) seek past end of file then read should return as if end of file (EOF). (0). don't try to load everything at once. not what anything will/should do. no locks required in your implementation... reality: it would be very bad if two processes want to create the same file at the same time. or claim the same free block or free inode at the same time. You could solve this with mutexes (one for file creation, one for free block data structure,... presumably in the "instance" structure) without too much pain, but... I can't test it... I can hardly even test semaphores. You probably can't test it easily either... and I can't rely on useful bits from prior projects. So, don't worry about locking shared data structures in the file system implementation. You can lock if you want, that would be cool. spanning blocks: no one ever knows that blocks are spanned. why? because there's a (helper) function that reads n bytes at position p. to read a dirent, use the helper function to read 6 bytes, then again to read entry_length (- 2?) RAID cleanup: 3 - each bit on a different disk, with parity bit. theoretical, mostly. 4 - each block on a different disk, with parity block. -> difference? sequential bits on different disks in 3, must read all disks at once to get sequential data. could just read sequential data off one in 3. 6 - instead of one parity block, cycled around, two error correcting blocks, cycled around (all disks store some correcting blocks, it's not a dedicated parity disk as in 4.) NFS network file system Idea: use remote procedure call to put the file system (and disks) on one server, so that clients can talk to the central server across a network. There are a few ways to communicate to a server or distribute a computation: can pass messages as microkernels do between processes, can make up a protocol like HTTP that has its own text, OR can re-use an RPC scheme invented for general use. RPC library takes care of marshalling arguments (serializing in java) blocking the caller, retransmitting, avoiding duplication with sequence numbers (maybe). So the RPC library provides the ability for the caller to just call a "read" or "write" function, block in that function, and not have to redesign the way the file system works. Could imagine an alternative design where the file server just provided blocks rather than files. ... where the layer of RPC was lower than file reads and writes, just using block reads and writes. ... and this would almost certainly be a mess for concurrent updates. Why is network file service hard? High latency? experiment: 0.5 ms good case. 2ms over wireless. 10ms to a busy machine. if you read from the server's cache, that would be faster over the network than reading from your disk. what's the likelihood of reading from cache? if the server supports many users, cache is shared. but maybe the cache is also bigger because of it. maybe everyone reads the same data? or maybe no one does? may also be able to additionally cache on the client, which help restore some performance if you infrequently access the same stuff. (that the server would drop from its cache) the more RPC functions you have to execute in sequence, the longer it's going to take. if across a wide area network (100ms to europe and back), then that could take a noticeably long time. network links are relatively slow in throughput. SATA sports 3-6Gb / s. practical network links top out at 10 Gb/s, likely only 1 Gb/s, residential likely only 10 Mb/s max (so you wouldn't do that) potentially no contention. - can you get the 10Gb/s easy answer is no - 28 bytes of 1500 bytes on IP headers, 14 on ethernet - lose 3% header tax harder answer is also no - processor, bus can have trouble keeping up. ever harder answer - switches rated for 10Gb links don't always keep 10 Gb pushing through on all ports all the time. - there are special purpose ($$$) high-performance network links that are more likely to reach their rated capacity. - I'm not sure how likely you are to reach the 6Gb SATA max. - turns out not very. - can read from the disk buffer (64MB-ish) at speed. - reading from the disk platter at 145 MB/s = 1.15 Gb/s (if sequential... and your file system kept the file sequentially) vs SSD: - can break 3Gb easy; 6 maybe not. 500 MB / s. == 4 Gb / s - can get PCI-e SSD's for a bit more. - would probably never be beaten by going across the network for files in terms of latency.... capacity, however, totally different. - each little SATA link can run at the same time (though aggregate bitrate unclear). Data corruption? Internet comprises cheap network links. makes few assumptions. Allow four bad things to happen to your data: packets can be dropped (loss) packets can be corrupted (bit errors) packets can be delayed (reordered) packets can be duplicated (e.g., some link was trying too hard to send your packet) Options for corruption: error detection + retransmission. error correcting codes. - gets larger as you handle more errors... not terribly likely to suffer only a few bit errors. Synchronization between two users accessing / writing the same file? CIFS / SMB - has functions for keeping cached data at the client. when another station accesses the same file for writing, have to disable that cache / confiscate a lock / get the unwritten data back up to the server so that the server can process all updates. NFS preserves the unix-like semantics of a free-for-all. Maintain causal or similar order? (don't want writes to seem like they disappear) Easy since the server is the single arbiter of ordering. Would want requests from individual clients to be sequenced in the order they're issued. Server could be (or go) offline. Reboot: lose all RAM: forget all in-memory state. (don't forget stuff on disk) we're going to lose / forget all pending requests we would lose all state. if intentional reboot, you could satisfy the queue of pending requests before termination... my context is the crash. (if you can handle crash, intentional reboot is easy) no open files on the server. no file positions on the server. assume the server is unreliable. re-issue the write if you get no ack. re-issue the read if you get no data. don't expect the server to remember anything (except what is written to disk) server should not ack the write until it's actually on disk. nfsstat shows the calls. server remembers nothing Privacy server sees all (can't do anything about that... except store encrypted files, but that's not fun) you're sending over the network. often visible to lots of people. Security. Are there users? yes (there's an "access" function) Which hosts get to use NFS? list of approved IP addresses. How does it know about users? nfs client machines have the same user ids. (passwd file) your local uid has to match the one on the server. you can be extra careful about uid 0 (root / super user) could do ssh-based file system -- sshfs, which uses FUSE, which is a scheme for implementing a file system at user level. TODO: journaling May 7 P5c - deletion from a directory - the easy way is not space efficient, but works. (no need to compact... unless you think that's fun.) (apparently, the easy way is also the official way.) (could imagine a garbage collector. e2fsck will compact if given an option... or if it feels like it (man 8 e2fsck)) neil believes endPos is misguided. File system checking : order of writes partially dictated by disk scheduling (unless the file system is really careful giving blocks to write in a particular order, waiting for each to complete) don't necessarily know whether the free blocks bitmap is right - claims occupied blocks when they're deleted/unused or claims unoccupied blocks when used. blocks claimed by different files! (maybe a deleted file didn't get truly deleted before a new file claimed the block and wrote its inode.) - maybe the checker / fixer clones the block and undoes the delete (not knowing which file was deleted) Journaling writing all metadata updates in order to a in-sequence log (journal) rather than scatter these updates, they become persistent when written to the log. (and attain an order). if crash and reboot -> replay the log. replaying the log might involve a write to an inode or maybe a dirent. write-back to the correct location of the inode or indirect block in order to reclaim space in the log or if replaying the log on recovery. you expect to have to write everything twice. -> typical journaling does not include the data... only the metadata. -> you get the benefit to consistency after crash, but at at least some performance cost. if there's a crash while writing to the log, it's as if the update didn't happen at all. - if the application really wanted to know that the write finished, it only has to wait for the journal/log. are there patterns in the kernel for bounding the amount of inconsistency tolerated or the age of a dirty buffer? clean (write out) the dirty buffers associated with the oldest entries in the log? (you might get this without trying) Copy-on-Write file systems ZFS is an example Write a copy of the block. Write a copy of the indirect block. Write a copy of the inode. Write a copy of the inode file indirect block. Write a copy of the inode file inode to a designated place for tne next root inode. cost: potentially lots of writes just to update a little bit. note that appending to a file requires update to the inode. huge benefit: no inconsistency! no vulnerability to the block the disk was writing. Approximates the functionality of a "flash translation layer" User-level file systems Also: User-level network services. Goals of kernel memory allocation - contiguous, large allocation. (devices might demand that) correctness - don't allocate the same space to two requesters. maybe alignment - a better allocator might not store the length of the allocation in a way that munges the start pointer. we'll want to deal with out-of-memory nicely. Buddy allocator recursively divide memory in two. take each requested number of bytes, round it up to a power of two, look in the free list for that size: - if there's a block free, take it. - if there's not, split a larger block. when you free, - see if your "buddy" is also free, if so, merge. May 9 Exam Saturday 8am, normal room. 5c due friday. SLAB allocator take the irregularly sized objects and allocate an array of them inside a page. - homogeneous objects in one page. - might have pre-initialized objects in this page = could re-use "free" ones. closest thing in GeekOS is the page list. - who knows sizeof(struct Page) (but probably not a power of 2) - allocated as a big array to ensure compact storage. SLAB has a little header saying which or how many objects are free - so that it can have three states: full empty partial - and the allocator can reclaim empty slabs. One nice feature: - memory overrun more likely to confine damage to objects of the same type. (might be good). - access of free()d memory more likely to hit the same object type. (well, might be bad). Linux uses a "SLUB" allocator: * pages of objects of the same size, not necessarily of the same type. (can't be pre=initialized) * moves counters into Linux's equivalent of struct Page. (making them less likely to be damaged, and consume less space) Kernel allocation: Wait or fail? Cannot wait: interrupt handlers. can't wait for slabs to be reclaimed or dirty pages to be sent to disk. "GFP_ATOMIC" Can wait: probably most everything else. especially if waiting for a device otherwise. "GFP_KERNEL" Passwords Tenex hack for (i = 0; i <= strlen(directoryPassword); i++) { if (directoryPassword[i] != passwordArgument[i]) { /* the password is wrong. */ sleep (3); return EACCES; } } return 0; passwordArgument is UserToKernel(state->ecx) if user code passes very long password without null termination, we'll still terminate. garbage just won't match. bad guy: calls p = malloc(8192); find q > p where q & 0xfff == 0xfff. q[0] = 'a' call r = malloc(whatever I can get away with). touch every page in r. touch every page in r again. q[0] = 'a' start = gettimeofday() check_password("root", q) end = gettimeofday()