15 410 Maybe the world has enough sokoban implementations The Thread Sep 15 2004 Dave Eckhardt Bruce Maggs 1 L07 Thread 15 410 F 04 Synchronization Project 1 Should have much of console working Should have some progress at least design for kbd timer Write good code Console driver will be used and extended in P3 2 15 410 F 04 Book Report Goals Some of you are going to grad school Some of you are wondering about grad school Some of you are in grad school You should be able to read a Ph D dissertation More generally Looking at something in depth is different Not like a textbook 3 15 410 F 04 Book Report Goals There s more than one way to do it But you don t have time to try all the ways in 410 Reading about other ways is good maybe fun Habituation Long term career development requires study Writing skills a little Summarizing a book in a page is tough 4 15 410 F 04 Book Report Read the handout Browse the already approved list Pick something soon Don t make me stop the car Read a bit before you sleep at night or before you sleep in the morning and or Thanksgiving break Recommended by previous OS students 5 15 410 F 04 Road Map Thread lecture Synchronization lectures Probably three Yield lecture This is important When you leave here you will use threads Understanding threads will help you understand the kernel Please make sure you understand threads We ll try to help by assigning you P2 6 15 410 F 04 Outline Textbook chapters Already Chapters 1 through 4 Today Chapter 5 roughly Soon Chapters 7 8 Transactions 7 9 will be deferred 7 15 410 F 04 Outline Thread schedulable registers that s all there is Why threads Thread flavors ratios Against cancellation Race conditions 1 simple 1 ouch Make sure you really understand this 8 15 410 F 04 Single threaded Process Stack stdin Registers Heap Data Code 9 stdout timer 15 410 F 04 Multi threaded Process Stack Stack Stack Heap Data Code 10 Registers Registers Registers stdin stdout timer 15 410 F 04 What does that mean Three stacks Three sets of local variables Three register sets Three stack pointers Three eax s etc Three schedulable RAM mutators heartfelt but partial apologies to the ML crowd Three potential bad interactions 11 15 410 F 04 Why threads Shared access to data structures Responsiveness Speedup on multiprocessors 12 15 410 F 04 Shared access to data structures Database server for multiple bank branches Verify multiple rules are followed Account balance Daily withdrawal limit Multi account operations transfer Many accesses each modifies tiny fraction of database Server for a multi player game Many players Access update shared world state Scan multiple objects Update one or two objects 13 15 410 F 04 Shared access to data structures Process per player Processes share objects only via system calls Hard to make game objects operating system objects Process per game object Scan multiple objects update one Lots of message passing between processes Lots of memory wasted for lots of processes Slow 14 15 410 F 04 Shared access to data structures Thread per player Game objects inside single memory address space Each thread can access update game objects Shared access to OS objects files Thread switch is cheap Store N registers Load N registers 15 15 410 F 04 Responsiveness Cancel button vs decompressing large JPEG Handle mouse click during 10 second process Map x y to cancel button area Verify that button release happens in button area of screen without JPEG decompressor understanding clicks 16 15 410 F 04 Multiprocessor speedup More CPUs can t help a single threaded process PhotoShop color dither operation Divide image into regions One dither thread per CPU Can sometimes get linear speedup 17 15 410 F 04 Kinds of threads User space N 1 Kernel threads 1 1 Many to many M N 18 15 410 F 04 User space threads N 1 Internal threading Thread library adds threads to a process Thread switch just swaps registers Small piece of asm code Maybe called yield Stack Stack Stack Registers Heap Data Code 19 15 410 F 04 User space threads N 1 No change to operating system System call probably blocks all threads The process makes a system call Kernel blocks the process special non blocking system calls can help Cooperative scheduling awkward insufficient Must manually insert many calls to yield Cannot go faster on multiprocessor machines 20 15 410 F 04 Pure kernel threads 1 1 OS supported threading OS knows thread process ownership Memory regions shared reference counted Stack Stack Stack Registers Registers Registers Heap Data Code 21 15 410 F 04 Pure kernel threads 1 1 Every thread is sacred Kernel managed register set Kernel stack Real timer triggered scheduling Features Program runs faster on multiprocessor CPU hog threads don t get all the CPU time User space libraries must be rewritten Requires more kernel memory 1 PCB N TCB s 1 k stack N k stacks 22 15 410 F 04 Many to many M N Middle ground OS provides kernel threads M user threads share N kernel threads Stack Stack Stack Registers Registers Heap Data Code 23 15 410 F 04 Many to many M N Sharing patterns Dedicated User thread 12 owns kernel thread 1 Shared 1 kernel thread per hardware CPU Each kernel thread executes next runnable user thread Many variations see text Features Great when scheduling works as you expected 24 15 410 F 04 Against Thread Cancellation Thread cancellation We don t want the result of that computation Cancel button Asynchronous immediate cancellation Stop execution now Free stack registers Poof Hard to garbage collect resources open files Invalidates data structure consistency 25 15 410 F 04 Against Thread Cancellation Deferred pretty please cancellation Write down thread 314 please go away Threads must check for cancellation Or define safe cancellation points Any time I call close it s ok to zap me The only safe way IMHO 26 15 410 F 04 Race conditions What you think ticket next ticket 0 1 What really happens in general ticket temp next ticket 0 temp 1 but not visible next ticket temp 1 is visible 27 15 410 F 04 Murphy s Law of threading The world may arbitrarily interleave execution Multiprocessor N threads executing instructions at the same time Of course effects are interleaved Uniprocessor Only one thread running at a time But N threads runnable timer counting down toward zero The world will choose the most painful interleaving Once chance in a million happens every minute 28 15 410 F 04 Race Condition Your Hope T0 tkt tmp n tkt tmp n tkt tmp T1 0 1 1 tkt tmp n tkt tmp n tkt
View Full Document
Unlocking...