CPS221 Lecture: Threadslast revised 6/27/11Objectives1.To introduce threads in the context of processes2.To introduce UML Activity Diagrams Materials: 1.Diagram showing state of memory for a process2.Diagram showing code being executed by a thread and corresponding stack3.Diagram showing thread states4.UnthreadedRacers and ThreadedRacers to demonstrate + code to project5.AWThreadDemo.java to demonstrate6.AWTBlockDemo.java7.Handout of code for ThreadedRacers8.UML Activity Diagram for Racer problemI.Processes and ThreadsA.As you know, abstraction is a fundamental design tool in many areas of computer science. In the realm of operating systems, we have already noted that the fundamental abstraction is the notion of a PROCESS.1.Recall that a process is a PROGRAM IN EXECUTION. 2.At any given time, the status of a process includesa)Information about resources that may be allocated to the process (e.g. open files)b)One or more threads of executionc)A region of memory holding its code and data. The memory belonging to a process is typically divided into four regions 1(1)Code (called text in the Unix world)(2)Fixed data (static variables).(3)Heap: objects created dynamically as the program is running (e.g. by an operation such as new)(4)Stack - contains a frame for each routine currently executing that holds parameters, local variables and return addresses.PROJECT2int i = 3;a() {main() { int j = 7; Foo f = new Foo() f.a(3);}class Foo{ double x; void a(int k) { int l;!... }}State of memory when executing the following code at point shown(main(), a(), and any other code)Frame for main() (exit at end)jfFrame for a() (return to main)klobject of class Foox(Room for growth)iSTACKDATAHEAPCODE(5)The code and data regions are of fixed size, but the heap and stack can change size as the program runs.(a)The heap grows whenever an object is created by an operation such as new. Depending on the programming language in use, the space allocated for the object can be freed up for use by another object by explicit deletion or by garbage collection. But since it is not possible to predict when this might occur (if it ever does), such objects are said to have indefinite lifetime.(b)The stack grows when a routine is called, and shrinks when the routine returns. Routine call and return obeys a last-in-first-out order.(c)To allow the heap and stack to grow and shrink independently, they are allocated as two separate regions, growing in opposite directions as shown by the arrows.3.Frequently, a process has only a single thread of executiona)Historically, this was always the case.b)Today, for a variety of reasons, this is not necessarily the case. Modern operating systems incorporate support for multiple threads within a single process. For this reason, the book we are using distinguishes between threads of execution (discussed in chapter 2) and processes (discussed in chapter 7). We will largely follow that distinction.B.More about Threads of Execution (commonly abbreviated to just Threads)31.Until now, the programs you have written have typically had a single thread of execution. We will see shortly how to make use of a multiple threads within a program; but for now, we’ll focus on an individual thread.2.A thread is defined by three things:a)The address in memory of the instruction it is executing - typically contained in a special register in the CPU called the program counter (PC).b)The values that are present in other CPU registers.c)An execution history, representing the procedure calls that have brought it to its current point. This history is commonly called the thread’s stack, and it contains one stack frame for each procedure that is still active, which holds its parameters, local variables, and other information:Example: Suppose we have the following:! PROJECTclass SomeClass {!void p0() {!!...!}!void p1() { !!int v1; !!... !!p2(); !!... !}!void p2() { !!int v21, v22; !!... !!p3(); !!... !}4!void p3() {!!...!! /* Here */ !!...!}!public static void main(String [] args) {!!p0();!!p1();}When execution is at the point marked Here, the stack would look like this:PROJECTParameter args(Other information)Local variable v1(Other information)Local variables v21,v22(Other information)(No locals or parameters)(Other information)Frame for main()Frame for p1()Frame for p2()Frame for p3()(Notice there is no frame for p0(), since it completes execution before p1() is called.)3.One other important piece of information maintained for a thread is its state - is it currently able to continue execution, or must further execution wait until some event occurs (e.g. the completion of an IO operation it has requested) Over the course of its lifetime, a thread transitions between various states.5PROJECTRUNNING BLOCKEDdispatchREADYtimerpre-emptionIO or event waitIO or event completecreationexita)On a one-CPU system with a single core, there is exactly one running thread at any given time. On a multi-core system (or one with multiple CPU’s), there can be as many running threads as there are cores. (If there are not enough threads eligible to run, the operating system includes a “do-nothing” null thread that can be run until some other thread becomes ready.)b)(Discuss other transitions)c)The diagram shows that a thread terminates as a result of executing an exit() operation. Actually, many systems also allow a thread to be terminated from the other states by some other thread.C.To manage the various threads, the operating system maintains a set of data structures called THREAD CONTROL BLOCKS (TCB's) - one per process. (On a system that only supports one thread per process, this may be combined with the information the system maintains about the process in the process control block, or PCB).61.Each TCB contains information about its thread, including:a)Identification information (what process it is part of, and some sort of identification within its process)b)The state of the thread (running, ready, or blocked).c)The values of the CPU registers if the thread is not currently running. (When the thread is running, these values are actually in the hardware registers and change constantly)2.One major use of the TCB's is in conjunction with a CONTEXT SWITCH operation.a)A context switch occurs whenever the a new thread is given use of the CPU in place of the one that is currently running. This can happen for one of two reasons:(1)The running thread has performed some operation - e.g. issued