Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29Slide 30Slide 31Slide 32Slide 33Slide 34Slide 35Slide 36Slide 37Slide 38Slide 3915-410, F’04- 1 -The ThreadSep. 15, 2004Dave EckhardtDave EckhardtBruce MaggsBruce MaggsL07_Thread15-410“Maybe the world has enough sokoban implementations?”15-410, F’04- 1 -SynchronizationProject 1Project 1Should have much of console workingShould have some progress (at least design) for kbd, timerWrite good codeWrite good codeConsole driver will be used (and extended) in P315-410, F’04- 1 -Book Report GoalsSome of you are going to grad. schoolSome of you are going to grad. schoolSome of you are wondering about grad. schoolSome of you are wondering about grad. schoolSome of you are Some of you are inin grad. school grad. schoolYou should be able to read a Ph.D. dissertationMore generallyMore generallyLooking at something in depth is differentNot like a textbook15-410, F’04- 1 -Book Report GoalsThere's more than one way to do itThere's more than one way to do itBut you don't have time to try all the ways in 410Reading about other ways is good, maybe funHabituationHabituationLong-term career development requires studyWriting skills (a little!)Writing skills (a little!)“Summarizing” a book in a page is tough15-410, F’04- 1 -Book ReportRead the “handout”Read the “handout”Browse the already-approved listBrowse the already-approved listPick something (soon)Pick something (soon)Don't make me stop the car...Read a bit before you sleep at nightRead a bit before you sleep at nightor: before you sleep in the morningand/or: Thanksgiving breakRecommended by previous OS students!Recommended by previous OS students!15-410, F’04- 1 -Road MapThread lectureThread lectureSynchronization lecturesSynchronization lecturesProbably threeYield lectureYield lectureThis is importantThis is importantWhen you leave here, you will use threadsUnderstanding threads will help you understand the kernelPlease make sure you Please make sure you understandunderstand threads threadsWe'll try to help by assigning you P215-410, F’04- 1 -OutlineTextbook chaptersTextbook chaptersAlready: Chapters 1 through 4Today: Chapter 5 (roughly)Soon: Chapters 7 & 8Transactions (7.9) will be deferred15-410, F’04- 1 -OutlineThread = schedulable registersThread = schedulable registers(that's all there is)Why threads?Why threads?Thread flavors (ratios)Thread flavors (ratios)(Against) cancellation(Against) cancellationRace conditionsRace conditions1 simple, 1 ouchMake sure you really understand this15-410, F’04- 1 -Single-threaded ProcessStackCodeDataHeapRegistersstdinstdouttimer15-410, F’04- 1 -Multi-threaded ProcessstdinstdouttimerCodeDataHeapSt ackRegistersSt ackRegistersSt ackRegisters15-410, F’04- 1 -What does that mean?Three stacksThree stacksThree sets of “local variables”Three register setsThree register setsThree stack pointersThree %eax's (etc.)Three Three schedulable RAM mutatorsschedulable RAM mutators(heartfelt but partial apologies to the ML crowd)Three potential bad interactionsThree potential bad interactions15-410, F’04- 1 -Why threads?Shared access to data structuresShared access to data structuresResponsivenessResponsivenessSpeedup on multiprocessorsSpeedup on multiprocessors15-410, F’04- 1 -Shared access to data structuresDatabase server for multiple bank branchesDatabase server for multiple bank branchesVerify multiple rules are followedAccount balanceDaily withdrawal limitMulti-account operations (transfer)Many accesses, each modifies tiny fraction of databaseServer for a multi-player gameServer for a multi-player gameMany playersAccess (& update) shared world stateScan multiple objectsUpdate one or two objects15-410, F’04- 1 -Shared access to data structuresProcess per player?Process per player?Processes share objects only via system callsHard to make game objects = operating system objectsProcess per game object?Process per game object?“Scan multiple objects, update one”Lots of message passing between processesLots of memory wasted for lots of processesSlow15-410, F’04- 1 -Shared access to data structuresThreadThread per player per playerGame objects inside single memory address spaceEach thread can access & update game objectsShared access to OS objects (files)Thread-switch is cheapThread-switch is cheapStore N registersLoad N registers15-410, F’04- 1 -Responsiveness““Cancel” button vs. decompressing large JPEGCancel” button vs. decompressing large JPEGHandle mouse click during 10-second processMap (x,y) to “cancel button” areaVerify that button-release happens in button area of screen...without JPEG decompressor understanding clicks15-410, F’04- 1 -Multiprocessor speedupMore CPUs can't help a single-threaded process!More CPUs can't help a single-threaded process!PhotoShop color dither operationPhotoShop color dither operationDivide image into regionsOne dither thread per CPUCan (sometimes) get linear speedup15-410, F’04- 1 -Kinds of threadsUser-space (N:1)User-space (N:1)Kernel threads (1:1)Kernel threads (1:1)Many-to-many (M:N)Many-to-many (M:N)15-410, F’04- 1 -User-space threads (N:1)Internal threadingInternal threadingThread library adds threads to a processThread switch just swaps registersSmall piece of asm codeMaybe called yield()CodeDataHeapStackStackRegis tersStack15-410, F’04- 1 -User-space threads (N:1)+ No change to operating system+ No change to operating system- System call probably blocks all “threads”- System call probably blocks all “threads”“The process” makes a system callKernel blocks “the process”(special non-blocking system calls can help)- “Cooperative scheduling” awkward/insufficient- “Cooperative scheduling” awkward/insufficientMust manually insert many calls to yield()- Cannot go faster on multiprocessor machines- Cannot go faster on multiprocessor machines15-410, F’04- 1 -Pure kernel threads (1:1)OS-supported threadingOS-supported threadingOS knows thread/process ownershipMemory regions shared & reference-countedCodeDataHeapStackRegistersStackRegistersStackRegisters15-410, F’04- 1 -Pure kernel
View Full Document
Unlocking...