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

(Version: 1)

Due Date: Tue, Feb 6, 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:
  1. implementations of Send(), Receive() and Reply(),
  2. a running name server, created by the first user task, and
  3. 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.

In addition to the kernel primitives, the FirstUserTask, and the name server task, you must program a game server and some game 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 48 conditions generated by compiler optimization (off and on), CPU caches (off, instruction, data, both), 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, 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.
  1. 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 their first play.
  2. 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 to both clients, giving the result.
  3. 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.
The RPS server should log requests to the console, so that console output can be used to trace client/server interactions and game play.

RPS Clients

Clients that play the game should
  1. find the RPS server by querying the name server,
  2. perform a set of requests that adequately test the RPS server,
  3. send a quit request when they have finished playing, and
  4. exit gracefully.
RPS clients should log requests and replies to the console, so that console output can be used to trace client/server interactions and game play. We'll be running your game server and clients and manually reviewing the results, so try to keep your tests both short and informative. If your test is generating thousands of lines of output, that's too much! If there are multiple separate tests, make sure they are delineated in the output (or consider prompting for input between tests so that test runners can control the pace).

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. For this assignment, you need to measure the time taken by a Send/Receive/Reply sequence, under 12 different conditions: 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. Measurements should be reported in microseconds.

Give some thought to measurement precision, and explain your measurement methodology in your assignment document.

Your measurements should be reported in a CSV file with 48 rows, one row for each condition you test. Each row should consist of 5 comma-separated fields:

  1. opt or noopt - indicating whether optimization enabled or not
  2. nocache or icache or dcache or bcache - caches enabled or not: (i)nstruction, (d)ata, (b)oth
  3. R or S - indicating receiver first or sender first
  4. 4, 64, or 256 - indicating message size
  5. the measured time per SRR operation in microseconds
For example, a row might look like 
opt,icache,R,64,187
This indicates a measured time of 187 microseconds for an SRR with compiler optimization on, receive before send, and 64-bytes messages.

Notes

  1. Message size X means X bytes sent and X bytes replied.
  2. Use task priorities to ensure the order of send and receive.
  3. Optimization off means no optimization flag; optimization on means using the -O3 compiler flag.
  4. If your kernel does not work with optimization enabled, record 0 as the measured SRR time for tests with optimization on.

Submission

Your readable and documented source code should be in your repository at https://git.uwaterloo.ca. The repository must be set to 'Private' with instructor and TAs added as 'Reporter'. Your repo should include a README-K2 file, which describes how to make and operate your program. Each group should be working from a single repository.

Each group should submit a single PDF file into the K2 dropbox for this course in Learn. The PDF should include the following information:

  1. The names, userids, and student IDs of your group members.
  2. The name of your group's code repository on git.uwaterloo.ca and the SHA of the commit that we should be using for this assignment. The commit must be dated before the assignment deadline.
  3. A description of the structure of your kernel so far. Aside from testing, we will judge your program primarily on the basis of this description. Describe which algorithms and data structures you use and why you chose them. Describe your choices for critical system parameters and limitations, such as stack size, maximum number of tasks, etc.
  4. If appplicable, a description of unimplemented aspects of the assignment. Also, if you know of bugs in your implementation describe them explicitly.
  5. A description of your RPS game test - what it does and what the output should show. (We will be running your test.)
  6. A description of your performance measurement methology (how do your tests work?) and a brief summary of conclusions you can draw from your test results.
In addition, the following material should be present in your git repository, in addition to your code:
  1. The README-K2 file indicating how to build and run (a) your RPS game test, and (b) your performance measurements. We should be able to build and run your code in the linux.student.cs environment without having to edit any files. We'll be running your RPS game test and use the description in your PDF file to interpret the results.
  2. A CSV file called PerfResults.csv, containing the results of your experiments.

We may perform code reviews with students, in which case a TA/instructor and will contact you to set up a meeting.