Comp 242 Spring 1999

Time Management & Transparent Distributed IPC (Due Wed Mar 17)

In this project, you will add time management and distributed IPC to your Xinu-like kernel.

I have written some sample code that illustrates both the use of sockets and Unix signals/timers. It can be accessed from the Course home page (URL: http://www.cs.unc.edu/ dewan/242/s99/code/assignment3/)

I would recommend implementing time management first and distributed IPC next.

Time Management

The goal of this part of your project is to implement preemptive scheduling and alarms. Like Xinu, your kernel should preempt a process after its time quantum has expired. In addition, you should implement the sleep10 call. You do not have to implement tick rate or deferred processing but do have to make sure that interrupts are blocked during execution of critical regions. You can get clock interrupts from Unix by using the Unix calls setitimer and signal (the SIGVTALRM signal), and you can block interrupts using sigsetmask. The Disable and Enable routines in the sample code illustrate enabling and disabling of signal interrupts.

One problem we face with signals is that there no way to atomically change the signal mask and context switch to a new process. Recall that interrupts have to be disabled during context switching (since shared data are being changed), and the PS/signal mask value has to be restored when the new process starts. So restoring of the new PS/mask and jumping to the start address have to be done atomically. This can be done in Xinu through the rtt instruction, but we do not have such a facility in our OS. You could call restore before jumping to the new process, but when you return to the new process, you have to hope that no interrupts occur in between. The solution is to surround the call to ctxsw with Disable and Restore - so a newly ready process, before returning from resched, will explicitly restore the PS. Fortunately, this will work in the PC-Xinu version for even a new process, since such as process, when first scheduled, starts executing the intsuction after ctxsw.

When an interrupt occurs, registers are saved on the stack of the process currently executing. So be sure to allocate enough space on the stack to service multiple interrupts, otherwise you might get strange core dump errors such as unaligned access.

Distributed IPC

You should extend the semantics of the IPC primitives of the previous assignment to support communication among Xinu threads executing in different Unix processes. The Unix processes represent different Xinu kernels, and thus your IPC essentially allows threads executing on ``distributed'' Xinu kernels to talk to each other. The Xinu kernels may execute on the same or different machines. The distributed IPC you support should be transparent, that is, it should have the same syntax and semantics as the local IPC you have implemented. The only difference should be in performance. You can assume that there will be no failures.

In order to implement transparent IPC, your Xinu kernels need to know the identities and locations of all Xinu kernels in the distributed system. This information will be given as a sequence of arguments to each Unix process representing a Xinu kernel. Each of these arguments consists of a unique kernel id followed by host name. The -l flag before an argument indicates the local kernel while the -r flag indicates a remote kernel. The kernels are assigned consecutive integer ids starting from 1. Thus, the following sequence of commands:

/* executed on jeeves */
xinu -l 1:jeeves -r 2:wooster -r 3:jeeves 
xinu -r 1:jeeves -r 2:wooster -l 3:jeeves

/* executed on wooster */
xinu -r 1:jeeves -l 2:wooster -r 3:jeeves

Since IPC is transparent, user programs do not have to name hosts - they simply name ports, without worrying about the location of the processes sending messages to and receiving messages from these ports. Thus, a single global port name space is used in all kernels - for instance, port 2 means same port on all machines. To make your task easy, you may be tempted to partition the port name space among the various hosts, for instance, ports 1..8 are to be allocated by processes on host jeeves and ports 9..16 by processes on host wooster. Given a port number, you can use the partitioning to figure out which host receives messages on that port.

However, this approach is not allowed since it violates the transparency principle. A process can allocate any unallocated port, and is not restricted to ports in some range.

Your distributed Xinu IPC mechanism will be implemented on top of a distributed Unix IPC mechanism. You are free to use any Unix IPC mechanism - I would recommend sockets because they provide an easy way to do non-blocking I/O. To use sockets, you will need to learn several Unix calls: socket, bind, listen, accept, connect, select, read, write, gethostbyname, ntohs, ntohl, htons, and htonl. To learn more about these calls, you can look at the Unix man pages.

Also, as I mentioned in class, never do a read without doing a select before it that confirms that there is data to be read.

You can assume that the maximum number of xinu kernels in the distributed system is bounded - that is, you know this number at program writing time. Also, you can assume that you will always be able to get an unreserved Unix port on a machine.

In writing a distributed program, many things you are not aware of can go wrong. Therefore, your program must check for error return values from all system calls and, if these calls change the errno variable, print out its value in case of error. This should make the debugging task easier.

Issues

You should explain the issues you faced in the design of the implementation and how you resolved them. In particular, you should consider and answer the following questions:

Can you use the Unix sleep call to implement the Xinu sleep10 call?

Why not use blocking reads to get information from sockets?

How frequently should you poll for socket input - give the advantages/disadvantages of polling frequently/rarely, and justify the frequency you picked.

Why does partitioning the port name space violate the transparency principle?

How can you make the Xinu IPC calls ( alloc_port, req_port, asend, ssend, mrecv ) efficient - in particular, how can you reduce the number of Unix messages a Xinu IPC call sends? (Hint: think caching or replication of data structures.) It may not be possible to make all Xinu IPC calls efficient in a single implementation, in which case, which ones have you favoured and why? For each of these calls, explain how many Unix messages may be sent.

What kind of race conditions can occur in this distributed program and how do you prevent them? Do you need additional Unix processes for coordination or can this task be done by one or more of the Xinu kernels you create?

Because race conditions can arise in a replicated implementation, you may be tempted to do a completely centralized implementation. Here are two `hints' on how replication problems can be overcome:

1. Race conditions occur when two different distributed processes have different interpretations of the same sequence of events. You can overcome this problem sometimes by using ids of the processes that generated the events to make sure all processes agree on what happened. When this does not work, you can route distributed events though a distinguished process to make sure all processes see the same sequence of events. If all else fails you can keep all data structures in a central process - thus doing a centralized implementation.

2. You do not have to do ``absolute'' replication of shared data structure. For instance, in the case of Xinu ports, you may not guarantee that each kernel always has local information regarding the exact location/status of the port. The cached information may only be a ``hint'' and the exact status may be kept at a distinguished site. If you are wrong about the kernel id associated with the port, then that kernel will let you know and you can then check the absolute information kept at the distinguished site for the real status. If hints are true most of the time, this approach is efficient.

If this does not make sense to you, ignore it, I am talking here only about general concepts, which may not apply to your particular implementation. This is a difficult assignment, speciallyif you do a replicated implementation, so start on it right away.

• About this document ...