C++ pthread algorithm shuttle

[John Linux]

In a past prac. exam for an algorithm course I'm doing is the challenge below, and their are no solutions but it seems like a really interesting one to solve. Can someone please help and point me in the right direction, I would like to try this on my own, but please give some assistance.

I need to write a multithreaded program (using pthreads, code must run on linux, i'm using ubuntu maverick) to simulate a shuttle that operates on a circuit, stopping at the stadium, and the city center only.

1) The shuttle waits until the occupants signal for it to move to the other stop.
2) The people waiting board the shuttle, and when the last person is on they signal that the bus should begin moving.
3)The passengers exit, and when the last passenger has left, the other passengers board, and signal to leave for next stop.
4) If their are no passengers waiting, shuttle waits.
5) The shuttle can take a max of 12 people.
6) The shuttle takes 2 time units to move between stops.

Use a thread for each stop to indicate when passengers arrive.

Generate a random number between 1 and 10 to indicate the time units when a passenger arrives.

If there are more than 14 people waiting the other people elect to use the stairs.

Output a trace for twenty movements of the shuttle: ie.
Shuttle waits at stadium
Shuttle moves from stadium to city center with 8 people.
Shuttle waits at city center
Shuttle moves from city center to stadium with 10 people.

[L7Sqr]

So a basic layout could be:
Thread1 -> populating Queue1 at random interval
This represents people waiting at the stadium. When a passenger arrives and the queue is empty the thread signals a NonEmptyQueue1 condition

Thread2 -> populating Queue2 at random interval
Same as the stadium, but for the city center

Thread3 -> Controls the shuttle
if at city center, wait for NonEmptyQueue2 condition. When triggered wait for AllAboard condition, move to stadium
if at stadium, do the same except wait for NonEmptyQueue1 condition

There are other things not handled in the above. For instance, what if you are at the stadium with no people waiting and there is a line at the city center? Do you have a timeout that moves the empty shuttle to the city center to pick up the people? If not, do the people have a timeout at which point they will stop waiting and instead take the stairs?

[L7Sqr]

The conditions I talk about can be implemented with pthread_cond_t . A quick google turned up this as a starting point.

Um, this was supposed to be an edit, but I wrote in the wrong box. Ughh.

[template<>]

Objects and thread work together well. Try to model your problem in terms of classes.

For example Shuttle can be designed as an active class

[rubberman]

Template<> is pointing you in the right direction. Model the problem as classes of objects (Shuttle, Station, Passenger), define their behaviors and interactions (Shuttle arriving at station, Passenger entering shuttle, ...). Build up some finite state machines to model behavior. See where threads make the most sense. My guess is that each Shuttle, not the stations, should be threaded. The stations should have a mutex that an arriving shuttle (thread) locks, so two shuttles cannot enter the station at the same time. Have you started UML modeling yet? If so, that is how I model these sort of complex scenarios, and I have built some REALLY big systems with very few bugs as a result. I usually spend about 80% of a project's time on design and modeling, and 20% (or less) on coding. Once the model is clear and solid, coding is usually a snap. It keeps one from wandering down dead-end alleys. :-)

[John Linux]

Thanks for your input, have been busy lately:

a) It seems are we are missing the point here, the requirements suggest "Use a thread for each stop to indicate when passengers arrive.", so this is the way I would preferably like to do it.

@L7Sqr, yes I also considered the problem of the shuttle waiting at a empty stop, yet the requirements state, "If their are no passengers waiting, the shuttle waits".

This means that the scenario is quite simple, however I am not familiar enough with threads to code this yet, for example, would I require mutex's, and which other thread functions are necessary. How would I generate a time signal, for example, i wanted to simulate the system where one time unit is 30 seconds, or 15 seconds, how would I do this. Also how do I pass a signal between a thread.

ie. event happens -> thread processes event.

Also, when generating random numbers in C++ what is the best way to do it, I am more familiar with Java where random numbers, are ACTUALLY random, for example what is the best way to generate a random in c++ that would give a pretty even spread over 10 million results for example.

[John Linux]

I have found some thinks on similar topic, elevator in building, this one is simpler though as there is only one shuttle, and two stops, yet i can't seem to wrap my mind around it...

http://www.daniweb.com/software-development/cpp/threads/90056
http://www.daniweb.com/software-development/cpp/threads/193246
http://64.106.20.52/~darnold/classes/cs481/labs/lab2/

[John Linux]

@L7Sqr, I am having issues populating each Queue at random intervals

[L7Sqr]

@L7Sqr, I am having issues populating each Queue at random intervals

Here is a working example of placing values into a vector at a random time interval. The idea is that there is a shared vector and there is a producer and a consumer. The operations on the vector are locked and a condition variable is used to signal when a vector is full (and should be emptied). There are no comments so if you need further explanation please ask.

#include <iostream>
#include <cstdlib>
#include <pthread.h>
#include <vector>

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t queue_full = PTHREAD_COND_INITIALIZER;

void * worker (void * arg) {
    std::vector< int > * v = (std::vector< int > *) arg;
    int delay = rand () % 10;
    while ( true ) {
        pthread_mutex_lock (&mutex);
        v->push_back (delay);
        std::cerr << "Added " << delay << " to the queue (size: "
                    << v->size () << ")" << std::endl;
        if (v->size () > 10)
            pthread_cond_signal (&queue_full);
        pthread_mutex_unlock (&mutex);
        delay = rand () % 10;
        sleep (delay);
    }
    return NULL;
}

int main()
{
    pthread_t thread;
    std::vector< int > v;
    pthread_create (&thread, NULL, worker, (void *)&v);
    while ( true ) {
        pthread_mutex_lock (&mutex);
        pthread_cond_wait (&queue_full, &mutex);
        std::cerr << "Queue full! Flushing!" << std::endl;
        v.clear ();
        pthread_mutex_unlock (&mutex);
    }
    return 0;
}

Running the above results in something like the following:

Added 7 to the queue (size: 1)
Added 9 to the queue (size: 2)
Added 3 to the queue (size: 3)
Added 8 to the queue (size: 4)
Added 0 to the queue (size: 5)
Added 2 to the queue (size: 6)
Added 4 to the queue (size: 7)
Added 8 to the queue (size: 8)
Added 3 to the queue (size: 9)
Added 9 to the queue (size: 10)
Added 0 to the queue (size: 11)
Queue full! Flushing!
Added 5 to the queue (size: 1)
Added 2 to the queue (size: 2)
Added 2 to the queue (size: 3)
Added 7 to the queue (size: 4)
Added 3 to the queue (size: 5)
Added 7 to the queue (size: 6)
Added 9 to the queue (size: 7)
Added 0 to the queue (size: 8)
Added 2 to the queue (size: 9)
Added 3 to the queue (size: 10)
Added 9 to the queue (size: 11)
Queue full! Flushing!

[nezachem]

Notice that sleep() delays the whole process (that is all threads are sleeping). It kind of defeats the purpose, don't you think?

[John Linux]

Notice that sleep() delays the whole process (that is all threads are sleeping). It kind of defeats the purpose, don't you think?

I agree with you on this one, that is why I'm looking into the timed wait...

[L7Sqr]

Notice that sleep() delays the whole process (that is all threads are sleeping). It kind of defeats the purpose, don't you think?

Not true. See description here. Specifically, The sleep() function shall cause the calling thread to be suspended....

Run the following for yourself:

#include <iostream>
#include <pthread.h>
#include <unistd.h>

void * run (void *) {
    std::cerr << "Thread 2 begin" << std::endl;
    sleep (20);
    std::cerr << "Thread 2 exiting" << std::endl;
    return NULL;
}

int main () {
    pthread_t thread;
    pthread_create (&thread, NULL, run, NULL);
    sleep (2);
    for (int i = 0; i < 10; ++i)
        std::cerr << "Main Thread" << std::endl;
    std::cerr << "Waiting on Thread 2" << std::endl;
    pthread_join (thread, NULL);
    return 0;
}

The output is

Thread 2 begin
Main Thread
Main Thread
Main Thread
Main Thread
Main Thread
Main Thread
Main Thread
Main Thread
Main Thread
Main Thread
Waiting on Thread 2
Thread 2 exiting

If the sleep suspended all threads then you would not see the output of the main thread there until after the spawned thread exited.

[nezachem]

Not true. See description here. Specifically, The sleep() function shall cause the calling thread to be suspended....

I can answer with another man page:
sleep() makes the current process sleep until seconds seconds have elapsed

The difference seems to be in conformance to different flavors (generations?) of posix-like standards. That makes me very nervous from the protability perspective.

[L7Sqr]

The difference seems to be in conformance to different flavors (generations?) of posix-like standards. That makes me very nervous from the protability perspective.

That, or the language is overloaded. For instance, on my machine, a thread is implemented with a call to clone. The man pages of clone state that the main use of clone is to implement threads, but all of the language speaks of processes.

In either case, I fully agree on the portability concern.

[Sergio_1]

HOw compilar?