Exam Review excited Overview Part 1 about 40 short text answers all sorts of topics Part 2 about 60 small programs Understand what you did in the projects and why Understand what happened in lecture User program does I O syscall io op loc addr op read or write loc location on device addr memory location ToyOS I O no DMA Goal let user programs deal with I O devices Program waiting for I O should not waste CPU time General idea Is the I O device available Wakeup No Yes Put user program on I O wait queue Lock device Serve request Unlock device wake up from queue Return ToyOS I O no DMA User program does I O syscall io op loc addr op read or write loc location on device addr memory location Is the I O device available Wakeup No Yes Put user program on I O wait queue Lock device Serve request Unlock device wake up from queue Return User program does I O syscall io op loc addr Is the I O device available is the I O queue empty No Yes ToyOS I O with DMA Traditional I O CPU completely occupied when doing I O DMA direct memory access I O device drives memory bus Issues interrupt when it s done General idea CPU can do other things while I O device reads writes memory Wait for it to become available add to I O queue Tell DMA device to do it s thing Suspend user program add to I O queue I O Interrupt Tell DMA device to start next requested operation for the next program on I O queue Now I O call can return ToyOS I O with DMA User program does I O syscall io op loc addr Is the I O device available is the I O queue empty No Yes Wait for it to become available add to I O queue Tell DMA device to do it s thing Suspend user program add to I O queue I O Interrupt Tell DMA device to start next requested operation for the next program on I O queue Now I O call can return ToyOS async I O Synchronous I O user program stuck waiting for I O General idea I O request returns immediately User program continues I O operation takes place in the executing background User Thread Kernel I O server thread User program does I O syscall io op loc addr Is there a pending I O request I O request added to I O queue return I O interrupt No Wakeup Wait for an I O request Yes Issue I O request to device Wait for an I O interrupt Remove completed request from I O queue ToyOS async I O User Thread Kernel I O server thread User program does I O syscall io op loc addr Is there a pending I O request I O request added to I O queue return I O interrupt No Wakeup Wait for an I O request Yes Issue I O request to device Wait for an I O interrupt Remove completed request from I O queue Scheduling x86 Memory Management background 8086 CPU real mode Running software gets direct access to everything 286 CPU protected mode Each process gets its own address space Privilege levels introduced Protection Designate memory segments for specific purposes i e writing to the code segment might be bad x86 Memory Management cont Memory separated into segments which have rules segment info must be stored somewhere GDT global descriptor table LDT local descriptor table Don t worry about paging for now unless it was covered during class x86 Memory Management cont Segment descriptors define Where the segment starts How big the segment is What s allowed on that segment Memory accesses pass through either the global descriptor table GDT or optionally a local descriptor table LDT x86 Memory Management GeekOS userseg c Create User Context Allocate an LDT descriptor for the user context context ldtDescriptor Allocate Segment Descriptor if context ldtDescriptor 0 goto fail if userDebug Print Allocated descriptor d for LDT n Get Descriptor Index context ldtDescriptor Init LDT Descriptor context ldtDescriptor context ldt NUM USER LDT ENTRIES index Get Descriptor Index context ldtDescriptor context ldtSelector Selector KERNEL PRIVILEGE true index Initialize code and data segments within the LDT Init Code Segment Descriptor context ldt 0 ulong t context memory size PAGE SIZE USER PRIVILEGE Init Data Segment Descriptor context ldt 1 ulong t context memory size PAGE SIZE USER PRIVILEGE context csSelector Selector USER PRIVILEGE false 0 context dsSelector Selector USER PRIVILEGE false 1 Allocate two LDT entries NUM USER LDT ENTRIES 2 Define characteristics of segments There s a code segment and a data segment Look at segment c for more info x86 stack stuff Remember project 2 Know how the stack works know it really well Synchronization test set instruction Set a variable to true return the old value rc x x true return rc All this is atomic Using wait queues Higher level constructs Synchronization test set instruction Let s call that instruction tset for simplicity Have a shared variable lock acquired lock acquired false To acquire the lock while tset lock acquired true we now have the lock To release the lock lock acquired false Weak lock Thread waiting on lock can get starved Synchronization with wait queue General idea ensure some fairness by having threads wait in line for a lock Also don t want threads to waste CPU time while waiting for lock Acquire lock Lock the wait queue associated with the lock spin lock to do this If the lock is free lock acquired false Take it lock acquired true Release lock wait queue s lock Else lock not free Move thread to lock wait queue Release lock wait queue s lock Release lock Wake up the next waiting thread No waiting threads set lock acquired to false Synchronization higher level constructs Await B S S is a section of code B is a condition S gets atomically executed if B holds Goal express program requirements at higher level and then translate from awaits to real synchronization constructs Example bounded buffer
View Full Document
Unlocking...