this assignment is to give you hands-on experience with thread synchronization

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

this assignment is to give you hands-on experience with thread synchronization and the pthreads library, as well as with dynamic memory allocation (i.e., malloc/calloc/realloc and free).

For this project you will need to read and understand the material in Sections 12.3 through 12.7 in your textbook, on concurrent programming with threads, as well as the information on dynamic memory allocation in Section 9.9.1-2. Introduction A function is said to be thread-safe if it does not have any race conditions — that is, if it behaves according to its specification regardless of how events are scheduled. A sufficient condition for a function to be thread-safe is if all access to shared variables is protected by appropriate synchronization mechanisms such as semaphores, mutexes, and condition variables. To complete this assignment you must use the pthread synchronization mechanisms pthread_mutex_t and pthread_cond_t. For this project you will implement two data types:

a priority queue and a thread pool. A priority queue is a list of items, each with an associated priority. Items can be inserted in any order, but the highest-priority item will always be removed first. A thread pool is an abstraction that handles processing arbitrary tasks in parallel, using threads. Each instance of a thread pool has its own associated set of worker threads, which process tasks in parallel as they are submitted to the pool. The number of worker threads can be specified when the thread pool is created (up to some maximum). In this assignment, tasks have an associated priority, and the tasks are processed in order of their priority. The major attraction of such data types is that they hide many details of the implementation, and can be used with practically any type of list item (for the priority queue) or task (for the thread pool).

Part I: Thread-Safe, Unbounded Priority Queue Type The first part of the assignment is to implement a thread-safe, unbounded priority queue. "Unbounded" means that instances of the queue does not have a fixed capacity: any number of items can be inserted without removing an item. This means you will have to use dynamic memory allocation to grow and shrink the queue as items are inserted and removed. "Items" can be anything - they are represented by a pointer. It is up to the client (i.e., the code using the implementation) to ensure that the void * that is returned is cast to the actual type.

Note that, unless everything placed into the queue is of the same type, there is no way for the client code to know what to cast the void * pointer returned by pq_next() to. So the best thing is for each instance of pq_t to be used to store only one type of item. You will define a type: typedef struct { /* your code here */ } pq_t; You will also define three functions: pq_t *pq_create(void) { /* your code here */ } — Creates and initializes a priority queue instance and returns a pointer to it. Returns NULL on error (e.g., OS out of memory - should never happen). This includes creating and initializing the void pq_insert(pq_t *q, void *item, short prio) { /* your code here */ } — insert the given item into the given queue at the given priority. This operation never blocks. If item A has priority x, and item B has priority y, and x > y, then item A will be returned before item B. Negative priorities are allowed. void *pq_next(pq_t *q) { /* your code here */ } — Returns the item in the given queue that was inserted with the highest priority.

If there is more than one item with the same priority, returns the oldest one. If the queue is empty, this operation blocks until an item is inserted. You may implement the queue abstraction any way you want, but you must use pthread_mutex_t and pthread_cond_t to synchronize access to your data structure, since it will be used by multiple threads at the same time. (In particular, your definition of pq_t must include at least one variable of type pthread_mutex_t and one of type pthread_cond_t.) You will also need to use malloc() and free() to dynamically adjust the size of the data structure. (Note: using pthreads' mutex and condition variable is probably the simplest way to implement this.) You are given the following: pq.h Download pq.h- declares the interface to the abstraction, namely, the type pq_t and the three functions above. Be sure to rename the file to "pq.h" once you have added your type declaration(s) and #defines (if any).

Also fix the typo in the first declaration: typdef ➛ typedef. Do not put any executable code in the .h file. seqdriver.c Download seqdriver.c- a simple unit test program to verify that your implementation maintains priorities correctly. You will turn in your pq.h along with a file prioq.c containing your implementation. (See turnin instructions below.) Part II: Thread Pool with Priority For the second half of this project, you will build a thread pool using your priority queue implementation. This thread pool is designed to execute only self-contained tasks — that is, tasks that do not return a value. They may, however, take a parameter and a priority. You will define a type: typedef struct { /* your code here */ } threadpool_t; You will define two functions: threadpool_t *tp_create(int nthreads) { /* your code here */ } — Creates and initializes a thread pool with the given number of "worker" threads and returns a pointer to it. This includes creating the priority queue instance that will be used. void tp_submit(threadpool_t *tp, void (*task)(void *), void *arg, short prio) { /* your code here */ } — Submit a task for execution by one of the threads in the pool indicated by the first argument. The second argument is a pointer to the task to be performed by the worker thread (by calling the given task function).

The third argument will be passed by the worker thread when it invokes the task function. The fourth argument is the task's priority; a higher value is higher priority. Once a task is invoked, it will run to completion. In this simple abstraction there is no way for a task to return a value, so any output must be handled via the file system or some other way. You are given the following: threadpool.h Download threadpool.h— declares the interface to the thread pool abstraction, namely, the type threadpool_t and the two functions above. Be sure to rename the file to "threadpool.h" once you have added your type declaration(s) and #defines (if any). Do not put any executable code in the .h file. pooldriver.c Download pooldriver.c— a simple unit test program that creates a threadpool and submits tasks to it. Command-line parameters control the size of the pool and the number of tasks to submit. The tasks are defined in the driver program;

each one simply prints its priority and a sequence number, (indicating the order it was submitted to the pool), sleeps for a random number of seconds, and then a message indicating completion. Here is a Makefile Download Makefilethat will compile both seqdriver and pooldriver, once you have the code complete. You can compile them one at a time by typing "make seqdriver" or "make pooldriver". A word to the wise: don't just blindly rely on the Makefile to compile your code. You need to understand how make works, and why the commands are what they are.

Things to note: Your definition of threadpool_t must include a variable of type pq_t, so obviously your implementation of tp_create() must call your implementation of pq_create(). You will also need to define a data type (maybe call it task_t) that tp_submit() will place in the queue. It must store (at least) the function pointer to be invoked and the argument to pass to that function. Your implementation of tp_create() must also call pthread_create() the given number of times to create the given number of worker threads. You will define a function for each thread to execute, which will loop forever, calling pq_next() and invoking the function in the returned task, passing it the given argument. Turnin You will turn in a tar or zip file containing your implementations of: pq.h and pqimpl.c threadpool.h and threadpool.c ... and nothing else. The rubric will consider correctness, but also efficiency, i.e., whether your critical section(s) are as small as possible. Hints (on both parts) The textbook doesn't cover pthread_mutex_t or pthread_cond_t. These will be covered in lecture (and you should read their man pages carefully)

. Their usage is analogous to what you did in Project 5 for a process awaiting notification from another process - using sigprocmask() and sigsuspend() to eliminate the race between checking the condition and delivery of the notification (i.e., signal). Your implementations must not depend on any knowledge about the the particular types of items placed in the queue, or jobs being submitted to the thread pool. This actually makes them simpler. Because items are only ever removed from the front of the priority queue, you only need to keep track of the beginning of the list. The simplest approach is to keep the priority queue sorted at all times.

That is: every element in the list is either higher priority than its successor, or the same priority but inserted before. When you insert a new element, you can ensure this easily by walking through the list, looking for an element e whose priority is at least (i.e., greater than or equal to) the new element's priority, and whose successor element either does not exist, or has priority less than the new element's priority. The new element becomes e's successor, and e's successor becomes the new element's successor. (Before walking through the list you have to deal with two special cases: (i) the queue is empty, or (ii) the new element has higher priority than the current highest-priority element.) It is possible to implement the thread pool in such a way that there's only one priority queue, and it's the only shared data structure.

 

 

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of