CPS110: Landon Cox Page 1 of 16 Threads and concurrency Motivation Operating systems are becoming extremely complex Multiple users, programs, I/O devices, etc How should we manage this complexity? Decompose or separate hard problem into several simpler ones Programs decompose into several rows int main () { getInput (); computeResult (); printOutput (); } void getInput () { cout (); cin (); } void computeResult () { sqrt (); pow (); } void printOutput () { cout (); } Processes decompose mix of activities running on a processor into several parallel tasks (columns). Each job can work independently of the others Remember, for any area of the OS, ask: What interface does the hardware provide? What interface does the OS provide? Job 1 Job 2 Job 3 main computeResult printOutputCPS110: Landon Cox Page 2 of 16 What is in a process? Definition of a process Informal: a program in execution; a running piece of code along with all the things the code can read/write Note that a process is not a program. Formal: one or more threads in their own address space Play analogy Thread Sequence of executing instructions from a program (i.e. the running computation) Active Play analogy: Address space All the data the process uses as it runs Passive (acted upon by threads) Play analogy: the objects on stage during a performance Types of data in the address spaceCPS110: Landon Cox Page 3 of 16 Multiple threads Can have several threads in a single address space Play analogy: several actors on a single set. Sometimes they interact (e.g. do a little dance together) and sometimes they perform independently. Private state for a thread vs. global state shared between threads What private state must a thread have? Other state is shared between all threads in a process Upcoming lectures Concurrency: multiple threads active at one time (multiple threads could come from one process or from multiple processes) Thread is the unit of concurrency Two main topics: o How can multiple threads cooperate on a single task? o How can multiple threads share a single CPU? Address space Address space is the unit of state partitioning Main topic o How can multiple address spaces share a single physical memory efficiently and safely?CPS110: Landon Cox Page 4 of 16 Can threads be truly independent? Possible to have multiple threads on a computer system that don’t cooperate or interact at all? e.g. mail program reads a PDF attachment and starts acroread process to display the attachment? e.g. running an mp3 player and cps110 project on a computer at the same time? Two possible sources of sharing Correct example of non-interacting threads Web server example But if threads are cooperating, is it still a helpful think of multiple threads? Or is it simpler to think of a single thread doing multiple things? How to build a web server that receives multiple, simultaneous requests, and that needs to read files from disk to satisfy each request? Handle one request at a time easy to program, but slow. Can’t overlap disk requests with computation or network service.CPS110: Landon Cox Page 5 of 16 Event-driven with asynchronous I/Os need to keep track of multiple outstanding requests o request 1 arrives o web server receives request 1 o web server starts disk I/O 1a to satisfy request 1 o request 2 arrives o web server receives request 2 o web server starts disk I/O 2a to satisfy request 2 o request 3 arrives o disk I/O 1a finishes at each point, web server must remember which requests have arrived and are being serviced, what disk I/Os are outstanding and which requests they belong to, and what disk I/Os still need to be done to satisfy each request Multiple cooperating threads each thread handles one request each thread can issue a blocking disk I/O , wait for I/O to finish, and continue with the next part of its request even though a thread blocks, other threads can make progress (and new threads can be started to handle in-coming requests) where is the state of each request stored? Benefits and uses of threads The thread system of an operating system manages the sharing of the single CPU among several threads (e.g. allowing one thread to issue a blocking I/O and still allow other threads to make progress). Applications (or higher-level parts of the OS) get a simpler programming model. Typical domains that use multiple threads program uses some slow resource, so it pays to have multiple things happening at once physical controller (e.g. airplane controller) slow component: window system (1 thread per window) slow component: network server slow component: parallel programming (using for multiple CPUs) slow component:CPS110: Landon Cox Page 6 of 16 Cooperating threads First major topic in threads: how multiple threads can cooperate on a single task assume for now that we have enough physical processors to run each thread in its own CPU later we’ll discuss how to give the illusion of infinite physical processors on a single processor Ordering events from different threads is non-deterministic processor speeds may vary e.g. after 10 seconds, different threads may have gotten differing amounts of work done thread A thread B thread C Non-deterministic ordering produces non-deterministic results Printing example thread A: print ABC thread B: print 123 possible outputs? impossible outputs? Ordering within a thread is guaranteed to be sequential, but there are lots of ways to merge the orderings between threads What is being shared between