Lecture 4 Threads weaving control flow CSE 120 Principles of Operating Systems Alex C Snoeren HW 1 Due NOW Announcements Homework 1 due now Project 0 due tonight Project groups Please send project group info to Jose Project 1 will start on Thursday CSE 120 Lecture 4 Threads 2 Processes Recall that a process includes many things Creating a new process is costly because of all of the data structures that must be allocated and initialized An address space defining all the code and data pages OS resources e g open files and accounting information Execution state PC SP regs etc Recall struct proc in Solaris which does not even include page tables etc Communicating between processes is costly because most communication goes through the OS Overhead of system calls and copying data CSE 120 Lecture 4 Threads 3 Parallel Programs Also recall our Web server example that forks off copies of itself to handle multiple simultaneous requests Or any parallel program that executes on a multiprocessor To execute these programs we need to Create several processes that execute in parallel Cause each to map to the same address space to share data They are all part of the same computation Have the OS schedule these processes in parallel logically or physically This situation is very inefficient Space PCB page tables etc Time create data structures fork and copy addr space etc CSE 120 Lecture 4 Threads 4 The Soul of a Process What is similar in these cooperating processes What don t they share Each has its own execution state PC SP and registers Key idea Why don t we separate the concept of a process from its execution state They all share the same code and data address space They all share the same privileges They all share the same resources files sockets etc Process address space privileges resources etc Execution state PC SP registers Exec state also called thread of control or thread CSE 120 Lecture 4 Threads 5 Threads Modern OSes Solaris NT modern Unix separate the concepts of processes and threads A thread is bound to a single process The thread defines a sequential execution stream within a process PC SP registers The process defines the address space and general process attributes everything but threads of execution Processes however can have multiple threads Each process has at least one thread Threads become the unit of scheduling Processes are now the containers in which threads execute Processes become static threads are the dynamic entities Each CPU runs one thread at a time CSE 120 Lecture 4 Threads 6 Threads in a Process Stack T1 Thread 2 Thread 1 Stack T2 Stack T3 Thread 3 Heap Static Data PC T3 PC T2 Code PC T1 CSE 120 Lecture 4 Threads 7 Thread Design Space One Thread per Process One Address Space MSDOS One Thread per Process Many Address Spaces Early Unix Address Space Thread Many Threads per Process One Address Space Java VM CSE 120 Lecture 4 Threads Many Threads per Process Many Address Spaces Solaris Linux NT MacOS 8 Why Use Threads Separating threads and processes makes it easier to support parallel applications Concurrency multithreading can be very useful Creating concurrency does not require creating new processes Low overhead sharing between threads in same process Improving program structure Handling concurrent events e g Web requests Taking advantage of multiple CPUs Overlapping I O with computation But brings a whole new meaning to Spaghetti Code Forcing OS students to learn about synchronization CSE 120 Lecture 4 Threads 9 Threads Concurrent Servers Using fork to create new processes to handle requests in parallel is overkill for such a simple task Recall our forking Web server while 1 int sock accept if child pid fork 0 Handle client request Close socket and exit else Close socket CSE 120 Lecture 4 Threads 10 Threads Concurrent Servers Instead we can create a new thread for each request web server while 1 int sock accept thread fork handle request sock handle request int sock Process request close sock CSE 120 Lecture 4 Threads 11 Scheduling Threads No longer just scheduling processes but threads We have basically two options Kernel scheduler used to pick among PCBs Now what Kernel explicitly selects among threads in a process Hide threads from the kernel and have a user level scheduler inside each multi threaded process Why do we care Think about the overhead of switching between threads Who decides which thread in a process should go first What about blocking system calls CSE 120 Lecture 4 Threads 12 Kernel Level Threads OS now manages threads and processes OS managed threads are called kernel level threads or lightweight processes All thread operations are implemented in the kernel The OS schedules all of the threads in the system NT threads Solaris lightweight processes LWP Scheduler deals in threads PCBs are no longer scheduled If a thread blocks another thread in the same process can run Kernel ready queue CSE 120 Lecture 4 Threads 13 Kernel Thread Limitations Kernel level threads make concurrency much cheaper than processes Much less state to allocate and initialize However for fine grained concurrency kernel level threads still suffer from too much overhead Thread operations still require system calls Ideally want thread operations to be as fast as a procedure call Kernel level threads have to be general to support the needs of all programmers languages runtimes etc For such fine grained concurrency need even cheaper threads CSE 120 Lecture 4 Threads 14 User Level Threads To make threads cheap and fast they need to be implemented at user level User level threads are managed entirely by a run time system a k a user level thread library Invisible to kernel A thread represented inside process by a PC registers stack and small thread control block TCB Creating a new thread switching and synchronizing threads are done via user level procedure call User level thread operations 100x faster than kernel threads Thread library Kernel ready queue CSE 120 Lecture 4 Threads 15 User Thread Limitations But user level threads are not a perfect solution User level threads are invisible to the OS They are not well integrated with the OS As a result the OS can make poor decisions As with everything else they are a tradeoff Scheduling a process with idle threads Blocking a process whose thread initiated an I O even though the process has other threads that can execute Unscheduling a process with a thread holding a lock Solving this requires communication between the kernel and the
View Full Document
Unlocking...