/* file: snake:/home/csi/graphx/msgfuncs.c date: 1/19/2010 */ /*---------------------------------------------------------- by: Gary D. Knott, garyknott@gmail.com Civilized Software Inc. 12109 Heritage park Circle Silver Spring MD 20906 www.civilized.com */ /*---------------------------------------------------------- This file, msgfuncs.c, contains functions for interprocess communication through a Unix message queue based on the applicable Linux message-queue service routines: msgget, msgctl, msgsnd, and msgrcv. Because of the use of MSG_EXCEPT, these functions only apply to Linux. In the discussion following, these functions are used in the presentation of a solution to the general resource-sharing problem for cooperating processes. A Unix message queue is just a queue maintained by the operating system wherein a process can 'post' a message (i.e. an arbitrary block of bytes) and another process (or even the same process) can retrieve that message from the queue. Posting messages and retrieving messages are done by calls to operating-system service routines. The routines we define are: export void setupmsgqueue(int32 *qid, int32 key, int16 csw) export int16 closemsgqueue(int32 qid) export int16 sendmessage(int32 qid, MSGBUF *m) export int16 getmessage(int32 qid, MSGBUF *b, int32 mtype, int16 waitsw) export int16 sendwithack(int32 qid, MSGBUF *m, int32 ackmtypev) export int16 getwithack(int32 qid, MSGBUF *m, int32 ackmtypev) --------------------------- In order to use message queue interprocess communication within a C program, the includes: #include (actually, we don't seem to need this.) #include #include (i.e. include /usr/include/sys/msg.h) must be present. In order to construct a C program using the routines defined here, you can add a collection of functions, plus a main function, in a copy of this file, and compile and link the modified file. Alternately, you can build another file or files holding your functions, and provide the various declarations needed to define the 'symbols' (including the functions) of this file in your file as "externs", and then compile your file and this file, and then link them together. ----------------- The LINUX Message-Queue Service Routines. To ask the operating system to create a message queue (or to "attach" to an existing queue) that can be used for processes to send and receive messages among themselves, execute: qid = msgget(key,flag). The argument 'key' is of type key_t (an int32). It is an identifier value that, hopefully, is unique for the processes wanting to communicate with this queue. The msgget function returns a queue identifier value (an int32) which is associated with the value 'key' (but is generally not equal to key). [There is a system function, called as ftok(".",c) where c is a byte, that returns a key-value, but it seems to be largely unnecessary. Using key=0 ensures a unique queue is specified, (but note we will need to communicate the returned queue-identifier value to our "partner" processes somehow.) Often, using the process id number of the parent process that 'starts' the other processes as the queue key is a sufficient means to ensure uniqueness.] The argument 'flag' is an int32. To create a new message queue or attach to an existing queue, it is generally suitable to use flag=(IPC_CREAT|0660). [0660 is 660 (octal); it is the "access permission" for the queue. 660 denotes RW access for the same user or same group as the creator. If desired, you may either tighten or relax this access code.] (Note, there are various "constants" like IPC_CREAT that we refer to herein; these capital letter names are "macros" defined in various C-system header files; they are all just names of various integer values that we could determine if we searched the header files.) If the queue associated with the value 'key' already exists, its identifier will be returned, if not, a new queue will be created and its identifer will be returned. This option is convenient when you are uncertain if your process is the first to attempt to acquire the queue. Using 0 as the value of key ensures that a new queue will be created. msgget() returns the queue identifier, here called qid, which is an int32, if it succeeds. The value -1 is returned if it fails (and the global variable errno is set to indicate the exact error). Note the resulting value qid must be communicated via some means such as in a file or on the 'command line', or the identifying 'key' must be known or computable, for every process or thread that wishes to use the queue. In order to ensure we are creating a queue rather than attaching to an existing queue, use flag = (IPC_CREAT|IPC_EXCL|0660). Then, if the queue already exists, msgget returns -1, and the extern int errno is set to EEXIST. In order to ensure we are "attaching to" a existing queue rather than creating a new queue, use flag = 0. Then, if the queue does not exist, msgget returns -1, and the extern int errno is set to ENOENT; in older Linux systems, if the queue existed, but was marked for deletion, msgget returned -1, and the extern int errno was set to EIDRM. One process can be responsible for creating the message queue and other processes can then obtain the message queue identifier by calling msgget(key,0). Note 0660 is not included in the call argument. The key value can be hard-coded, or can be passed in shared memory, or on the command line, or via a file. --------------------------------------------------------- To close any communications and delete the message queue, call: result = msgctl(qid,IPC_RMID,(struct msqid_ds *)NULL). qid is the queue identifier value (an int32). msgctl() returns -1 if it fails; otherwise it returns 0. If any processes are waiting on the message queue (for a message, if reading with msgrcv, or for space in the queue, if writing with msgsnd,) they will be "restarted" with -1 returned to them from their msgrcv or msgsnd call and errno will be set to EIDRM. Note: If any processes are waiting on the message queue, and a signal (i.e. an interrupt) is sent to the waiting process, the return from our `signal-handler routine will act to "restart" the waiting processes. For each blocked process, the return will jump to just after the blocking msgsnd or msgrcv call with -1 returned as the msgsnd or msgrcv value and errno set to EINTR. -------------------------------------------------------- To send a message "to" the message queue identified by the integer qid, call: result = msgsnd(qid,&buf,msgsize,flag); qid is an int32. It is the number identifying the message queue. buf is putatively a struct. It is actually the address of a memory area where the message is located. Its first four bytes are an int32 that holds the message-type (an arbitrary integer of our choice). A char array of msgsize bytes follows the message-type integer. These remaining bytes constitute the message. buf may be defined as: struct msgbuf {int32 mtype; char mtext[1];} buf; msgsize is the total size in bytes of the fixed-length message array field in the struct buf being "sent". (This does not count the four bytes of the message-type.) flag is an int32. If flag==IPC_NOWAIT and the message queue is full, then msgsnd() will return -1. If flag==0, msgsnd() will block until the message can be queued (It is unlikely that msgsnd will ever need to wait.) In any case, when the message is sucessfully queued, msgsnd() will return 0. If the queue does not exist, msgsnd() will return -1 with errno set to EINVAL, regardless of the value of flag. (other possible (but extremely-rare) error values are EAGAIN, ENOMEM, EACCES, and EFAULT. See Gray or the Linux man-pages.) If the queue is destroyed while msgsnd is waiting, msgsnd() will return -1 with errno set to EIDRM, regardless of the value of flag. (Also, if a signal (i.e. an interrupt) is sent as manifested by entering a signal-handler routine, when the signal-handler returns, msgsnd will be "coerced" to return with a value of -1, and errno will be set to EINTR. --------------------------------------------------------- To read a message from the message queue identified by the integer qid, call: actsize = msgrcv(qid,&buf,msgsize,msgtype,flag); qid is an int32. It is the number identifying the message queue. buf is a msgbuf struct. It is a memory area where the message being read is placed. Its first four bytes is an int32 that holds the message-type (an arbitrary integer of our choice). A char array of msgsize bytes follows the message-type int32. These remaining bytes constitute the message. As a template, buf may be defined as: struct msgbuf {long int mtype; char mtext[1];} buf; msgsize is the total size in bytes of the message-text field in buf. This is the space available for use. msgtype is an int32. If msgtype==0, then we are asking to read the next message of any message-type value. If msgtype>0, we are asking to read the next message whose message-type value is msgtype. If msgtype<0, we are asking to read the first message whose message-type value is the least value <= abs(msgtype). Specifying flag as the special value MSG_EXCEPT will tell msgrcv to get the first message whose message-type is NOT equal to msgtype, when msgtype >0 (If msgtype <=0, then MSG_EXCEPT has no meaning.) This feature is useful to prevent a msgrvc call from getting an acknowlegement message that is intended for another msgrcv, probably in a different process. This option is only available in Linux. Generally we will want to send messages of one message-type value and receive messages identified by a different message-type value. (Otherwise, we might end-up receiving messages that we send when we do not wish to do so.) flag is an int32. If flag==IPC_NOWAIT, then msgrcv() will not block, and if there is no message, msgrcv() returns -1. If flag==0, then we will block until there is a message to be obtained. In either case, if there is a message, msgrcv() returns the actual size in bytes of the message-text (i.e. the number of bytes in the char array of the struct, buf, as specified by the argument msgsize, given in the msgsnd call that enqueued the message.) If the message-text is longer than msgsize, the received message string will be truncated. Also, if the message queue does not exist, then msgrcv() will return -1. If the queue is destroyed while msgrcv is waiting, msgrcv() will return -1 with errno set to EIDRM, regardless of the value of flag. (Also, if a signal (i.e. an interrupt) is sent as manifested by entering a signal-handler routine, when the signal-handler returns, msgrcv() will be coerced to return with a value of -1, and errno set to EINTR. ----------------------------------------------------------- This form of queue-based messaging is not the same as pure "from-to" messaging as provided with TCP/IP sockets. With proper choices of message-types and content, one can achieve (unenforced) "from-to" messaging, but we are not confined to that paradigm. Also, of course, these queue-based routines only apply within a single computer. If we kept a message queue on one computer and ran suitable message-service software there, we could use TCP/IP messages to construct a network form of queue-based messaging, albeit centralized rather than distributed, although we could keep each distinct message queue on a distinct computer. ----------------------------------------------------------- There is a linux command: ipcs that reports all the operating- system-maintained interprocess communication data objects. (There is another linux command: ipcrm that 'removes' such data objects.) We note that there are a bunch of 'shared memory' 'objects' that we did not establish. These belong to Gnome. *----------------------------------------------------------*/ /* Now we may define our derived message-queue-based interprocess communication functions using the Linux-supplied routines described above. */ /* All our prosaic C header-files are included in gx.h */ #include "gx.h" /* "..." looks in . and our explicitly-specified directories. <...> looks in /usr/include/ */ #include #include #include #include #include /* The message queue struct template, msgbuf, and the message queue operations are defined in this header file.*/ #include /* Syntactic Sugar macros */ #define int32 int #define int16 short int #define Template #define import extern #define export #define private static #define AND && #define OR || /* The constant MSG_EXCEPT is found in /usr/include/bits/msq.h, which is included by . In order to have it defined, the macro __USE_GNU must be defined. But, we will just define MSG_EXCEPT ourselves!!! This constant only has meaning in Linux.*/ #define MSG_EXCEPT 020000 import int errno; /*This is set by msgget, msgsnd, msgrcv, and msgctl.*/ /* The integer qid is the id of the message queue created and opened herein. The client process sends messages to this parent process. Remember int = int32, we need to use 'int' to match the arg-types in function calls.*/ private int qid; /* The struct template: struct msgbuf {long int mtype; char mtext[1];} is declared in msg.h within an #ifdef on __USE_GNU. The mtext[1] is just a place-holder for the actual message-text area. We do not want the macro __USE_GNU to be defined in our code. Thus we define our own similar struct template ourselves.*/ #define MSGBUF struct msgbuf Template MSGBUF {long int mtype; char mtext[1];}; /* Define the addresses of message structs mb1 and mba. These addresses will be set to addresses of 32-byte areas to be used as message structs containing a 4-byte type-field (mtype) and a message buffer field (mtext[28]). This allocation is done in setupmsgqueue().*/ export MSGBUF *mb1; private MSGBUF *mba; /*============================================================*/ export void setupmsgqueue(int32 *qida, int32 key, int16 csw) /*--------------------------------------------------------- Create or "attach to" a linux message queue to be used for inter- or intra-process or thread communication. The argument 'key' is the "external" identifier of this queue (key=0, ensures a new queue with a new unique qid value is specified.) Return the int32 identifier of this message queue in *qida (i.e. The address of qid is to be supplied as the first argument.) If this function fails, it returns -1. If csw=0, we are asked to create a new queue; if the queue already exists, or cannot be created, -1 is returned in *qida. If csw=1, we are asked to "attach to" the existing queue specified by the "key" value given in key; if the queue does not exist, or cannot be attached to, -1 is returned in *qida *---------------------------------------------------------*/ {int flag; char mbt[32]; /* IPC_EXCL means we want a "new" queue. 660 is the 'permission' bits for the new to-be-created message queue. */ if (csw == 0) flag = IPC_CREAT|IPC_EXCL|0660; else flag = 0; /* Create or attach to a message queue for receiving and sending messages to the child process. 'key' is an arbitrary number to specify the desired queue; it is hopefully, appropriately unique. -1 is returned if the creation failed.*/ *qida = msgget(key,flag); /* If *qida = -1 and flag !=0, then we did not create a NEW queue (and errno will tell us why.) If *qida = -1 and flag=0, then we did not attach to an existing queue with key-value 'key' (and errno will tell us why. The most common reason is that a previous execution has failed to delete the queue and we are re-using the same 'key' to identify the queue.) */ if ((*qida == -1) AND (errno == EEXIST)) {printf("ipc queue exists. The previous execution EXIT was improper.\n"); /* Empty the existing queue and reuse it. This is not a perfect solution, especially if a process of another execution that uses this queue is around.*/ *qida = msgget(key,0); while (msgrcv(*qida,(MSGBUF*)mbt,28,0,IPC_NOWAIT) != -1); } if (*qida == -1) return; /*Let's see optimization work here! */ /* Allocate some message buffers. calloc() returns 0-filled memory. (This should probably be done more flexibly in a separate routine.) */ mb1 = calloc(32,1); mba = calloc(32,1); } /*============================================================*/ export int16 closemsgqueue(int32 qid) /*--------------------------------------------------------- Close the linux message queue, qid, used for interprocess communication. This function returns 0 if it succeeds, and returns -1 if it fails. If any processes are waiting on the message queue (for a message, if reading with msgrcv, and for space in the queue, if writing with msgsnd,) they will be "restarted" with -1 returned from the msgrcv or msgsnd and errno set to EIDRM. [Also note if any processes are waiting on the message queue, and a signal (i.e. an interrupt) is sent, the return from the signal-handler routine will act to "restart" the waiting process just after the msgsnd or msgrcv call with -1 returned and errno set to EINTR.] *---------------------------------------------------------*/ {int16 r; /* Close the message queue identified by qid.*/ r = msgctl(qid,IPC_RMID,(struct msqid_ds *)NULL); /* Discard the message buffers we allocated in setupmsgqueue(). (This should probably be done in a separate routine paired with an allocation routine.) */ free(mb1); free(mba); return(r); } /*============================================================*/ export int16 sendmessage(int32 qid,MSGBUF *mb1) /*--------------------------------------------------------- sendmessage() calls msgsnd() to place the msgbuf struct argument pointed-to by mb1 in the qid message queue and then returns 0. We return -1 if we have an error. The message-type of this message should be generally a value to indicate that it is being sent from this process. This message-type value should probably be distinct from the message-type values used in the messages sent from other processes! *---------------------------------------------------------*/ {int m; m = msgsnd(qid,mb1,28,IPC_NOWAIT); /* msgsnd() returns -1 if the queue is full, or if the queue does not exist! Note, if we wish to wait until space is available in the queue for a message, we could supply the argument 0 in place of IPC_NOWAIT, however we do not expect the queue to ever be full!! */ if (m == -1) {printf("msgfuncs: sendmessage: message queue is gone or full\n"); return(-1); /* Perhaps we should check if someone has deleted the message queue. - a signal could catch us in just the right place to generate an error return, even though we said IPC_NOWAIT!*/ } /* At this point, m = 0, indicating a successful send.*/ return(0); } /*===================================================*/ export int16 getmessage(int32 qid,MSGBUF *mb1, int32 mtypev,int16 waitsw) /*--------------------------------------------------- getmessage() gets a message in the message queue qid that has message-type mtypev. (If mtypev = 0, then we will get a message of ANY message-type, and if waitsw&MSG_EXCEPT != 0, we will get the first message whose message-type is NOT mtypev.) When this message is received, this subroutine will have obtained the message content in the msgbuf struct *mb1 and it then returns the number of chars in the mtext area that hold the message text. If waitsw&IPC_NOWAIT=0, then we will wait for a message; otherwise we will not wait, and if there is no message, -1 will be returned. Thus, to wait, set the waitsw argument to 0, and to not wait, set the waitsw argument to IPC_NOWAIT. *--------------------------------------------------*/ {int cmsg; int32 mt; char w[12]; if (waitsw & MSG_EXCEPT) mt = -mtypev; else mt = mtypev; /* msgrcv() reads a message of message-type mtypev (which is the type-value of the message sent to us that we desire to recieve. (mtypev = 0 means get a message with any message-type value. The received message is put into the buffer mb1->mtext of at most 28 bytes. The int32 mb1->mtype is set to the actual message type value. The actual number of bytes of the message is returned in cmsg. If the argument, waitsw, is 0, it means we will wait until a message is returned; otherwise, if we receive a message, cmsg will be set to its length in bytes, and if we do not receive a message, cmsg will be set to -1! When the qid queue does not exist or is deleted while we are waiting, then even with waitsw being on, the value -1 is returned from msgrcv(). Thus waiting is ignored when an error is detected. We also get -1 returned if a signal, such as ^C, is sent while we are waiting. That is, if we are waiting in getmessage(), a ^C will "stop" the waiting, and the return in sigint_handler() will continue after the msgrcv call; the global integer errno will be set to EINTR to indicate this. */ readmsg: cmsg = msgrcv(qid,mb1,28,mtypev,waitsw); /* When waitsw =IPC_NOWAIT, we are not to wait for a message, and cmsg = -1 if there was no message. (If cmsg = -1 and errno = EIDRM there is no queue identified by qid. If cmsg = -1 and errno = EINTR, ^C was typed to interrupt us while we were waiting for a message.) Otherwise cmsg is the number of chars in the message text. */ if (cmsg == -1) {/* Look at errno to see what happened. */ if (errno == EINTR) goto readmsg; if (errno == 0) return(cmsg); exit(2); } return(cmsg); } /*============================================================*/ export int16 sendwithack(int32 qid,MSGBUF *mb1, int32 ackmtypev) /*--------------------------------------------------------- sendwithack() sends the message text given in mb1 with the associated message-type value given there to our qid message queue. Then sendwithack() calls getmessage() to receive an acknowledgement. The acknowledgement is to have message-type value ackmtypev. Upon receiving the acknowledgement, we return 0. If we have an error, we return -1. The message-type of the message to be sent should be set in mb1->mtype to indicate that it is being sent from this process. This message-type value should be distinct from the message-type values used in the messages sent from the client process! The acknowledging message from the partner process is to have message-type ackmtypev. *---------------------------------------------------------*/ {int c,m; /* We will check and disallow the situation where mb1->mtype = ackmtypev, otherwise, we could and probably would receive our own message below!!. */ if (mb1->mtype == ackmtypev) {printf("msgfuncs:sendmessage: sending an ack msg as a non-ack msg.\n"); return(-1);; } m = sendmessage(qid,mb1); /* sendmessage queues the message mb1 in the qid message queue and returns with the value 0 for success and -1 for failure. */ if (m == -1) {printf("msgfuncs:sendmessage: msg queue is full or non-existent\n"); return(-1);; } /* At this point, m = 0, indicating a successful send. Now read an acknowledgement message, and don't return until we get it.*/ /* Retrieve an acknowledgement message sent by getwithack() via the qid message queue. This call waits for the message. The actual message will be in mba->mtext[0:27] and its actual length will be in c. 0 for the last arg means wait until a message is received.*/ c = getmessage(qid,mba,ackmtypev,0); /* At this point, we have received a message of type ackmtypev (or any type, if ackmtypev =0.)*/ return(0); } /*===============================================================*/ export int16 getwithack(int32 qid,MSGBUF *m,int32 gmtypev,int32 ackmtypev) /*--------------------------------------------------------- getwithack() gets a message with message-type value gmtypev from the qid message queue (waiting if necessary) and then calls sendmessage() to send an acknowledgement. The acknowledgement has message-type value ackmtypev. (If gmtypev=0, we are requesting a message of any type, except ackmtypev!! We must dissallow ackmtypev messages, because otherwise the calling program might loop around back into this function and we would incorrectly read our own acknowledgment message!) After sending the acknowledgement, we return 0, or -1 if we had an error. *---------------------------------------------------------*/ {int c,k,flag; /* Get a message of type gmtypev in the buffer m (gmtypev = 0 means get the first message of any message-type (except ackmtypev! - this is done by passing flag = MSG_EXCEPT with the message-type arg gmtypev reset to ackmtypev.) We wait until a message is received. (Leaving IPC_NOWAIT out of flag means wait until the message is received.) c is the actual message length of the obtained message-text (maximum 28 bytes for this file, due to our message buffer allocations above.) */ if (gmtypev == 0) {flag=MSG_EXCEPT; gmtypev=ackmtypev;} else flag=0; c = getmessage(qid,m,gmtypev,flag); /* At this point, c >= 0, indicating a successful get. Now send an acknowledgement message with message-type ackmtypev. This send is only to be received by send withack! Note sendmessage just enqueues the message and returns with 0 for success and -1 for failure. */ mba->mtype = ackmtypev; k = sendmessage(qid,mba); if (k == -1) {printf("msgfuncs: getwithack: message queue is gone or full\n"); return(-1); } /* Return the number of bytes of the message we received.*/ return(c); } #ifdef DISCUSSION The following material is a discussion with examples of the use of the above routines. Further discussion of these operating system facilities and much more is found in "Interprocess Communications in Linux" by John Shapley Gray (2003). We can use these inter-process communication functions for synchronization and for resource-use control. For example, in our program, MLAB, we spawn a separate process to watch for XWindows expose events, and repaint the exposed part of our picture from a pixmap, when such events are read. (We do this because our main program may be busy with a computation, and we want time-sharing (time-multplexing) to provide the appropriate responsiveness effect.) When the user resizes our picture, we need to stop this "expose-server" process until we handle the resizing by redrawing, and creating a new "backing-store" pixmap with the new size. Then we tell our expose-server the ID of the new pixmap and ask it to restart. [rant: XWindows is supposed to provide automatic backing-store and presumably handle expose events roughly like we do, but I can't find-out how to ask Xwindows to do this; it depends to some extent on the so-called Window manager program of which there are many, and all without easily acessible documentation. One more complaint: it is very hard to know when a resizing action starts (mouse-down in the border) and when it ends (matching mouse-up); we do this with absurdly complex heuristics that we had to painfully determine by experiments. There should be events corresponding to the mouse-down and mouse-up actions that begin and end a resizing action.] Our main program contains the following two routines. /*=================================================================*/ export void stopgxserver(int j) /*------------------------------------------------------------------ Send a message to gxserver to tell it to stop handling expose events until we restart it via another message sent by restartgxserver(). We do this by first sending an XEvent Expose 'message' with the send_event field = True. This will be caught by gxserver when it gets an X-event. This is a signal to gxserver to go check for a message in the qid message queue. After we send the X-event Expose 'message', we then call sendwithack() to send the stop message (which has message-type 1) to gxserver (and we wait until sendwithack() receives an acknowledgement). -----------------------------------------------------------------*/ {int16 ec; XEvent event; /* If gxserver is already stopped, then we just return. Actually this should never be the case.*/ if (gxserverstopped EQ 1) return; /* We will send a stop message(type 1) to gxserver. Before we send the message, we notify gxserver about it by sending it a 'fake' expose event, so it can go receive the message.*/ /* Load the event-struct event to represent a 'fake' expose event and send it to be received by XNextEvent() in gxserver. This is so gxserver will exit from XNextEvent() if gxserver was waiting there, and can handle receiving a message sent via sendwithack(). (gxserver detects that it is seeing a fake signaling event by testing for event.xexpose.send_event = True.) (This XSendEvent ability to send our own "X-events" is helpful - otherwise we would need to use a signal (an interrupt) - but it is kind of crippled because the X-server replaces most of the event structure elements with what it deems to be appropriate, so we can't stick whatever we wish in them.*/ event.xexpose.type = Expose; event.xexpose.send_event = True; event.xexpose.display = display; event.xexpose.window = gxwin; event.xexpose.x = 0; event.xexpose.y = 0; event.xexpose.width = 1; event.xexpose.height = 1; event.xexpose.count = 0x0000ffff; /* Send the fake expose event to notify gxserver that a message is to be received.*/ XSendEvent(display,gxwin,False,ExposureMask,&event); /* Force this event on to the XServer event queue.*/ XSync(display,False); /* Now send the promised type-1 stop-message to gxserver. The message-type of the acknowledgment message is to be 4.*/ mb1->mtype = 1; /* Send a stop message (message-type = 1).*/ ec = sendwithack(qid,mb1,4); if (ec EQ -1) gxerror("stopgxserver: sendwithack() failed.\n"); gxserverstopped = 1;/* Remember that gxserver has been stopped.*/ } /*==================================================================*/ export void restartgxserver(int j) /*------------------------------------------------------------------- This routine sends a type-3 message to gxserver to tell it to restart with a new pixmap. Since this routine should never be called unless stopgxserver() has been previously called, we can expect that gxserver is waiting for a message to arrive; it is not waiting for an X-event so we do not need to pre-notify it as we did in stopgxserver(). We call sendwithack() to send a message of message-type 3 with the new pixmap id in the first four bytes of the message. (Note that we wait until sendwithack() receives an acknowledgement.) ------------------------------------------------------------------*/ {int16 ec; XEvent event; /* First we do an XSync() to enqueue any X-events in the X event queue that are pending being enqueued for gxserver.*/ XSync(display,False); /* stronger than XFlush().*/ /* If gxserver is already stopped, then we just return. Actually this should never be the case.*/ if (gxserverstopped != 1) return; /* We will send the new pixmap id to gxserver as the first 4 bytes in a message with message-type 3. The message-type of the acknowledgement message is to be 4.*/ mb1->mtype = 3; *(int32 *)(mb1->mtext) = (int32)pixmap; ec = sendwithack(qid,mb1,4); if (ec EQ -1) gxerror("restartgxserver: sendwithack() failed.\n"); gxserverstopped = 0;/* Remember that gxserver is now running.*/ } We use these routines in our main program to control the gxserver process. Note we use sendwithack in order to make sure that gxserver is cognizant of our wishes before we proceed. The gxserver process calls getwithack() to receive messages from us, and it calls XNextEvent() to get X-events. There is another common situation where these process intercommunication procedures are helpful. Suppose we want to request a process to take a certain action (like enable receiving certain X-events for itself) while we wait until we are notified back that this action is complete (then we can, for example, safely do things that cause such X-events to be created.) We can do this as follows. ec = sendwithack(qid,mb1,4); where mb1 contains the action request. Our service process contains the following code. c = getmessage(qid,mb,0,0) /* wait for a message of any type. */; [Check that mb contains an action request, and if so, do the action.] /* notify the requester that the action is done. */ mb->mtype = 4; c = sendmessage(qid,mb); ----------------------------------------------------- Suppose we have two programs (or threads) that both need to use a 'resource' such as a data-structure or a non-re-entrant subroutine that can be used by only one process at a time. (Such a resource is called an "exclusive resource". In case the resource is a subroutine or a section of code that changes an exclusive data-structure, the resource is often called a "critical section".) We can program each process as follows. process 1: void resuse(void) {static int gotres = 1; if (gotres == 0) {getmessage(qid,b,1,0); gotres = 1;} useit: [ use the resource. ]; b->mtype = 2; sendmessage(qid,b); gotres = 0; return; } process 2: void resuse(void) {static int gotres = 0; if (gotres == 0) {getmessage(qid,b,2,0); gotres = 1;} useit: [ use the resource. ]; b->mtype = 1; sendmessage(qid,b); gotres = 0; return; } Note if we have threads instead of separately-compiled processes, then we need to use separate function names like resuse1 and resuse2. Also note that the message queue id, qid, and the message buffer b need to be established in each process before these routines are called. Finally, remember that 0 as the fourth argument of getmessage is a request to wait until the message is received before returning. Essentially all we do is give the resource initially to process 1, who, after using it, sends a message of type 2 to relinquish the resource to process 2; process 2, in turn, gets the message granting permission to use the resource, uses it, and sends a message of type 1 to relinquish the resource back to process 1. This protocol forces the two processes to take turns. We can avoid this with the following modification. (Do you see the difference?) process 1: void resuse(void) {static int gotres = 1; if (gotres == 0) {getmessage(qid,b,1,0); gotres = 1;} useit: [ use the resource. ]; b->mtype = 1; sendmessage(qid,b); gotres = 0; return; } process 2: void resuse(void) {static int gotres = 0; if (gotres == 0) {getmessage(qid,b,1,0); gotres = 1;} useit: [ use the resource. ]; b->mtype = 1; sendmessage(qid,b); gotres = 0; return; } These routines work if the msgsnd function checks for the existence of processes waiting for a message matching the message-type being sent and 'assigns' the message to the process that has been waiting the longest. If, however, processes waiting for a message are served out-of-turn, then using the routines above may allow "starvation" to occur, wherein, for example, process 1 gets the resource, sends a message to relinquish the resource, immediately recalls resuse and gets the resource again, and so on, while process 2 waits because its waiting time "priority" is not recognized. This could happen if, instead of having the message queue dispatcher code keep waiting processes in an ordered list for service, the scheduler essentially decides which waiting process next checks for a message by the action of awakening it. We can avoid starvation, even in the presence of an arbitrary service protocol, by having each process post a "reservation" request message requesting use of the resource if it does not "possess" the resource. This approach also deals with the situation of an arbitrary number of processes using the resource. This idea can be programmed as follows, for process 1, process 2, ..., etc.. process j: int resuse(int s) /*------------------------------------------------------------ If s = -1, return 1 if we "possess" the resource. Otherwise, return 0 to indicate we do not currently have the resource. If s = 1, use the resource, waiting if necessary to obtain it (and then relinquish it if another process is requesting it.) If s = 0, relinquish the resource if we possess it. ------------------------------------------------------------*/ {static int gotres = (j == 1); int p; if (s == -1) {if (gotres == 1) return(1); else return(0);} if (s == 0) {if (gotres == 1) goto giveres; else return(0);} if (gotres == 0) /*If we do not have the resource, get it.*/ {/*Read "grant for j" message.*/ nc = getmessage(qid,b,2+j,IPC_NOWAIT); if (nc == -1) {b->mtype=1; *(int *)mtext = j; sendmesssage(qid,b); /*Send request.*/ /*Wait for "grant for j" message.*/ readmessage(qid,b,2+j,0); } gotres = 1; } useit: [ use the resource. ]; giveres: /* Relinquish the resource if it is requested.*/ nc = readmessage(qid,b,1,IPC_NOWAIT); /* Check for a request.*/ if (nc == -1) return(1); /* There is no request.*/ p = *(int *)mtext; /*Set p = the requesting process number.*/ b->mtype = 2+p; sendmessage(qid,b); /*Relinquish the resource to process p.*/ gotres = 0; return(0); } We use the global queue id, qid, and the global message buffer: struct msgbuf {long int mtype; char mtext[4];} b; Each process needs to call resuse(1) when it wants to use the resource, and needs to call resuse(0) from time-to-time if the resource is not frequently used; this is because calling resuse is the only means to relinquish the resource. This scheme works because messages of the same message-type are (conceptually) kept in a first-in-first-out queue; thus when a process sends a request message, that message will eventually work its way to the head of the list of type-1 messages, and hence the requesting process will eventually be granted the resource. Note this scheme requires "cooperating" processes acting to release the resource. No process may keep the resource indefinitely. If we do not have cooperating processes, sharing a resource becomes harder; generally we need an intermediary process that uses the resource on behalf of each process and ensures that the resource is not held indefinitely. This is part of the role of an operating system. Note by calling resuse(-1) we can ask if we have the resource. With some further programming, we could add an option to have resuse try to get the resource if it does not have it, but not wait, and instead return 0 to indicate it is not available. Then we could use this call when we have only provisional need for the resource, and we can do other work when the resource is not available. The flexibility to have other work to do is generally hard to design, however. A more general resource management situation is that where we have a collection of resources, r[1], r[2], ... r[m], rather than just a single resource to be shared. Now if we have n cooperating processes, 1, 2, ..., n, where from time-to-time, process t requires the exclusive use of the resources specified in the set S[t], then we can use the following algorithm to manage these resources, granting them to requesting processes while never allowing starvation to occur. When we have more than one exclusive resource, we must also avoid the possibility of "deadlock". Deadlock occurs when, for example, process 1 possesses resource 1 and now requires resource 2, while process 2 possesses resource 2 and now requires resource 1. The algorithm below avoids deadlock by requiring that all the resources eventually needed simultaneously by a process, t, be recorded in the set S[t]. (Note, we assume each process has only one such simultaneity set of resources, but it is relatively straighforward to allow a process to have several such sets by specifying such a process with distinct synonyms, one for each simultaneity resource-set. Again, however, we assume we are dealing with cooperating processes where under no circumstances does any process hold any resource indefinitely.) The program given below is to run as a separate process. It requires the number of resources, m, and the number of processes, n, be known a priori or made available by some means. Note, however, we only need these values for array allocation purposes, so we really could do without this knowledge with more elaborate programming. The int32 array limit[1:n] and the resource sets S[t] for t = 1,...,n are also to be supplied as input; limit[t] is the number of times the process t can be passed-over before it is given priority for the assignment of resources. A process t is to send a 'resources-request' message of message-type 1 to the queue qid1, with the requesting processes' number t as the message-text. When the resources in S[t] are "safe" for process t to use, the resource-manager sends a 'resources-granted' message with message-type t to the queue qid2. Finally, when process t wishes to relinquish resource j, it is to send a 'relinquish' message of message-type 2 to the queue qid1 with the relinquished resource number j in the the message-text. Note that a requesting process may 'block' after making a request by calling getmessage to recieve the 'resources-granted message' with the waitsw argument set to 0, or it may keep running and 'poll' for the 'resources-granted' message from time-to-time by calling getmessage with the waitsw argument set to IPC_NOWAIT. { /* begin resource-mamager */ #define WAIT 0 #define REQUEST 1 #define RELINQUISH 2 int32 P[1:n]; int32 Q[1:n]; char resbusy[1:m]; int32 reserve[1:m]; int16 over[1:n]; int16 lengthP, lengthQ; int16 k,j,t; int16 change,waitsw; int32 pidkey; MSGBUF ms; pidkey = getpid(); setupmsgqueue(&qid1,pidkey,0); /*Create qid1*/ setupmsgqueue(&qid2,pidkey-1,0); /*Create qid2*/ ms = calloc(32);/* Allocate ms message buffer */ lengthP = 0; lengthQ = 0; delta: change = 0; alpha: if (change == 0) waitsw = WAIT; else waitsw = IPC_NOWAIT; k = getmessage(qid1,ms,28,0,waitsw); /* k = -1 when there is no message in qid1.*/ if (k == -1) goto gamma; /* Check if ms is a resources-request message.*/ if (ms->mtype == REQUEST) {/* Set t = the process number of the requesting process.*/ t = *(int32 *)ms->mtext; /* If t is not in the priority-request queue, P, or in the ordinary-request queue, Q, add t to the end of Q.*/ for (k=1; k<=lengthP; k++) if (P[k]==t) goto alpha; for (k=1; k<=lengthQ; k++) if (Q[k]==t) goto alpha; \* Add t to Q at the end.*/ Q[++lengthQ]=t; over[t]=0; change++; goto alpha; } /* Here ms is a relinguish-resource message. Set j = the relinquished resource number.*/ j = *(int32 *)ms->mtext; resbusy[j] = 0; change++; if (lengthP == 0) goto gamma; /* Check if some process in the priority-request queue P wants resource j.*/ t = reserve[j]; if (t == 0) goto alpha; /* resource j is not wanted.*/ /* Here resource j is wanted by process t; set k = t's position in P.*/ for (k = 1; k <= lengthP; k++) if (P[k] == t) break; /* If we can grant process t's request, do so.*/ for (j in S[t]) if ((reserve[j] != t) OR (resbusy[j] == 1)) goto alpha; /* Here we can grant process t's request.*/ /* Remove the k-th entry of the queue P.*/ while (k < lengthP) P[k] = P[++k]; lengthP--; /* Send resources-granted message to t via qid2. */ ms->mtype = t; sendmessage(qid2,ms,28,0); /* If some process in the priority-request queue P wants a resource just granted to t, reserve it for the first such process.*/ for (j in S[t]) {resbusy[j] = 1; reserve[j] = 0; for (k = 1; k <= lengthP; k++) if (j in S[k]) {reserve[j] = k; break;} } over[t] = 0; goto alpha; /* See if we can satisfy any process in the ordinary-request queue, Q.*/ gamma: k=1; scan: if (lengthQ < k) goto delta; /* Set t = the process number in the k-th entry in Q.*/ t = Q[k]; /* See if the resources in S[t] are all available and not reserved for processes other than t.*/ for (j in S[t]) if ((resbusy[j] != 0) OR ((reserve[j] != 0) AND (reserve[j] != t))) goto nogrant; /* Remove the k-th entry of the queue Q.*/ while (k < lengthQ) Q[k] = Q[++k]; lengthQ--; /* Send resources-granted message to t via qid2. */ ms->mtype = t; sendmessage(qid2,ms,28,0); for (j in S[t]) resbusy[j] = 1; over[t] = 0; goto scan; nogrant: if (++over[t] < limit[t]) {k = k+1; goto scan;} /* Process t has exhausted its forebearance and is to be moved into the priority-request queue, P.*/ for (j in S[t]) if (reserve[j] == 0) reserve[j] = t; /* Remove the k-th entry from Q.*/ while (k < lengthQ) Q[k] = Q[++k]; lengthQ--; /* Add t to the end of P.*/ P[++lengthP] = t; goto scan; } /*end of resource-manager */ The inputs to this algorithm are: the list of resource sets S[1], ..., S[n], the bit-array resbusy[1:m] initialized to 0's. (resbusy[j]=0 when resource j is available for use, and resbusy[j]=1 when resource j is being used. Thus resbusy[j] = 0 indicates our resource-manager "owns" resource j. the array over[1:n] initialized to 0's. (over[t] is the number of times we have passed-over process t in the ordinary-request queue because not every resource in it's resource set, S[t] was available. the limit array limit[1:n]. (limit[t] is the number of times we are permitted to pass-over process t in the ordinary-request queue when not every resource in it's resource set, S[t] is available. (limit[t] should be a positive integer.) When process t has requested use of the resources in S[t] and over[t] >= limit[t], we will not grant the use of any resource in S[t] until they have all become available; are then granted to process t. the array reserve[1:m] initialized to 0's. (reserve[j] is the number of the process in the priority-request queue, P, that has placed a "reservation" for resource j.) the ordinary-request queue Q[1:n], initialized to be empty (lengthQ=0). The entries in Q are process numbers. the priority-request queue P[1:n], initialized to be empty (lengthP=0). The entries in P are process numbers. This algorithm is an elaborated form of the "bankers" algorithm where a 'banker' 'loans' resources when appropriate, and 'collects' the 'loans' for reuse. It uses the two priority queues, P and Q, as follows. When a process, t, requests its set of resources, S[t], it enters the ordinary-request queue, Q. If it is passed-over there limit[t] times, it is promoted to the priority-request queue, P. As resources become available, they are reserved for the processes in P in priority order; a resource, j, is granted to a process t in Q only if (1) j is not wanted by any process in P or any other process, r, earlier in Q, such that all the resources in r's resource set, S[r], are available and not reserved, and (2) all the resources in t's resource set, S[t], are available and not reserved In practice, we need to augment the above resource-manager program with a procedure for registering resources and assigning them an integer identifier. Most resources such as files have natural names, but others need to be fit into a naming system to allow registration. We also need a convenient data-structure-based method for the resource sets, S[t], to be provided to the resource manager. The above program is written in pidgin C. You can probably see several immediate optimizations. (You might even be able to reduce the number of goto's, but it doesn't count as an improvement if readability is reduced.) This program can also be much improved by introducing data-structures that cater to its' storage, retrieval, and query needs. (In particular, if the number of resources, m, is less than 33, you might be able to use bitwise Boolean operations to advantage.) Note the above program is applicable to managing the Blockbuster or Netflix systems if we interpret clients as processes and DVDs as resources, and assume there is only one DVD of each movie. This leads to considering the generalization where there is a pool of c[j] "copies" of resource j. We might also consider the situation where a process can request resource 1 or resource 2 and be satisfied when either one is granted. #endif /*DISCUSSION*/ /* end of msgfuncs.c */