Class Note for CMPSCI 377 at UMass(4)
Class Note for CMPSCI 377 at UMass(4)
Popular in Course
Popular in Department
This 3 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 15 views.
Reviews for Class Note for CMPSCI 377 at UMass(4)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
CMPSCI 377 Operating Systems Spring 2009 Lecture 22 April 30 Lecturer Mark Corner Scribe Bruno Silva 221 Building Concurrent Applications In building concurrent systems we want to overlap access to different resources eg CPU disk network in order to hide latency and maximize parallelism and throughput Furthermore we want our systems to be relatively simple to build and maintain There are several standard threading models or patterns for building concurrent applications including thread pools producerconsumer bagof tasks and work queues We discuss these below 2211 Basic Server Model Suppose we want to program a Web server we could easily do so without using concurrency as follows whi1etrue wait connection read from socket and parse url look up url contents in cache if in cache fetch from disk put in cache send data to client How do we make this code work for lots and lots of clients Since there are a lot of slow operations being performed eg connecting to the networking accessing the disk etc processing only one client at a time clearly is not scalable Our goal then is to build a concurrent application that both minimizes latency and maximizes parallelism 2212 New Thread for each Client We could improve the model above using our previous knowledge of programming with threads and just spawn a new thread for each new connection to the server This would work but with the drawback of requiring lots of thread creation operations which can be relatively expensive 2213 Thread Pools Another solution then would be to keep a pool of threads Whenever a new task arrives the system would simply get a thread from pool and set that thread to work on the given task Whenever the pool is empty the system blocks until another thread completes its task 221 222 Lecture 22 April 30 One natural question now is how many threads do we pre create and add to the pool Ideally we would want to create an in nite or large enough amount of threads however this is clearly not possible since each thread has a descriptor a stack etc but our main memory is nite Also beyond a certain point creating more threads does not help anymore and the server starts to slow down again due to things like paging or lock contention For example if we only have 4 CPUs it doesnlt help to try to run a billion things at the same time In practice the netuning of how many thread to add to the pool for any given application is set empirically or perhaps adaptively 2214 Producerconsumer The general idea of a producerconsumer architecture is related to building a pipeline of threads similar to the web spider from Project 2 Each step of the processing will now be done by a specialized threads whenever one thread is done with its part of the processing it forwards the data to the next stage of the pipeline like a factory assembly line In a producerconsumer system we guarantee that each stage of the pipeline signals the next stage of the pipeline when it completes its task and blocks when there s nothing else for it to do etc If we were to implement our web server in a producerconsumer fashion we could simply create a pair of threads one for reading the URL requested by the client and another one for writing the answer back to the network We could also create yet another intermediate thread which would rst look for the URL in a cache This intermediate thread might help the overall average response time of the system if we can implement the shortest time to completion rst policy ie nish the easy things rst which leads to the lowest average response time As with the thread pool approach it is not always clear how many threads we need for each of stage of the pipeline the exact amount depends on the application and is usually netuned manually Since each thread has a specialized task if the number of threads for each task is not welltuned then many threads might be idle wasting resources In general the producerconsumer approach works well if the producer and the consumer are symmetric ie if they proceed roughly at same rate On the other hand if the order of processing doesn7t matter it doesnlt make sense to use a producerconsumer architecture with its ordered pipeline of processing 2215 Bag of tasks The producerconsumer model above has a standard human analogy of an assembly line Humans have specialized skills however whereas threads running the same program do not need to be specialized every thread has access to the same code and data So any thread could do the work of any other thread In the bag of tasks approach we have a collection of mostly independent worker threads we no longer need to have different types of threads one for the parser one for the workers etc A bag of tasks system is very simple every time a worker doesn7t have anything to do it goes to the bag of tasks and gets something to work on in our web server example this bag of tasks could contain new connections to be processed The advantage of the bag of tasks approach is that we can imagine all workers as being homogeneously implemented each one running a speci c piece of code depending on the type of the task it has to process at that time imagine each worker as being implemented with a big switch statement Let us now present a way to convert the pseudocode for the web server given in the rst section to a Bag of Tasks style Assume we have an addWork thread and a bunch of worker threads Lecture 22 April 30 223 addWork thread only one thread of this type whi1etrue wait connection bag put url worker thread there will be a bunch of these threads whi1etrue url bagpoll look up url contents in cache if in cache fetch from disk put in cache send data to client The bag of tasks approach seems to exploit the available parallelism well and it is easier to program and to extend It has one major performance drawback however namely that there is only one lock protecting the bag this implies contention Also imagine for instance that some of the workers are pretty quick it could be the case that they acquire the lock nish processing release the lock reacquire it etc The problem now is that each worker would be itself a new bottleneck One possible solution to this problem is to have several bags this is the approach that we discuss nextr 2216 Work queues In this type of concurrent architecture each thread has its own work queue of jobs Now contrary to the Bag of Tasks architecture we have no single point of contention surely there is still contention for the lock of each of these queues but at least there is less contention than before Although the existence of several bags eases the contention problem we now have yet another drawback suppose that one thread nishes all its jobs and yet there is still more work to be done on some other queues this should never happen given that there exists an idle thread The solution is that the idle thread voluntarily steals work from another random thread This type of behavior can actually be shown to be optimal in terms of load balancing and works great for heterogeneous tasks This is also a exible model for programming concurrent applications as it allows us to easily re de ne tasks performs automatic load balancing separates thread logic from functionality etcr Overall the use of work queues is very popular when structuring servers nowadays
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'