CS 452/652 Winter 2022 - Kernel (Part 2)

(Version: 1)

Due Date: Mon, Jan 31, 2022, 9:00am

Introduction

In the second part of your development of the kernel, you make it possible for tasks to communicate by message passing. You use this capability to create a name server. By the end of this part of the kernel you must have:

implementations of Send(), Receive() and Reply(),
a running name server, created by the first user task, and
implementations of WhoIs() and RegisterAs() as wrappers for Sends to the name server.

The task id of the name server must be known to the RegisterAs() and WhoIs() routines, which are executed by other tasks. This might be a minor violation of the memory separation principle, but is acceptable.

In addition to the kernel primitives you must program a server and some clients. The server is the custodian of a Rock/Paper/Scissors game; the clients play the game against one another by interacting with the server.

Finally, we would like you to measure the time (in microseconds) for Send/ Receive/Reply transactions in 24 conditions generated by compiler optimization (off and on), CPU caches (off and on), Send/Receive order (Send before Receive and Receive before Send), and message size (4, 64, and 256 bytes).

Description

Kernel

To accomplish this part of the kernel you must have the following kernel primitives operating:

int Send(int tid, const char *msg, int msglen, char *reply, int replylen),
int Receive(int *tid, char *msg, int msglen), and
int Reply( int tid, void *reply, int replylen ).

See the kernel description for the details of how these primitives should operate.

FirstUserTask

In addition you must program the FirstUserTask, which initiates the application. It, or its children,

creates the name server,
creates the Rock/Paper/Scissors server, and
creates the Rock/Paper/Scissors clients.

The interaction between these tasks tests your kernel and name server.

Rock/Paper/Scissors (RPS) Server

The RPS server should be able to support multiple pairs of clients concurrently. It needs to accept and provide service for the following three types of request.

Signup. Signup requests are sent by clients that wish to play. They are queued when received, and when two are on the queue the server replies to each, asking for the first choice.
Play. Play requests tell the server which of Rock, Paper or Scissors the client chooses on this round. When play requests have been received from a pair of clients, the server replies giving the result.
Quit. Quit tells the server that a client no longer wishes to play. The server replies to let this client go, and responds to the next play request from the other client by replying that the other player quit.

RPS Clients

Clients that play the game should

find the RPS server by querying the name server,
perform a set of requests that adequately test the RPS server,
send a quit request when they have finished playing, and
exit gracefully.

The game should pause at the end of every round of the game so that the TA can see what happened. bwgetc() is handy for this. Unless the opposing player is very stupid, a client cannot do better than playing randomly.

Performance Measurement

It is already possible to measure the performance of the most performance critical parts of your kernel. The following describes a few tests that you must do, handing in the results so that we can analyse them and let you know where you stand. In doing the measurements you examine the effect of

compiler optimization on (O3) or off,
data and instruction caches (L1I, L1D, L2) on or off,
execution order, and
message size 4 bytes, 64 bytes, or 256 bytes.

To perform the test instantiate exactly two tasks: one task sends a message to the other, which receives it and then replies. They should repeat the exchange often enough that you get a good estimate of the time taken by Send/Receive/Reply. You may measure time any way you like, from the clock on the wall to the 40-bit debug timer. However, the results must be given in microseconds.

Precision

Whatever method you choose you should give at least a few minutes thought to measurement precision. If you were, for example, to run ten SRRs while watching the second hand of the wall clock, the result would be uselessly imprecise. On the other hand, building a network stack so that you can run an ntp client that adjusts the multiplier used with your crystal oscillator so that you agree with an atomic clock run by a standards institute is probably overkill.

You need to run measurements long enough to mitigate the timing effects of inevitable start/stop overhead and timing inaccuracies. However, you probably do not want to wait for hours to obtain results. As a rough guideline, the fastest SRR times are around ten microseconds, while the slowest ones are sometimes as long as a millisecond. You can also try to quantify start/stop effects to inform your thinking. Explain your measurement methodology in your assignment documentation and also briefly discuss the observed results.

Results

Please produce 24 plain text records and store them in a file performance.txt in your repository. Each record should be on a separate line and have 5 fields, separated by whitespace:

opt or noopt - optimization enabled or not
cache or nocache - caches enabled or not
R or S - receiver first or sender first
4, 64, or 256 - message size
the time per SRR operation in microseconds

Example line/record:

opt nocache R 64 187

Notes

Message size X means X bytes sent and X bytes replied.
Use task priorities to ensure the order of send and receive.
Optimization off means no optimization flag; optimization on means using the -O3 compiler flag.
If your kernel does not work with optimization enabled, put 'broken' in the time field of the optimization records.

Hand In

Hand in the following, nicely formatted and printed.

A pointer to your code repository, readable by the TAs and instructor, containing the source code of your assignment, instructions how to make the executable, and documentation (see below). The code and documentation must remain unmodified after submission until the assignments have been marked. Email the commit SHA to the instructor before the deadline.
A description of how to access, make, and operate your program in a README file, including the full pathname of your executable file, which we might download for testing.
The names of your group members in the same README file.
A description of the structure of your kernel so far. We will judge your kernel primarily on the basis of this description. Describe which algorithms and data structures you used and why you chose them. Describe your choices for critical system parameters and limitations, such as stack size, maximum number of tasks, etc.
Output produced by your game task and an explanation of why it occurs in the order it does.
The performance measurements in a separate file, a brief explanation of the methodology, and your conclusions where in your code you think the time is being spent.
Note that we intend to perform code reviews with students. A TA/instructor and might contact you to set up a (virtual) meeting.