- virtual memory on the exam? - everything in lecture up to and including last week - everything we did in assignment - exam format - mostly short answer or multiple choice - some one sentence answers - maybe a code question that is not fill-in-the-blank (depending on whether we feel there's time) - [virtual memory] the last quiz - Q4: - a system uses COW to implement fork - a process forks, then the child modifies addresses 0x7FFFEFF8 through 0x7FFFF016 4K pages, last 12 bits are the page offset = 3 hexadecimal "nibbles" virtual pages numbers 0x7FFFE throgh 0x7FFFF --> 2 virtual page numbers 0x7FFFEFF8 ^^^--- page offset ^^^^^------ virtual page number on it stack - the system has 4K pages - how many new pages are allocated, besides page table pages and ones used by the kernel - 2 pages to copy: for 0x7FFFE and for 0x7FFFF - Q1: - how much space do we need to have a page table that stores valid mappings for addreses 0x8000 0000 through 0x8000 0000 + 224MB (assuming x86-32's page table layout) 224MB / 4KB per page = 56K pages 1K pages per second-level page table (2^10 pages because 10 bits are used to find where in the second level table to go) 56 second-level tables (56 and not 57 because 0x8000 0000 corresponds to the beginning of a second-level table, beacuse the last 10 bits of its VPN are 0) 1 first-level table (which points to the second-level table) [---- first level 10 bits ---][--- second level 10 bits ----] 2^10 possible first 10 bits and 2^10 entries in the first-level table one is always enough ~ 0x8000 1000 through ... 55 full second-level tables (1K entries each) + 1 second-level table with ALL BUT THE FIRST ENTRY usd + 1 second-level table with ONLY THE FIRST ENTRY USD - Q2: sbrk() only tracks what part of heap has pages, not how it's used - comparing scheduling methods ~ preemptive versus non-preemptive preemption: stop what's happening when we want to schedule something else simplest version: round-robin no preemption: just keep going until the thread givess up the CPU itself simplest version: first-come, first-served ~ optimizing for: throughput: first-come first-served minimum overhead (fewest context switches, simplest scheduling dec.) mean response time (keypress happens -- do something) theoretically: SJF (no preempt.), SRTF (preempt.) run the thing that will finish first, first pratically: multi-level feedback queues (heuristic) figure out the CPU burst time based on history` importance (as told by user) priority scheduling: "users/sysadmins say what order" run the most important one first always proportional share: "users/sysadmin say relative importance" run in specified ratio (lottery, ~CFS) fairness: round-robin (no ordering, just evenly split) but doesn't give you credit for coming back from not using the CPU afte while CFS some idea of fairness, but with proportional share if you wanted it, and tries to give you credit if you haven't the CPU for a while real-time guarantees earliest deadline first not the same as response time - Completely Fair Scheduler - determinstic proportional share - instead of tickets, track "CPU time units used" typically run process with the least time units used (weighted by relative importance) - limit how far ahead a process gets in CPU time units used by not using the CPU for a while - cache coherency - every CPU has cache - caches are connected via a shared bus ("shared wire") - CPUs track information about everything they have cached - Modified --- they have the only copy and it may be different from memory = license to change a value = can keep changing a value without sending messages (already done the work to make sure no one else has it) - Shared --- others may hvae copies, and its the same as memory - key problem: want the Modified to really mean ONLY YOU have it - cause everyone else to evict their copy when we want to modify something (Send a message "please invalidate this addres, I'm about to write to it") - make sure anyone reading a Modified value sees our update before they finish the read, and when they do that we don't keep the value marked as Modiifed - spinlock implementatoin - basic idea: a memory locatoin represents the lock some values means locked, some do not lock: use atomic operation to try to set from unlocked to locked if atomic operation says "it was already locked", then *retry* must be read-modify-write because you need to read the old value lots of atomic RMW operations that work: - test and set - atomic exchange (typical x86 choice) atomic-exchange(REGISTER, MEMORY-ADDR): atomically: (no one can write the memory locatoin while this happening) temp <- MEMORY[MEMORY-ADDR] MEMORY[MEMORY-ADDR] <- REGISTER REGISTER <- temp - compare and swap unlock: set from locked to unlocked - mutex versus spinlock - spinlock: RETRY -- keep running instructions for this thread on the CPU until it works (even though those instructoins won't do anything useful for a while) - mutex: we tell the OS "hey, run something else, I can't go" the unlock operatoin tells the OS "hey, this thread can go" typical implementatoin uses spinlocks or similar to handle information about who needs to be woken up on unlock - semaphores versus monitors (= mutexes and condition variables) - equally powerful: can implement either with the other - semaphores: two important patterns: - wait for event: start sem at 0, wiating thread calls down, event-detecting calls up - don't need waiting thread to start before event-detecting thread - mutex lock: start sem at 1, lock is down, unlock is up - monitors: - wait for event: done with condition variables signal/broadcast - threads that are CURRENTLY waiting generally have a loop checking shared data to see if we can go - mutex lock: a mutex - implementing a monitor with semaphores - mutex lock pattern above (sem at 1, lock = down, unlock = up) - list of wait for event pattern for condition variables - lists protected by a mutex-lock-style semaphore - "event detected" = signal/broadcast ~~~~ - versus quizzes ~ are typical of questions I write, but many quiz quesions assume you will look at slides - sample questions ~ besides quiz questions, some practice questions are in the exercises in the textbooks (Anderson-Dahlin or Arpaci-Dusseau) - rubric ~ I intend to deal with this when I map raw weighted score to letter grades - what's the implementatoin of a CV look like ~ queue of waiting threads (like for a mutex) ~ we need to do some sort of mutual exclusion when changing this queue (like for a mutex) ?spinlock? -- depends on OS system call for going to sleep until woken up ~ signal/broadcast look at queue and tell OS to wake up thread - deadlocks ~ definition ~ one thread A is holding a resource while it is waiting acquire a resource another thread B has but thread B is waiting for a resource that thread C has thread C " " " thread D has .... thread ? " " " threda A has - hold and wait - circular dependency - draw a "resource acquistion graph" --> cycle (edges from resource -> thread holding, thread waiting -> resource) - limited resources - no preemption (can't "steal" resources) - event loops - instead of multiple threads to do I/O to multiple things (e..g multiple network connections) use one thread, have a "GetNextEvent" call that returns which thing has input available or can accept output - very different code organization --- need to track some table of connection --> information about what's going on (what command is active?) - pro: no synchronization problems - con: possibly harder/less natural to program (e.g. need to avoid stalling on any operation) can't use multiple cores - atomic ops, using to do something - test and set TEST-AND-SET(memory-addr): atomically: old-value = MEMORY[memory-address] MEMORY[memory-address] = 1; return old-value implement spinlock if 1 == LOCKED - general pattern for atomic operations: use atomic read-modify-write operatoin to try to do something, detect from read value whether it worked right (e.g. did we acquire the lock or was it already locked? did COMPARE-AND-SWAP update the value to increment it or did someone else change it first? did we add to the linked list where we thought or did someone else change the next pointer first?) typically a loop that potentially loops forever if other threads keep trying to change the value, too