CS644 hw4 part I Programming, due Tues., April 20, 20 pts. part II Analysis, due Tuesday, April 22, 15 pts. Kernel Coding in Xinu and Analysis of it I. Xinu Send and Receive reimplemented Xinu send and receive can be implemented using shared memory and semaphores rather than its own process state, yet keeping the same external specs. This way, the Xinu micro-kernel can be pared down to semaphores, memory management, and clock management. Do this two ways, user-level (usend, ureceive) and kernel-level (ksend, kreceive), differing only in a few lines of code where using a kernel facility is natural to the kernel code but not allowed in the user code. Specifically, 1. As a purely user-level package--the code in main will have to call an init routine, then it or any of its descendents can call usend or ureceive instead of send or receive, and get the same service. Implementation in umessage.[ch] 2. As a reimplementation of the system calls send and receive, taking advantage of kernel-allowable facilities. Call these ksend and kreceive. Implementation in kmessage.[ch]. Here is where you need to use the "shadow" trick (implementation note c. below) so you can edit sysinit.c. 3. Write a test program mloop.c that sends a message around and around among n processes, where n is determined at program startup, with a delay of m msecs, between receive and send, m>=0, also determined at program startup. (Because of the Xinu sleep100 call for 1/100 sec sleeps, m = 0, 10, 20, ... is actually achievable.) For example, if n = 3, the message is sent to A, who receives it and then sends it to B, who receives it and sends it to C, who sends it back to A, and so on. Determine at runtime whether to use usend/ureceive, ksend/kreceive, or the original send/receive. Define csend/creceive (for case-send, etc.) with an extra argument specifying which version of send/receive to actually use, and write the main code in terms of csend/creceive. Test the 3 cases of send/receive for (m, n) = (10, 3), (0, 10), and (10, 20). What is the max value of n that works? Why? 4. Write a test program timeout.c that has one subprocess that waits for 3 secs and then "times out" by sending the orig process a "timeout" message, and another subprocess that waits for input from the console (a line of user input) and enqueues it via a Xinu port to the orig process, and then sends a "success" message to the original process. The original process has set up the port and the two helper processes, then goes into a receive to be notified of which happens first, and if it is "success", retrieves the user string from the port and prints it out, and otherwise prints "timeout". Again use csend/creceive and test all 3 cases. Implementation Notes. a. Don't use lots of semaphores unless and until they are needed; one or two from the start are fine. On the other hand, use separate semaphores for waits of different processes, i.e., don't go to the extreme of having all processes waiting on messages waiting on one semaphore! b. Copy from $xuker to your hw4 dir only the .c files you are going to modify. Read the Makefile in $xuker, as well as the one in $xuex, and devise a Makefile that will build a local version of xinu, using your own .c file(s) and the rest from the xinu libraries. c. Avoid clutter in your hw4 directory! You only need a few files there. Note that if the loader already has satisfied all symbol requests for an object file when it gets to the library search, it will not load the object file from the library. Thus if foo.o (or foo.opc) is in library libzzz.a and the ld command (or i386-ld command) is ld ... foo.o libzzz.a will unconditionally load foo.o before searching libzzz.a, so the library's foo.o will not be used. (This reasoning assumes the same external symbols in the original foo.o and your variant.) Thus you do not need to make local copies of libraries--use the ones on the system, shadowed this way by your own object files, if necessary. d. Please use a static array of structs as your master data structure for a straightforward approach (so we can grade it in finite time). e. Note that part II, no. 3 contains clues about difficult points in the kernel coding, the possible race conditions. II. Analysis of your implementation of the send/receive package. Put this discussion in analysis.txt. It should be true that the your user and kernel versions are close enough to not matter in this discussion-- 1. What are your state variables? Are any of them redundant, that is, could be calculated from the others? Note that while a semaphore is active and under your control, its count can be considered part of your state. How do you discriminate between used and unused slots in the master array? 2. Focusing on one process and state transitions caused by the send and receive operations, define 3-6 states that describe your system. Draw a state transition diagram. 3. Discuss potential test-and-set and other race conditions in your code and how you guarded them. -- In particular, consider the case that two senders send almost simultaneously to a process that has no waiting message. Justify your code, considering how the two send's can trade off in execution. Does it matter whether it's case 1a or 1b? -- In particular, consider the case that receive is just about to return with its message, and another process is sending a new message to the receiver. Justify your code, considering exactly where the sender can run with respect to the receive code. Does it matter whether it's case 1a or 1b? -- Find and consider another such case. 4. Is your service really the same as send/receive in external characteristics? Consider the case where a process terminates while active in your system. Even worse, another is born with the same pid. Can this discrepancy be fixed in the user-leval package? in the kernel-level service? If so, how, if not, why not. Is the application allowed to use semaphores for its own uses while your package is in use? Files: please don't leave irrelevant *.c or *.h in your dir! We'll collect README, analysis.*, *.h, *.c, Makefile. README: list of files. Please make clear what set of files should be graded! umessage.[ch] kmessage.[ch] initialize.c: small edit of sysinit for initializing kmessage package kill.c, create.c--possible small edits for kmessage package (optional) mloop.c timeout.c analysis.txt or analysis.html Makefile: make mloop.lnx, make timeout.lnx should work to build these.