- kernel responsibilities - the hardware has decided that certain things are only done by the OS ~ and it makes so the OS can arrange for ONLY its code to run in kernel mode (and well call that code "the kernel") - typically reserved for the OS: ~ setting how exceptions are handled ~ handling exceptions ~ setting page table base pointer ~ communicating with devices ~ in the Unix design: informatoin about proceses, I/O, etc. is all managed by the kernel - context switch versus exception ~ thread context switch: switching from one thread to another ~ thread ~~ "virtual processor" ~ has its own registers and program counter ~ exception: run OS code to handle some "event" ~ kind of like a function call to handle the eventS ~ HW: jumps to the OS code (location configured at boot with the processor) and switches to kernel ~ the OS code can decide to do a context switch if it wants ~ or it can just handle the event and go back to what happened before exception - context v mode switches ~ thread/process context switch: we're changing what thread (which set of registers) and/or what process (memory, open files, etc.) are active ~ mode switch usually means kernel versus user mode ~ changing whether we're in kernel or user mode ~ often this involves saving/restoring registers, but we're usually saving registers when we enter kernel mode (like we save registers when entering function) and restoring registers when we exit kernel (like we restore regsiters when leaving a function) VERUS thread context switch where we typically save the old register AND restore the new ones (not like a function --- we have specific registers to switch to) ~ mode switch happens on most exceptions (b/c the event that triggers the exception usually occurs when a program is in user mode, but the exception is always handled in kernel mode) (exception could be syscall, page fault, I/O, ....) - process versus thread control block ~ thread ~~ "virtual processor" ~ has its own registers and program counter ~ its stack pointer register points to a memory location that's process's address space, ~ typically a stack is allocated for each thread, but every thread in the process can access that stack if it has a pointer to it ~ thread is always started with stack pointer pointing to correct stack so it won't access other thread stacks normally ~ whatever starts the thread will choose different address ranges for each stack ~ often with some invalid pages around it so stack overflows crash ~ but one thread can pass a pointer to another ~ process ~~ "virtual machine" ~~ one or more threads (virtual processors) + files (I/O devices) + memory (address space) ~ address space: ~ page table ~ other information about memory layout (e.g. xv6: "end of heap"; Linux: the list of mmaps) ~ open files, current working directory ~ one or more thread control blocks - when does xv6 decide to schedule something ~ supplied scheduler in xv6 is run: ~ when a thread becomes non-runnable (e.g. waiting in read() or sleep() or similar system calls) ~ when a timer interrupt goes off ~ when the yield() system call runs it ~ and when the scheduler runs, xv6's default scheduler just chooses the next thing in the process table (going back to the beginning if there's nothing left) "next thing" --> next _runnable_ thing - pipes and dup2: week 4 quiz Q2 ~ question: run programA --> (convert to upper case) --> programB code at the bottom reads from BLANK FOUR + converts to upper case + writes to BLANK FIVE BLAKN FOUR ~~ program A and BLANK FIVE ~~ program B programA's output goes to pipe_fds1[1] [write end of the pipe created by pipe(pipe_fds1)] (because the dup2 changes STDOUT) dup2(x, y) --> makes the file descriptor identified by 'y' go to where the file descriptor identified by 'x' currently goes then Q2 asks, what do read from to get what we want to convert to upper csae pipe_fds1[0] [read end of that pipe created by pipe(pipe_fds1)] - semaphores versus mutexes ~ mutexes --> type of lock mutual exclusion with two operations Lock() --> wait for the lock to be available, then mark it as locked not letting anyone else have it Unlock() -> mark the lock as available [requires that the current thread locked it previously] ~ mutexes unlike some other types of locks we discussed generally wait without using tons of processor time (--> somehow integrated with the scheduler) ~ common implementation technique is that mutexes will use spinlocks (that use a lot of processor time) but only to see if they need to wait, but actual waiting will involvie calling the scheduler ~ implies that unlock operation needs to work the scheduler to make something runnable that was previously not runnnable ~ usually once threads decide to wait, there's some queue of waiting threads that unlock can take threads from ~ [counting] semaphores are more general mutexes: semaphore stores a non-negative number: Down() operation --> wait for the number to be positive, then decrement it Up() operation -> increment the number can implement mutexes with semaphores: sem = Semaphore(1) Lock() {sem->Down()} Unlock() {sem->Up()} we can also do other things with semaphores, for example, we can wait for osmething to happen: sem = Semaphore(0) WaitForThing() {sem->Down()} MarkThingHappened() {sem->Up()} (if we were using mutexes and also needed the wait for something to happen operatoin, usually, we'd use condition variables to do this) - fork efficiency ~ naive implementation of fork: copy all the program's memory ~ better implementation: "copy on write" avoid copying the program's memory as long as possible: instead: mark both [pretend] "copies" as read-only, but don't actually make a copy then, when something tries to access one of the copies, actually copy at least enough for that access to work [at least a page with page tables] ~ with fork: often we will end up never copying a lot of things that we would otherwise copy (even better than just deferring the copy) - Quiz 7 Q4 -- counting page tables VPNs 0, 1, 2, 3, 4, 5, 0x7FFE, 0x7FFF Q: what does our two-level page table structure look like for this? 1st-level table: 2nd-level table (for vpn 0-0x3ff) [index 0: vpn 0-0x3ff]------------------------------------------> [index 0: vpn 0] ^^^^^^^ --- all vpns with the first ten bits 0 [index 1: vpn 1] [index 1: vpn 0x400-0x7ff] <-- marked not present ... ^^^^^^^^^^^ --- all vpns with the first ten bits 1 ... [index ???: vpn 0x7400-0x7FFF]---------------------------------> 2nd-level table (for vpn0x7400-0x7fff) ... ... [index: 0x3FE: vpn 0x7FFE] [index: 0x3FF: vpn 0x7FFF] first-level page table + two second-level page tables don't need other second-level page tables -- we just mark that whole range of VPNs not present in the first level 3 tables and each table on xv6 is one page --> 3 pages - device controllers -- memory-mapped I/O + buffers ~ big idea with device controllers: processors know how to talk to memory, memory is already not on the same chip let's just use that functionality to also talk to other things ~ hardware implements the memory interface, but makes it do things relevant to a device for example: "keyboard controller" exposes memory locations, but rather than storing data, these memory locations let the processor access the keyboard ~ to use this: operating system accesses particular memory locations (needs to know what the device controller expects may need to disable caching by the processor --- b/c these locations don't store data) ~~~~ ~ device controllers often need to store data that either: ~ hasn't been processed by the OS yet OR (e.g. keypresses I've made that hasn't received yet) ~ hasn't been processed by the device yet (e.g. stuff that needs to go out on the network but hasn't yet) ~ sometimes, the device controllers will have some built-in storage for this buffer on the device controller ~ sometimes, the device controller will ask the OS to point to what storage will be used for this "direct memory access" ~~~~ ~ OS often needs to store data that either: ~ has been written by a program but not sent to the device controller yet ~ has been received from the device controller but not received by a program yet ~ it will usually have its own "kernel bufferS" for this - week 14 quiz Q2 -- failure ~ scenario: SetEnrollment(..., 150) call and previous value of enrollment is 140 this call appears to fail b/c the network breaks: ~ scenario 1: we sent the call out, and it didn't get anywhere ---> value is still 140 ~ scenario 2: we sent the call out, it got to the machine, but the acknowledgment didn't get anywhere --> value is 150 ~ scenario 3: we sent the call out, but the network took an exceptionally long time to get it there, and we gave up --> value was 140 but then it actually got there (even though we had guessed wouldn't take this long) --> value become 150 - week 14 quiz Q4 -- transactions ~ options say "can complete transactions" NOT "can complete any transaction" they can't complete every possible transaction, but they can definitely complete transactoins involving the same machines but different customers/items - set-user-ID ~ normally: execv() a program --> the process's user ID stays the same this means that, e.g., if a run `ls`, it can access the same files I can normally access ~ but we can mark a program as set-user-ID execv() a set-user program --> the process's user ID becomes the user ID of the owner this means that it can access whatever the owner's user ID represents ~ common example: set-user ID program owned by user ID 0 "owner" ~~ special user ID stored with the file ~ in POSIX: the user ID that has permission to change the access cotnrol list ~ default owner of a file is the user ID that creates it ~ that program can access anything since user ID 0 skips most acces control checks ~ system administrator who sets up this program --> chooses carefully what programs they set this way to make sure its only programs that allow things they want ~ password checking ~ Unix design: the kernel knows nothing about passwords or usernames ~ instead, programs the system administrator sets up do this wrok ~ they tell the kernel what user ID to run things as based on their database of usernames/passwords ~ capabilities ~ kernel or somethig trusted uses them to lookup "what resources does this capability refer to" we can't let the attacker control this or they can make up new tokens for anything ~ main advantage of capabilities is probably a cleaner interface