Question

1 Introduction

This assignment requires the design and implementation of a multithreaded event scheduler. This will give you an opportunity to write a multithreaded program that reads in and store event requests in any order and then executes the requests in order in real time. You will gain experience in writing a multithreaded program that uses timers, signals, signal handlers and semaphores to manage the use of a shared data structure. Your program will have two threads. The first thread will read event requests from stdin. An event request will consist of a timestamp and an event string. The incoming event requests may be entered in any order. The first thread will reject any event request scheduled to happen in the past (before now) and add any future request to a MinHeap shared with the second thread. The second thread will respond to timer events (”timeouts”). The second thread will block until a timeout and then respond to the timeout by updating now by the most recent unperformed event in the MinHeap. It will then extract and perform all events prior to the updated now.

2 Event Requests

An event request has two parts: A timestamp and the request string. The timestamp is a string of the form ”yyyy/ddd/hh/mm/ss”. Note the use of Julian dates (where the ddd is in the range 1-366) instead of Gregorian dates. The use of Julian dates removes (most of) the need to worry about validating the timestamp. You don’t have to check for ”April 31”. You don’t have to worry about leap years, so ”2017/366/00/00/00” is perfectly fine even though 2017 is not a leap year. You can perform ordering comparisons on the timestamp with simple string comparisons. The request string is just a simple string. The string contents take the place of an encoded request that might be arbitrarily complicated. As far as this program is concerned, ”performing a request” is nothing more than printing out the request string and the associated timestamp. In a more realistic implementation, performing the request would involve various forms of application-specific activities.

3 The MinHeap

The data structure of choice for string and retrieving ordered event requests is the MinHeap. The MinHeap allows you to add data elements in any order and later extract them in increasing order. The lowest element in the minheap is always at the top of the heap structure, and thus readily and inexpensively available. 1 The MinHeap data structure will be extensible and be able to hold any number of event requests, ordered by timestamp.

4 Starting Now

This is not just an admonition to start working on the program immediately, it is also something your program needs to do its job. For the sake of your sanity and the sanity of your valiant TA, we will not extract the actual current date and time in our program. Instead, your program will take a timestamp in the same form as the event request timestamps as a command-line argument. This argument then becomes the programs initial idea of the current time (now). The first thread reads incoming event requests and rejects any request whose timestamp is less than (i.e. earlier tha) now. The scheduler cannot perform actions in the past. Extra credit if you can come up with a working time-travel mechanism to support performing actions before they are scheduled. As events are performed, the program will have to update its idea of now to match the timestamp of the most recently performed requst.

5 Timers and Timeouts

The UNIX/Linux timmer is a fairly primitive mechanism. One sets a timer to go off some number of seconds and nanoseconds in the future. Your process continues execution after setting the timer. After the specfied span has elapsed (a ”timeout”), your process gets a SIGALRM signal. Note that timer delays are expressed in terms of a relative time span rather than absolute dates and times. Your program will calculate a relative time span as ”future timestamp minus now”. Both the first and second threads have to reset the timer to the nearest scheduled future event. The first thread resets the timer when it adds a new event request to the MinHeap. Keep in mind that an event request with an earlier timestamp may have been read after the earlier entry of an event request with a later timestamp. The second thread will have to reset the timer after the extraction of some event requests. There may be more events in the MinHeap scheduled to happen in the future.

6 Sanity

The format of the timestamp string allows to specify time and dates centuries into the future. It is inadvisable to submit test data specifying centuries, decades or years into the future as it slows down the grading of your program by your TA, who certainly has better things to do for the rest of this century than watch your program do nothing for extended periods between scheduled events. Any test data you submit and any test data we use to grade your program should encompass a fairly small span of time, not more than a minute or two. Your program should deal with multiple event requests scheduled for the same time. Multiple event requests scheduled for the same time can be executed in any order.

7 Extra Credit

We’ve greatly oversimplified the execution of a request, merely printing out the descriptive string. Let’s assume that the actual execution of a request takes some time. Input to your program would now be [timestamp, duration, event string]. The duration, exressed in seconds, specifies how long it would take to ”execute”the request. If the second thread pretented to do some action (faked by sleep()ing) for the duration while holding a mutex, the first thread would get blocked from adding new event requests. We could solve this by having the second thread spawn a worker thread to do time-expensive requests. The worker thread would pretend to do some action, again by sleep()ing, leaving the original second thread free to continue to extract and execute requests.

8 Deadlocks and Race Conditions

There should be NO DEADLOCKS and NO RACE CONDITIONS in your code.

9 Program Termination

Your program should shut down gracefully after all requests have been performed.

Answer 1

typedef struct{
chhar buffer[size];

int occupy;

int nextinput;

int nextoutput;

pthread_mutex_t mutex;

pthread_cond_t more;

pthread_cond_t less;

}buffer_t;

void producer(buffer_t *b, char item)

{

private BlockingQueue<LocalTime> data;
private final LinkedBlockingQueue<Result> results = new LinkedBlockingQueue<Result>();

public void run() {
while (!data.isEmpty()) {
    for (LocalTime dataTime : data) {
      if (new LocalTime().isAfter(dataTime)) {
        results.put(result);
      }
    }
}
}

pthread_mutex_lock(&b->mutex);

while(b->occupied >=Buffersize)

pthread_cond_wait(&b->less,-&->mutex);

assert(b->ocuupied < buffersize);

b->buffer[b->nextin++] = item;

b->nextinpu t%=buffersize;

b->occupied++;

pthread_cond_signal(&b->more);

pthread_mutex_unlock(&b->mutex);

}

char consumer(buffer__t *b)

{

char item;

pthread_mutex_lock(&b->mutex);

while(b->occupied >0)

item=b->buffer[b->nextout++];

b->nextout%=buffersize;

b->occupied--;

pthread_cond_signal(&b->less);

pthread_mutex_unlock(&b->mutex);

return item;

}