Objective: Send messages around the circle and listen to what happens to the message!
Rules: This game is intended for a large group. The group sits in a large circle. The originator whispers a short message into the ear of the person sitting to the right of them. The message is whispered once. The new messenger then whispers the message into the ear of the one to their right, and so on and so on. When the message reaches the originator, the message is announced out loud. Seldom does the message arrive in its original form. The originator may find out what message is being transmitted at various points around the circle through the persons in the circle.
The mq_open, sem_open, and shm_open functions are very much like the commonly used open function used for opening files. They return a descriptor that points to the opened object, which will have the corresponding type (i.e., mqd_t for message queues, sem_t for semaphores, and int for shared memory). The first argument of the *_open functions in POSIX is the name of the POSIX object, which can later be used by other processes or threads in order to open an existing POSIX object (very much like file names). The second argument is used to specify the flags used, which can take one of O_RDONLY, O_WRONLY or O_RDWR, and may be bitwise or'ed with O_CREAT, O_EXCL and O_NONBLOCK. The last three flags are used only while creating a new POSIX object. The third argument of the *_open functions (mode) is required only when opening a non-existing POSIX object. mode sets access rights: for example, 777 opens with read-write-execute rights to owner, group, and others. The fourth argument is different for every object.
The close functions (mq_close, sem_close, and shm_close) are very similar to the close function used for closing a file. As usual, the close functions decrement the reference counter of an object, which denotes the number of descriptors pointing to the object. All of the POSIX objects are named, and they are removed from the system by the unlink functions (mq_unlink, sem_unlink, and shm_unlink). Unlink has no effect until all references to that object have been closed.
Message passing is used to achieve the effect of whispering to your neighbor in the telephone game. Each thread has its individual message queue. Every message queue is set to hold only one message, and the maximum message size is set to 200 characters. Message queues are specified as "blocking," so that a thread blocks at the mq_receive call on its message queue. All of these settings are specified in the attr argument of mq_open.
Both mq_receive and mq_send take a message queue descriptor (of type mqd_t) as their first argument. Their second argument is of type character pointer and specifies where message will be copied. The third argument gives the size of the message that will be read (or written). The last argument of these functions sets the priority of the message to be read, which is 0 in this case.
We also maintain another message queue, the detector message queue. The originator uses this queue to receive messages from other threads, and the other threads use this queue to send the messages that they "gossip" to their neighbors to the originator. Since the originator should receive messages from every other thread in the circle, and the detector message queue is shared by all the threads, the queue can be set to hold multiple messages. In our case, this could is NUMOFTHREADS-1. When non-originator threads send their "gossip" messages to the detector queue, they set the priority of the message to a function of the thread id, so that the originator can identify which thread sent a particular message.
You are required to complete the telephone1.c so that it will follow the above specifications. You are given the code for all threads other than the originator, and you are required to complete the code for the originator. Additionally, you need to add code to manipulate the detector message queue, so that the originator can detect messages each thread passes to its neighbor. If you run the given code as is, you will observe that all threads hang. The ones that are not the originator are suspended on the mq_receive call in play_game. Threads are differentiated by their ids. The id of the originator is 0, and the id of the last thread is NUMOFTHREADS-1.
uncompress lab4-src.tar.Z2. Change directory to lab4-src and examine the contents of the file telephone1.c:
tar -xvf lab4-src.tar
cd lab4-src
3. Build the executables:
make4. Run the program telephone1 to see what happens.
telephone1 "Hello."
4. Now modify the play_game function in telephone1.c so that the originator will do its job. In addition, extend play_game, so that the originator can print the detector message queue contents. A non-originator thread should now send its modified messages to the detector queue (in addition to passing the modified message to the message queue of its neighbor, which is done by the code you are given). When you are done, the output of your program (with argument "Hello.") will look something like this:
Starting thread 1
Starting thread 2
Starting thread 0
Starting thread 3
Originator detected: Hello.Oo from thread 1
Originator detected: Hello.Oop from thread 2
Originator detected: Hello.OopS from thread 3
Originator sent: Hello.O
Originator received: Hello.OopS
"OopS" is appended to the original message you had input on the command line (each letter should have been appended by a separate thread).
You must precisely follow the format of printing given here, since grading is automated. Any other or "similar" output will NOT be accepted. In addition, the messages detected by the originator must be printed in the increasing order of their thread ids.
In this part, we will also play the telephone game, but using different mechanisms. Unlike Part 1, now we have multiple processes, which use a shared memory space in order to exchange the message. The processes must use semaphores to synchronize shared memory access and to wait for each other. You can think of this version of the game as if there is only one telephone and all processes use it to exchange the message. Every process is created separately, by starting the program execution from the command line several times with different ids that are passed to each process as a command line argument. The allowed values for the id argument are 0 for the originator, and 1, 2.., (NUMOFPROCESSES-1) for the rest of the processes. The originator takes a second command line argument, which is the original message (e.g., at your command line prompt, type telephone2 0 "Hello World"). Other processes only take the id argument (e.g., telephone2 2). Use SEVERAL xterm windows to run the different processes, or you can run them in the BACKGROUND by appending an ampersand to your command line.
The program is designed such that every
process performs different tasks according to these ids. Message
exchange rules are same as Part 1. All processes other than the
originator read the message, modify it, and write it back. Then, they
signal the next process (with message queues, synchronization was built-in, but in this program, semaphores are used for synchronization).
The originator process first opens
and initializes shared resources, and then starts the game by writing its
message to shared memory. The originator then signals the next process, and starts
waiting for the last process to wake it up so it can finally print the message.
The size of the shared memory object is set by the ftruncate call, which takes the descriptor of the shared memory object and the size as arguments. The shared memory is mapped to the address space of the process by the mmap call. After mmap is called, anything done on this memory address will directly effect the mapped object. The msync function is called in order to make sure that the contents of the memory, which the process is accessing, are synchronized with the real shared memory object kept in kernel space.
Unlike the other processes, the originator opens all the semaphores with creation flags and values. It sets the initial value of the counter of semaphores to 0, using the last argument to sem_open. Setting the starting value of a semaphore to 0 means that a sem_wait call on this semaphore will block the caller until another process performs a sem_post on this semaphore. The names of the semaphores are also kept in the shared memory space, so that every process can learn which name is given to the semaphore assigned to it by the originator. Processes other than the originator will use this name to open that semaphore, with sem_open and wait on it with sem_wait. These processes must also read their neighbor's semaphore's name, in order to signal the neighbor using the sem_post function.
All processes must call sem_close for any semaphore they opened, in order to decrement the reference count on the semaphore object. The originator performs the destruction of semaphores by calling sem_unlink on their names. Finally, all processes unmap the mapped memory before exiting.
You are required to complete the code for the processes that are not the originator. When you run the originator now, it will print the message that it is writing to shared memory, and signal process 1. Then, it hangs on the call to sem_wait for its semaphore. The other processes perform their initializations, but they return without playing the game. As you will observe when you run the given code, nobody signals the originator.
2. Run the program telephone2 for process ids 0, then 1, 2, and 3, to see what happens.
3. Now modify the specified part of the main function in telephone2.c so that processes other than the originator will modify (i.e., add the character from "to_append" that corresponds to its id) and pass the message. When you are done, if your program works correctly, the final message should have "OopS" appended to the original message (each letter should have been appended by a separate process).
This lab is due on Sunday, October 24th, 2004, by 11:59 PM. To submit: