Deli simulation with user-level thread library
Overview
This project will give you experience writing simple multi-threaded programs
using monitors. In addition to this lab, you are encouraged to review and practice
concurrency problems on the concurrency page.
You will see this lab referred to as "p1d" for historical reasons. The moniker "p1"
refers to a package of thread-related labs that includes "p1t" (implementing threads)
and "p1s" (implementing synchronization). They use the C++ language rather than C.
These labs are borrowed from Prof. Peter Chen
at Michigan.
Please do not publish your solution code. We must answer to him for it.
Prior abuses by Duke students have come to his attention, and it reflects badly on us.
These labs are characterized by AG testing that is unusually stringent and exacting.
For these labs the tests are "secret".
AG reveals little about your specific errors. The purpose is to place responsibility for
testing your code on you. To further encourage you to test your code, you are asked
to create a test suite for the thread library and submit it for grading.
The test suite is due with the third
thread lab p1s, but you should be working on it all along.
We give you a small test case for deli, but you should also experiment with larger
test cases.
For p1d you write a simple
concurrent program that schedules deli orders. This concurrent program
uses a thread library that we provide. The grader considers a single source
file: deli.cc. It examines the output from deli.cc under secret test cases.
You must follow the instructions for your output byte-for-byte exactly to
receive points from the AG.
Thread library interface
This section describes the interface to the thread library.
You write a multi-threaded program that uses this interface. Later
your write your own implementation of this interface.
int thread_libinit(thread_startfunc_t func, void *arg)
thread_libinit initializes the thread library. A user program should call
thread_libinit exactly once (before calling any other thread
functions). thread_libinit creates and runs the first thread. This first thread
is initialized to call the function pointed to by func with the single argument
arg. Note that a successful call to thread_libinit does not return to the
calling function. Instead, control transfers to func, and the function that
calls thread_libinit will never execute again.
int thread_create(thread_startfunc_t func, void *arg)
thread_create is used to create a new thread. When the newly created
thread starts, it calls the function pointed to by func, passing the
single argument arg.
int thread_yield(void)
thread_yield causes the current thread to yield the CPU to the next
runnable thread. It has no effect if there are no other runnable threads.
thread_yield is used to test the thread library. A normal concurrent
program should not depend on thread_yield; nor should a normal concurrent
program produce incorrect answers if thread_yield calls are inserted
arbitrarily.
int thread_lock(unsigned int lock)
int thread_unlock(unsigned int lock)
int thread_wait(unsigned int lock, unsigned int cond)
int thread_signal(unsigned int lock, unsigned int cond)
int thread_broadcast(unsigned int lock, unsigned int cond)
thread_lock, thread_unlock, thread_wait, thread_signal, and thread_broadcast
implement Mesa monitors in your thread library.
A lock is identified by an unsigned integer (0 - 0xffffffff). Each lock
has a set of condition variables associated with it (numbered 0 -
0xffffffff), so a condition variable is identified uniquely by the tuple
(lock number, cond number). Programs can use arbitrary numbers for locks
and condition variables (i.e., they need not be numbered from 0 - n).
Note: it follows that if you use a condition number under two different locks, the
thread library understands it as two distinct condition variables.
Each of these functions returns -1 on failure. Each of these functions returns 0
on success, except for thread_libinit, which does not return at all on success. It is
wise to check your return values.
A thread finishes when it returns from the function that was specified in thread_create.
When there are no runnable threads in the system (e.g. all threads have finished, or all threads are deadlocked), the thread library prints:
Thread library exiting.
Bugs in your program may cause your thread library to exit sooner than expected. If this happens, it is likely because one or more of your thread_startfunc_t in your program have returned prematurely, and/or all surviving threads are blocked, leaving nobody to wake them up (deadlock).
Here is the file "thread.h". DO NOT MODIFY OR RENAME IT. thread.h is to be
included by programs that use the thread library, and should also be included by
your library implementation.
-------------------------------------------------------------------------------
/*
* thread.h -- public interface to thread library
*
* This file should be included in both the thread library and application
* programs that use the thread library.
*/
#ifndef _THREAD_H
#define _THREAD_H
#define STACK_SIZE 262144/* size of each thread's stack */
typedef void (*thread_startfunc_t) (void *);
extern int thread_libinit(thread_startfunc_t func, void *arg);
extern int thread_create(thread_startfunc_t func, void *arg);
extern int thread_yield(void);
extern int thread_lock(unsigned int lock);
extern int thread_unlock(unsigned int lock);
extern int thread_wait(unsigned int lock, unsigned int cond);
extern int thread_signal(unsigned int lock, unsigned int cond);
extern int thread_broadcast(unsigned int lock, unsigned int cond);
/*
* start_preemptions() can be used in testing to configure the generation
* of interrupts (which in turn lead to preemptions).
*
* The sync and async parameters allow several styles of preemptions:
*
* 1. async = true: generate asynchronous preemptions every 10 ms using
* SIGALRM. These are non-deterministic.
*
* 2. sync = true: generate synchronous, pseudo-random preemptions before
* interrupt_disable and after interrupt_enable. You can generate
* different (but deterministic) preemption patterns by changing
* random_seed.
*
* start_preemptions() should be called (at most once) in the application
* function started by thread_libinit(). Make sure this is after the thread
* system is done being initialized.
*
* If start_preemptions() is not called, no interrupts will be generated.
*
* The code for start_preemptions is in interrupt.cc, but the declaration
* is in thread.h because it's part of the public thread interface.
*/
extern void start_preemptions(bool async, bool sync, int random_seed);
#endif /* _THREAD_H */
-------------------------------------------------------------------------------
start_preemptions() is part of the interrupt library we provide
(libinterrupt.a), but its declaration is included as part of the interface that
application programs include when using the thread library. Application programs
can call start_preemptions() to configure whether (and how) timer interrupts are
generated (emulated) as the program runs. These timer interrupts can
preempt a running thread and start the next ready thread by forcing the preempted thread to call
thread_yield(). If you want to test a program in the presence of these
preemptions, have the application program call start_preemptions() once in the
beginning of the function started by thread_libinit().
Concurrent Deli
In this part of the project, you write a concurrent program to simulate a
deli. We provide a working thread library (thread.o) for you to use while
testing your deli simulation. When you later write your thread library, the deli
program will also help you test your thread library (and vice versa).
The deli has a list of 1,000 sandwich types, and each sandwich is assigned its own unique number between 0 and 999 on the menu. Sandwiches that are numerically close share many of the same ingredients. For example, a classic reuben (corned beef, swiss cheese, sauerkraut, and Russian dressing on rye) might be sandwich number 2, a "Dinty moore" (corned beef, lettuce, tomato, and Russian dressing on rye) might be sandwich number 4, and a "BBQ Chicken" (pulled BBQ chicken with white cheddar on a challah bun) might be sandwich number 977.
The deli contains one master sandwich maker and a variable number of cashiers,
who take orders from queued customers. The cashiers and sandwich maker
communicate via a fixed-size cork board. Cashiers post orders on the board so
that the sandwich maker knows (1) what to prepare, and (2) which cashier posted
the order. The board can hold a maximum number of order requests (max_orders).
Cashiers must wait if the board is full.
Your program should start by creating a specified number of cashier threads to
read in sandwich orders from a file and one thread for the sandwich maker.
There
are no customer threads. Instead, each cashier thread receives and forwards a
series of sandwich requests, which are specified in its input file.
A cashier
thread must wait until the sandwich maker has finished the last request from the
cashier before submitting its next order to ensure that a cashier's orders are
completed in FIFO order. This is to prevent a customer from getting upset
because someone behind them in line received their sandwich first.
Also, because the sandwich maker's board has limited capacity,
cashiers may need to wait for an open spot to appear.
A cashier thread finishes
after all the sandwiches in its input file have been prepared (completed) by the sandwich
maker.
While orders received by each cashier thread are prepared in FIFO order, the
sandwich maker does NOT prepare sandwiches from the board in FIFO
order. Instead, the sandwich maker's thread chooses the next sandwich based on
how similar it is to the one it just completed. This way the sandwich maker can
reduce latency between sandwiches by re-using as many materials as possible from
sandwich to sandwich. In other words, the next sandwich that the sandwich maker
should make is the one with the number on the board that is closest to the value
of the last sandwich it made. The maker is initialized with her last sandwich as -1.
Keep the cork board as full as possible to minimize average time between
sandwiches. That is, your sandwich-maker thread should handle a request only
when the cork board has the largest possible number of orders. This gives the
maker thread the largest number of sandwiches to choose from. Note that the
"largest number of orders" varies depending on how many cashier threads are
still active. When at least max_orders cashier threads are alive, the largest
possible number of requests on the board is max_orders. When fewer than
max_orders cashier threads are alive, the largest number of orders on the board
is equal to the number of living cashier threads. You will probably want to
maintain the number of living cashier threads as shared state.
Deli input
Your program is called with several command-line arguments. The first
argument specifies the maximum number of orders that the cork board can
hold. The rest of the arguments specify a list of input files (one input file
per cashier). I.e., the input file for cashier c is argv[c+2], where 0 <= c <
(number of cashiers). The number of cashier threads is given by the
number of input files specified.
The input file for each cashier contains that cashier's series of sandwich
orders. Each line of the input file specifies the requested sandwich (0 to
999). You may assume that input files are formatted correctly. Open each input
file read-only (use ifstream rather than fstream).
Deli output
After issuing a request, a cashier thread should call (note the space characters
in the strings):
cout << "POSTED: cashier " << cashier << " sandwich " << sandwich << endl;
An order is available to be made (i.e., has been posted to the board) when the
cashier thread prints this line.
After making a sandwich, the maker thread should make the following call (note
the space characters in the strings):
cout << "READY: cashier " << cashier << " sandwich " << sandwich << endl;
An order is considered to be complete and off the board when the sandwich-maker
thread prints this line.
Your program should not generate any other output. Note that the console is
shared between the different threads. Hence the couts in your program must be
protected by a monitor lock to prevent interleaving output from multiple
threads.
Sample input/output
Here is an example set of input files (sw.in0 - sw.in4). These sample input
files will be in the course repo.
sw.in0 sw.in1 sw.in2 sw.in3 sw.in4
------ ------ ------ ------ ------
53 914 827 302 631
785 350 567 230 11
Here is one of several possible correct outputs from running the deli simulation with the following command:
./deli 3 sw.in0 sw.in1 sw.in2 sw.in3 sw.in4
(The final line of the output is produced by the thread library, not the deli simulation.)
-------------------------------------------------------------------------------
POSTED: cashier 0 sandwich 53
POSTED: cashier 1 sandwich 914
POSTED: cashier 2 sandwich 827
READY: cashier 0 sandwich 53
POSTED: cashier 3 sandwich 302
READY: cashier 3 sandwich 302
POSTED: cashier 4 sandwich 631
READY: cashier 4 sandwich 631
POSTED: cashier 0 sandwich 785
READY: cashier 0 sandwich 785
POSTED: cashier 3 sandwich 230
READY: cashier 2 sandwich 827
POSTED: cashier 4 sandwich 11
READY: cashier 1 sandwich 914
POSTED: cashier 2 sandwich 567
READY: cashier 2 sandwich 567
POSTED: cashier 1 sandwich 350
READY: cashier 1 sandwich 350
READY: cashier 3 sandwich 230
READY: cashier 4 sandwich 11
Thread library exiting.
-------------------------------------------------------------------------------
Tips
We provide a working thread library (thread.o) for you to use while testing
your deli. You should first get your deli working without preemption, then test
it with preemption enabled. The section above explains how to configure
preemptions in your testing.
Example program
Here is a short program that uses the thread library, along with the output generated by the program. Make sure you understand how the CPU is switching between two threads (both in function loop). "i" is on the stack and so is private to each thread. "g" is a global variable and so is shared among the two threads.
-------------------------------------------------------------------------------
#include <stdlib.h>
#include <iostream>
#include "thread.h"
#include <assert.h>
using namespace std;
int g=0;
void loop(void *a) {
char *id;
int i;
id = (char *) a;
cout <<"loop called with id " << (char *) id << endl;
for (i=0; i<5; i++, g++) {
cout << id << ":\t" << i << "\t" << g << endl;
if (thread_yield()) {
cout << "thread_yield failed\n";
exit(1);
}
}
}
void parent(void *a) {
int arg;
arg = (long int) a;
cout << "parent called with arg " << arg << endl;
if (thread_create((thread_startfunc_t) loop, (void *) "child thread")) {
cout << "thread_create failed\n";
exit(1);
}
loop( (void *) "parent thread");
}
int main() {
if (thread_libinit( (thread_startfunc_t) parent, (void *) 100)) {
cout << "thread_libinit failed\n";
exit(1);
}
}
-------------------------------------------------------------------------------
parent called with arg 100
loop called with id parent thread
parent thread:00
loop called with id child thread
child thread:00
parent thread:11
child thread:12
parent thread:23
child thread:24
parent thread:35
child thread:36
parent thread:47
child thread:48
Thread library exiting.
-------------------------------------------------------------------------------
Project logistics
Write your thread library and deli simulation in C++ on Linux. The public
functions in thread.h are declared "extern", but all other functions and global
variables in your thread library should be declared "static" to prevent naming
conflicts with programs that link with your thread library.
Compile application source deli.cc into executable deli with the
solution thread library thread.o as follows:
g++ -o deli thread.o deli.cc libinterrupt.a -ldl -no-pie
Use g++ (/usr/bin/g++) to compile your programs. You may use any functions
included in the standard C++ library, including (and especially) the STL. You
should not use any libraries other than the standard C++ library.
Your deli simulation must be in a single file called "deli.cc".
Your git repo includes copies of thread.h, thread.o, interrupt.h, and libinterrupt.a. Do not modify them.
Because your programs are auto-graded, you must be careful to follow the
exact rules in the project description:
1) (deli simulation) Print only the two items specified above.
2) (deli simulation) Your program should expect several command-line
arguments, with the first being max_orders and the others
specifying the list of input files for the requester threads.
3) Do not modify source code included in this handout (thread.h,
interrupt.h).