:::::::::::::: umessage.h :::::::::::::: /* umessage.h: umessage API */ int uinit(void); int usend(int pid, int msg); int ureceive(void); :::::::::::::: umessage.c :::::::::::::: /* File: umessage.c */ /**************************************************************************** * * User-level package for message passing * using simple pid-indexed mailbox array. * ****************************************************************************/ #include #include "umessage.h" /* our guess as to how many processes this system is built for-- */ #define MAXPROC 50 #define NOSEM -1 struct msgentry { int pmsg; int phasmsg; int psem; /* NOSEM or sem id */ }; /* check if pid in our array range, and thus has mailbox-- */ #define u_isbadpid(x) (x<=0 || x>=MAXPROC) static struct msgentry msglist[MAXPROC]; /* message table */ static int mutex; /* sem for mutual exclusion */ /**************************************************************************** * uinit -- initialize the message data stucture ****************************************************************************/ int uinit() { int i; for (i = 0; i < MAXPROC; i++) { msglist[i].phasmsg = 0; msglist[i].psem = NOSEM; } if ((mutex = screate(1)) == SYSERR) return(SYSERR); else return(OK); } /**************************************************************************** * usend -- send a message to another process * eoneil note: this uses the sender-creates-sem approach ****************************************************************************/ int usend(int pid, int msg) { struct msgentry *mptr; /* for receiver's mailbox */ if (u_isbadpid(pid)) return(SYSERR); /* can't send to it: no mailbox for it */ mptr = &msglist[pid]; wait(mutex); if (mptr->phasmsg) { /* process has a message already */ signal(mutex); return(SYSERR); } /* one way to do it: create a sem when mailbox becomes "active" */ /* alternatively, hold off sem creation until really need it */ if (mptr->psem == NOSEM) /* if proc has no sem, create one */ mptr->psem = screate(0); mptr->pmsg = msg; /* deposit message */ mptr->phasmsg++; signal(mptr->psem); /* unhang any current or future wait */ /* can be put after signal(mutex) */ signal(mutex); return OK; } /**************************************************************************** * ureceive -- wait for a message and return it ****************************************************************************/ int ureceive() { struct msgentry *mptr; int pid, msg; pid = getpid(); if (u_isbadpid(pid)) return SYSERR; /* this process has no mailbox */ mptr = &msglist[pid]; /* set up pointer to this process's mailbox */ wait(mutex); if (mptr->phasmsg == 0) { /* if no message, wait for one */ if (mptr->psem == NOSEM) /* if no sem, create one */ mptr->psem = screate(0); else /* left over from prev. process of this pid!*/ sreset(mptr->psem, 0); } signal(mutex); /* release mutex: state in good shape */ wait(mptr->psem); /* wait for message if necessary */ wait(mutex); /* get mutex again for 2nd state transition */ mptr->phasmsg = 0; msg = mptr->pmsg; /* retrieve message */ sdelete(mptr->psem); mptr->psem = NOSEM; /* release sem */ signal(mutex); return msg; /* return message now in process-local var */ } :::::::::::::: kmessage.h :::::::::::::: /* kmessage.h: kmessage API */ int kinit(void); int ksend(int pid, int msg); int kreceive(void); :::::::::::::: kmessage.c :::::::::::::: /* File: kmessage.c */ #include #include #include "kmessage.h" #define NOSEM -1 struct msgentry { int pmsg; int phasmsg; int psem; /* NOSEM or sem id */ }; static struct msgentry msglist[NPROC]; /* message table */ /**************************************************************************** * * kernel-level package for message passing * ****************************************************************************/ /**************************************************************************** * kinit -- initialize the message data stucture, it is called from sysinit ****************************************************************************/ int kinit() { int i; for (i = 0; i < NPROC; i++) { msglist[i].phasmsg = 0; msglist[i].psem = NOSEM; } return(OK); } /**************************************************************************** * kcleanup -- delete semaphore associated with specified process and change * the mailbox status to inactive. Called under kernel mutex. ****************************************************************************/ void kmsg_cleanup(int pid) { if(msglist[pid].psem != NOSEM) { sdelete(msglist[pid].psem); /* this releases any sem waiters */ msglist[pid].psem = NOSEM; } } /**************************************************************************** * ksend -- send a message to another process ****************************************************************************/ int ksend(int pid, int msg) { STATWORD ps; struct msgentry *mptr; if (isbadpid(pid)) return(SYSERR); mptr = &msglist[pid]; /* OK to do outside mutex */ disable(ps); if (mptr->phasmsg) { restore(ps); return(SYSERR); } if (mptr->psem == NOSEM) /* if proc has no sem, create one */ mptr->psem = screate(0); mptr->pmsg = msg; /* deposit message */ mptr->phasmsg++; signal(mptr->psem); /* the signal can be put after restore(ps) */ restore(ps); return(OK); } /**************************************************************************** * kreceive -- wait for a message and return it ****************************************************************************/ int kreceive() { STATWORD ps; struct msgentry *mptr; int pid, msg; pid = getpid(); /* or use currpid here */ mptr = &msglist[pid]; disable(ps); if (mptr->phasmsg == 0) { /* if no message, wait for one */ if (mptr->psem == NOSEM) { /* if no sem, create one */ mptr->psem = screate(0); if (mptr->psem == SYSERR) { restore(ps); return SYSERR; } } else sreset(mptr->psem, 0); /* left over from previous one */ /* now the mailbox state is in good shape for wait */ /* restore(ps); */ /* the restore and disable won't hurt, but */ /* are not needed, because the process */ /* switch will reenable interrupts */ wait(mptr->psem); /* wait for message */ /* disable(ps); */ } mptr->phasmsg = 0; msg = mptr->pmsg; if (mptr->psem != NOSEM) { sdelete(mptr->psem); /* clean up sem, back to idle state */ mptr->psem = NOSEM; /* (or alternatively, don't clean up...) */ } restore(ps); return msg; } :::::::::::::: mloop.c :::::::::::::: /* * File: mloop.c * * This test program will send a message around and around * among N porcesses, with a delay of M msecs between receive * and send. * * Hua Tang * Apr. 12, 2003 */ #include #include "kmessage.h" #include "umessage.h" #define MESSAGE 9 /* The Xinu has 50 processes and 100 semaphores. The whole mailboxes needs one sepaphore as mutex. Among 50 processes, one is null process and one is main process. Each process will use two semaphores. Null process won't use any semaphore. The total semaphores used will be 49*2 + 1 = 99 < 100. So the maximal N will be 49 - 1(main) = 48 under current Xinu configuration. However, the real test gives maximal N = 44 based on my approach for both usend/ureceive and ksend/kreceive. Some semaphores are used by system. That decreases the maximal N. */ #define N 5 #define M 10 /* main process will sleep this time before killing child processes. */ #define MAIN_SLEEP 10 void runner(int select); /* global array of pids of message-passing processes */ int runner_pid[N]; int main(void) { int i; int error; int select; uinit(); /* test three cases: select == 1: usend/ureceive select == 2: ksend/kreceive select == 3: send/receive */ for(select = 1; select <= 3; select++) { if(select == 1) printf("mloop testing using usend/ureceive ...\n"); else if(select == 2) printf("mloop testing using ksend/kreceive ...\n"); else printf("mloop testing using send/receive ...\n"); printf("N = %d processes, M = %d msecs.\n", N, M); /* create N processes and save the process' id. */ for(i = 0; i < N; i++) { if(select == 1) runner_pid[i] = create(runner, 2000, 20, "u", 1, select); else if(select == 2) runner_pid[i] = create(runner, 2000, 20, "k", 1, select); else runner_pid[i] = create(runner, 2000, 20, "o", 1, select); printf("creating runner process %d\n", runner_pid[i]); } /* start processes */ for(i = 0; i < N; i++) resume(runner_pid[i]); /* send message to the first process created. */ if(select == 1) error = usend(runner_pid[0], MESSAGE); else if (select == 2) error = ksend(runner_pid[0], MESSAGE); else error = send(runner_pid[0], MESSAGE); if(error == SYSERR) { printf("System error happened in mloop's send. Exiting ...\n"); break; } /* wait for child processes to run this time duration before killing them. */ sleep(MAIN_SLEEP); /* kill processes and delete associated semaphores. */ for(i = 0; i < N; i++) kill(runner_pid[i]); printf("\n"); } return 0; } void runner(int select) { int npid, i; int msg; int n_msg = 0; int which; int error; int pid = getpid(); if(select == 1) which = 'u'; else if (select == 2) which = 'k'; else which = 'o'; /* determine who is the receiver for current process. */ for(i = 0; i < N; i++) { if(runner_pid[i] == pid) { /* found my i value */ npid = runner_pid[(i + 1) % N]; /* next process in loop */ break; } } while(1) { /* receive message */ if(select == 1) msg = ureceive(); else if(select == 2) msg = kreceive(); else msg = receive(); if(msg == SYSERR) { printf("System error happened in receive. Exiting...\n"); break; } /* print out one message every 50 messages. */ n_msg++; if(n_msg == 50) { printf("%c%d: %d.\n", which, pid, msg); n_msg = 0; } sleep100(M/10); /* delay M msecs, approx. */ /* send message to next process */ if(select == 1) error = usend(npid, msg); else if(select == 2) error = ksend(npid, msg); else error = send(npid, msg); if(error == SYSERR) { printf("System error happened in send, msg # %d, Exiting...\n", n_msg); break; } } } :::::::::::::: timeout.c :::::::::::::: /* * File: timeout.c * * This test program will set up two subprocesses: one will sleep 3 secs * and then "time out" by sending the original process a "timeout" * message. Another one will wait for user input from the console and * enqueue it via a Xinu port to the original process, and then send a * "success" message to the original process. The original process will * print out message according to the message received from subprocesses. * * Hua Tang * Apr. 12, 2003 */ #include #include "kmessage.h" #include "umessage.h" /* the maximal input from console */ #define LEN 128 /* message token */ #define TIMEOUT 0 #define SUCCESS 1 void runner1(int toppid, int select); void runner2(int toppid, int port, int select); int main(void) { int pid1, pid2; int recv; int port; int select; char* recmsg; int toppid = getpid(); uinit(); port = pcreate(1); /* test three cases: select == 1: usend/ureceive select == 2: ksend/kreceive select == 3: send/receive */ for(select = 1; select <= 3; select++) { if(select == 1) printf("timeout testing using usend/ureceive ...\n"); else if(select == 2) printf("timeout testing using ksend/kreceive ...\n"); else printf("timeout testing using send/receive ...\n"); /* create and start two subprocesses */ resume(pid1 = create(runner1, 2000, 20, "sleeper", 2, toppid, select)); resume(pid2 = create(runner2, 2000, 20, "messager", 3, toppid, port, select)); if(select == 1) recv = ureceive(); else if (select == 2) recv = kreceive(); else recv = receive(); if(recv == SYSERR) { printf("System error happened in receive. Exiting...\n"); break; } /* check received message and print out correct result. */ if(recv == TIMEOUT) { printf("timeout\n"); } else if(recv == SUCCESS) { recmsg = (char *)preceive(port); printf("%s\n", recmsg); } /* clean up the message in the port. */ preset(port, 0); /* kill processes and delete associated semaphores. */ kill(pid1); kill(pid2); printf("\n"); } return 0; } /* The process to run this routine will sleep 3 secs, then send out the "time out" message to the process toppid. */ void runner1(int toppid, int select) { int error; printf("I am going to sleep 3 secs.\n"); sleep(3); if(select == 1) error = usend(toppid, TIMEOUT); else if (select == 2) error = ksend(toppid, TIMEOUT); else error = send(toppid, TIMEOUT); if(error == SYSERR) { printf("System error happened in runner1's send. Exiting...\n"); kill(getpid()); } } static char buf[LEN]; /* The process to run this routine will get input from console, then send input into the port and then send "success" message to toppid. */ void runner2(int toppid, int port, int select) { int error; printf("Please enter the message: "); fgets(buf, LEN, CONSOLE); psend(port, buf); if(select == 1) error = usend(toppid, SUCCESS); else if (select == 2) error = ksend(toppid, SUCCESS); else error = send(toppid, SUCCESS); if(error == SYSERR) { printf("System error happened in runner2's send. Exiting...\n"); kill(getpid()); } } :::::::::::::: analysis.txt :::::::::::::: (from analysis from Marcus DeGruttola, edited to line up with code here) 1. Until created, the array entry for a semaphore for a given process, psem, is equal to NOSEM, later a real sem id. This is one state variable. A flag phasmsg is set when there is a message to be received. This is another state variable. After the semaphore exists, it is possible to block on a semaphore. This is yet another state. The semaphore count is always either 0 or -1. 2. State Transition diagram for one mailbox Receive runs in two parts, receive1 to the psem wait, then it holds that state for a while (if necessary) and then runs its second part, receive2, where the message is picked up and psem is released. Send runs without pause (with respect to this system, i.e, under mutex), so it has only one part. If a message is already sitting there for a process, receive runs without wait, labelled simply "receive" here. Actually, send can lose the CPU in signal, but it has finished modifying kernel variables at that point, so it doesn't count here as another transition. Waiting for message ------------- --------------- | sem exists | | no sem exists | Idle | scount=-1 |<---------| no msg | | no msg | receive1 ---------------- ------------- ^ | ^ | | | | | | | | |send receive2 | | send | | ------ | |receive | | V | V | ------------- |------------| | | sem exists |<-- --> | sem exists | | | scount=1 | | send send | | scount=0 |-- | has msg |--- --- | has msg | ------------- |------------| Has message, no Has message not yet receive seen yet picked up by ongoing receive (but receiver is ready-to-run, so will run pretty soon) Note that is is impossible for receive1 or receive2 to be generated from the blocked state "waiting-for-message", because receive only receives for its own process, and it is blocked. 3. case 1: 2 senders sending to process without a message. Both user and kernel impl's guarantee that only one of the two sends will get through. user does it with a master mutex lock. kernel does it with disable/restore. In user impl, both sends will hit the wait on the master mutex. Only one will get through while all others block. The master mutex is not released until the message is setup and a signal is sent off to the potential receiving process. Once released, the second send will come awake and find the message hold full, returning an error. In kernel impl, both sends will hit the disable. Whoever hits the atomic disable first is garanteed the cpu. Restore is not called until the message is in place. Once restored, the second send will be eligable for the CPU and will find a message in the message hold and return an error. case 2: a receiver about to return, sender sends new message. The receiver copies the old message to a local var, i.e., a process-local storage spot while still under mutex. Then it marks the message slot free and releases the mutex, and at this moment the sender can get to run, before the receiver actually returns to its caller. But it can't hurt the old message, safely held in process-local storage--it just drops off the new message in the array. case 3: a receiver has to release mutex before waiting on psem, and a sender can send it a new message before the receiver gets to call wait. Here is where the semaphores work so well--the signal can unhang a future wait just as well as a current wait, so as long as a signal goes with the send (in this implementation), all is well. 4. It is impossible for user package to clean up on a kill. A user process never sees itself get killed and isn't given the time to clean up. This means that a process can receive a message that was intended for the previous process with that PID. Here a leftover psem is reset in receive (which expects no sem there, having cleaned up after its last receive) but can be fooled in send. In the user package, we could "package up" kill into, say, msgkill, that cleans up and then calls kill, but that is a messy solution. The kernel package can do better, because we could edit kill and/or create to make sure the process starts off clean. Yes, each semaphore is independent of the others, so an app can create a different semaphore and use it in any normal way.