To prevent the producer from run-away production, we require it to receive an “empty” message from the consumer before it can produce a full one.  We prime the system by producing N empty messages to start with.  After that, there are always nearly N messages total in the system, some empty, some full.

 

Pg. 122—another somewhat magic program, using the empty messages for flow control as outlined above.  Again, let’s show how the system objects are set up by the top-level thread and used by the worker threads.

 

/* various includes—see testmq.c, a simpler program than this sketch */

#define MSGSIZE sizeof(message)

#define N 10

mgd_t msgq_data, msgq_empties;

int main()

{

    struct mq_attr attr;

 

    attr.mq_maxmsg = N;  /* not effective as limit on producer */

    attr.mq_msgsize = MSGSIZE;

    attr.mq_flags   = 0;

 

    msgq_data = mq_open(“/mqdata”, O_CREAT|O_RDWR, 0666, &attr);

    msgq_empties = mq_open(“/mqempties, O_CREAT|O_RDWR , ...);

    create_thread(consumer, ...);  

    create_thread(producer, ...);

    getchar();

}

void producer(void)

{

    int item;

    message m;

 

    while (TRUE) {

        item = produce_item();

       /* wait for empty */

 mq_receive(msgq_empties, &message, MSGSIZE, 0);
 build_message(&m, item);

        mq_send(msgq_data, &m, MSGSIZE, 1 /*priority*/);

    }

}

void consumer(void)

{

    int item, i;

    message m;

  

    for (i=0;i<N;i++)

mq_send (msgq_empties, &m, MSGSIZE, 1); /* or put this in main */

while (TRUE) {

          mq_receive(msgq_data, &message, MSGSIZE, 0);/* wait for data*/

          item = extract(&m);

          mq_send(msgq_empties, &m, MSGSIZE, 1);   /* send empty */

          consume_item(item);

       }

}

 

Consider how this example could run:

main runs and initializes empty message queues “data” and “empties”.

Say producer runs first, blocks on receive from empties, because it has no messages.

Consumer runs, fills empties with N messages, then blocks on receive from message queue “data”.

When empties has any messages, producer is unblocked.

Producer runs, does up to N passes of its loop, eventually blocks on empty “empties”.

The “data” message queue has up to N messages in it.

 

We see that the “empties” message queue is ensuring that there are never more than N messages in the data message queue, i.e., enforcing the bounded buffer behavior required by classic producer-consumer.

 

Note that the data that is sent but not yet received is held in the message system.  This held data is analogous to the shared buffer we had with semaphores but in this case the storage is in the kernel, not in the user image.  Because the kernel has responsibility for the data in transit, the user program needs no explicit mutex.  The mutex in the semaphore code was guarding the access to the shared buffer in user memory.

 

Semaphores vs. Message Passing

 

Message passing can be done across systems, whereas semaphore systems offered by OSs are for synchronization of processes or threads all on one system.  On a single system (which may have multiple CPUs, and has a common memory system), semaphores and message queues have the same synchronization power.  Semaphores can by implemented by message queues plus shared memory, and vice versa.  Semaphores are often lighter-weight than message passing, partly since they can depend on being between local threads/processes.

 

Mutex by message passing:  put one message in a message queue.  receive it to obtain the mutex, send it back in to release the mutex.

Message passing by semaphores?  No way to move the data.

Message passing + shared memory can provide message passing within one system.

 

Actual message services

System V msgget, etc.: available on most UNIX systems.  Provides message passing between processes on one system.

Pipes, Network i/o: stream-oriented, but can subdivide stream into messages.

Win32: pipes, network i/o.  Also “mailslots” which can do broadcasts, but use datagrams and thus are unreliable at least between systems.

Something portable between Windows and UNIX?  Answer: TCP network i/o, works between processes on one machine as well as over the network.

 

Rest of IPC coverage in Tanenbaum:

 

pg. 123:barriers—can skip.

 

Dining philosophers:  has easy solution with mutex:  get mutex, pick up both forks, eat, release mutex.  But this allows only one eater at a time.  The challenge is to safely allow 2 eaters.

 

Readers and Writers: more realistic problem.  Allow N readers XOR 1 writer to each data item.  The solution uses two semaphores, one (db) to make sure the system is EITHER doing reading or writing, the other (mutex) to guard rc, the reader count.  Only the first reader does the down on the “db” mutex, and subsequent readers get blocked at the down on mutex, since the first reader still holds that until it gets db.  But that’s OK, since they need to block.  They get unblocked at the right time too. 

 

Sleeping barber—skip.

 Intro to hw3, multitasking tiny OS

Look at PEntry in handout:  see places for saved registers, p_status, etc.  The saved registers are saved at process-switch time.  A process gets to use the real CPU registers while it’s running, and when it’s switched, these values (the “CPU state”, or “CPU context”) are put away in its PEntry.  That way, when it gets the CPU back, its old register values can be put back, and the CPU is back to exactly where it was before, for this process.

 

The really mysterious thing here is the process switch itself, so let’s tackle that first.

 

Look at asmswtch.s in handout:  Here is the actual CPU-state switch.  It’s tricky to save and restore the CPU registers while using the CPU to do it, but that’s what’s going on here.  The ESP points to the whole stack (with kernel stack built on top of user stack), so the swap of ESP represents a swap of program-execution state.  EFLAGS is also swapped, with its important IF flag.

The system will have 3 user processes doing output via syscall write, finally syscall exit, plus a “process 0”, a kernel process.  The kernel will now have a scheduler that will allow one (or more) process(es) to be blocked while another runs. The scheduler is non-preemptive.  Same old 6-char output buffer, now shared between 3 processes.

 

Simple scheduler: looks for user process (1, 2, or 3) to run, if none, chooses process 0.

 

Process 0: loops, calling scheduler with IF=0, then setting IF=1 for a moment to allow interrupts.  Its only job is using system idle time (the CPU has to do something, even when the system has no work to do) and making sure the scheduler gets another process running as soon as possible.

 

Here is what we expect to happen with three user programs all doing more than 6 chars of output (the output buffer size) to the same TTY device. 

--One user process runs until it has filled the output buffer, then blocks (via call to scheduler, which looks for another process to run),

--another process runs, also blocks, because it wants to output to the same device, and the output queue for it is full

--a third runs, blocks, and no user processes are left to run,

--so process 0 is chosen to run.  As process 0 runs, output drains at interrupt level, and the user processes are unblocked by a call to the scheduler from the transmitter interrupt handler.  Process 0 calls the scheduler and the scheduler finds a process to run

--the chosen user process runs and refills the output buffer, then blocks.

--the other two user processes run in turn and find the full output buffer, and block again.

--process 0 runs again…

…over and over... until the output is done.

 

But we need to work up to this.

 

Look at PEntry in handout:  see places for saved registers, p_status, etc.  The saved registers are saved at process-switch time.  A process gets to use the real CPU registers while it’s running, and when it’s switched, these values (the “CPU state”, or “CPU context”) are put away in its PEntry.  That way, when it gets the CPU back, its old register values can be put back, and the CPU is back to exactly where it was before, for this process.

 

The really mysterious thing here is the process switch itself, so let’s look at it briefly.

 

Look at asmswtch.s in handout:  Here is the actual CPU-state switch.  It’s tricky to save and restore the CPU registers while using the CPU to do it, but that’s what’s going on here.  The ESP points to the whole stack (with kernel stack built on top of user stack), so the swap of ESP represents a swap of program-execution state.  EFLAGS is also swapped, with its important IF flag.