CS 162 Operating Systems and Systems Programming Put any threads waiting on the termination of this thread on the ready list Professor Anthony D Joseph Spring 2004 Lecture 5 Independent vs cooperating threads Can t deallocate thread yet since we re still running on its stack Record thread as waitingToBeDestroyed Call run new thread to run anther thread ThreadHouseKeeping will examine waitingToBeDestroyed and deallocate the finished thread s TCB and stack 5 0 Main points Thread Creation Why do we need to handle cooperating threads Atomic operations run new thread newThread PickNewThread switch curThread newThread 5 1 Thread creation ThreadHouseKeeping discussed later Thread fork create a new thread three arguments Pointer to application routine to execute fcnPtr Pointer to arguments records fcnArgPtr Size of stack to allocate Thread fork is not the same thing as UNIX fork UNIX fork creates a new process so it has to create a new address space in addition to a new thread Thread fork implementation Sanity check arguments Enter kernel mode and allocate a stack Allocate a new TCB and initialize its register fields In particular the stack pointer is made to point at the stack the PC return address is made to point at an OS assembler routine ThreadRoot and two of the registers are initialized to fcnPtr and fcnArgPtr Put the newly allocated TCB on the ready list Runnable This will cause it to eventually be dispatched by run new thread and start running the routine ThreadRoot ThreadRoot Do start up housekeeping e g record start time Return to user mode Call fcnPtr fcnArgPtr Do thread finish up call ThreadFinish ThreadFinish CS 162 Spring 2004 Lecture 5 1 6 For now don t worry about how switching between different processes address spaces is done Thread fork is very much like an asynchronous procedure call it means go do this work where the calling thread does not wait for the callee to complete What if the calling thread needs to wait Thread Join wait for a forked thread to finish Thus a traditional procedure call is logically equivalent to doing a fork then immediately doing a join This is a normal procedure call A B B CS 162 Spring 2004 Lecture 5 2 6 If the dispatcher can do any of the above programs must work under all cases for all interleavings The procedure A can also be implemented as A Thread t new Thread t Fork B So how can you know if your concurrent program works Whether all t Join interleavings will work 5 3 Definitions Independent threads 5 2 Multiprocessing vs Multiprogramming Multiprocessing multiple CPU Multiprogramming multiple jobs or processes Definition of run concurrently scheduler is free to run threads in any order e g FIFO random etc No state shared with other threads Deterministic input state determines result Reproducible Scheduling order doesn t matter Cooperating threads Shared state Non deterministic For example A B C Multiprocessing A Non reproducibility and non determinism means that bugs can be intermittent This makes debugging really hard C B Non reproducible 5 4 Why allow cooperating threads Multiprogramming A B C A B B People cooperate and computers model people s behavior so computers at some level have to cooperate 1 Share resources information One computer many users One bank balance many ATMs Embedded systems ex robot control Dispatcher can choose to run each thread to completion or time slice in big chunks or time slice so that each thread executes only one instruction at a time simulating a multiprocessor where each CPU operates in lockstep CS 162 Spring 2004 Lecture 5 3 6 CS 162 Spring 2004 Lecture 5 4 6 2 Speedup Overlap I O and computation 5 6 Atomic operations UNIX file system does read ahead Multiprocessors chop up program into smaller pieces What we want is some way of allowing a thread to perform a task without having other threads interfere with the task Atomic operation an operation that always runs to completion or not at all It is indivisible it can t be stopped in the middle and its state can t be modified by someone else during the operation 3 Modularity chop large problem up into simpler pieces For example to compile gcc cpp cc1 cc2 as ld On most machines memory reference and assignment i e load and store of words are atomic This makes the system easier to extend you can replace the assembler without changing the loader Many instructions are not atomic For example on most 32 bit architectures double precision floating point store is not atomic it involves two separate memory operations 5 5 Some simple concurrent programs Most of the time threads are working on separate data so scheduling order doesn t matter Thread A Thread B x 1 y 2 What about initially y 12 x 1 y 2 x y 1 y y 2 What are the possible values for x after the above What are the possible values of x below x 1 x 2 Can t say anything useful about a concurrent program without knowing what are the underlying indivisible operations CS 162 Spring 2004 Lecture 5 5 6 CS 162 Spring 2004 Lecture 5 6 6
View Full Document
Unlocking...