Project 02: Process Queue

Overview

The second project is to build a multi-core process queue called pq, whose purpose is to receive a series of jobs and then schedule them to run on multiple CPU cores as separate processes.

This process queue has two components as shown above:

1. Client: This component allows the user to send the following commands to the server:

   • Add: This adds a command to the waiting queue on the server.

   • Status: This retrieves and displays the status of the queue.

   • Running: This retrieves and displays just the running jobs in the queue.

   • Waiting: This retrieves and displays just the waiting jobs in the queue.

   • Flush: This removes all the jobs from the queue (and terminates any active processes).

2. Server: This component maintains of a queue of running jobs (ie. tasks that actively assigned CPU time), and waiting jobs (ie. tasks that haven't started yet or have been preempted). Its purpose is to schedule as many running jobs as there are CPU cores using one of the three scheduling policies mentioned below.

   The number of CORES and the scheduling policy can be specified by the user when the server is started, but cannot change once it is active. By default, the server assumes one core and the FIFO scheduling policy.

Working in groups of one or two people, you are to create this pq application by midnight on Tuesday, September 26, 2017. More details about this project and your deliverables are described below.

Protocol

To communicate, the client and server must use a common IPC mechanism such as named pipes or Unix domain sockets (which one is up to you).

The communication will be a simple text-based request and respond protocol that works as follows:

Running =    1, Waiting =    8, Levels =    0, Turnaround = 00.10, Response = 00.00

Running Queue:
  PID COMMAND              STATE    USER     THRESHOLD USAGE    ARRIVAL    START
 2309 ./worksim.py 0.1 1   Sleeping 100      0         20.75    1505531908 1505531909

Waiting Queue:
  PID COMMAND              STATE    USER     THRESHOLD USAGE    ARRIVAL    START
    0 ./worksim.py 0.1 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.5 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.5 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.5 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
      

  PID COMMAND              STATE    USER     THRESHOLD USAGE    ARRIVAL    START
 2309 ./worksim.py 0.1 1   Sleeping 100      0         20.75    1505531908 1505531909
      

  PID COMMAND              STATE    USER     THRESHOLD USAGE    ARRIVAL    START
    0 ./worksim.py 0.1 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.5 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.5 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.5 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
    0 ./worksim.py 0.9 1   Sleeping 0        0         0.00     1505531908          0
      

  Flushed 1 running and 8 waiting processes
      

Each message should be terminated with a newline character (ie. \n). Likewise, the server only needs to process one command per client and only needs to handle one client at a time. The client should echo the response it receives from the server to stdout.

Scheduling

The order in which jobs should be executed is determined by one of the following scheduling policies:

1. FIFO: Execute jobs in the order in each they arrival in the process queue.

2. Round Robin: Execute jobs in a round robin fashion.

3. Multi-Level Feedback Queue: Execute jobs based on a dynamic priority structure.

You must implement all three scheduling disciplines along with any accounting and preemption mechanims required to build these algorithms.

Usage

The full set of pq command-line options are show below:

$ ./pq -h
Usage: ./pq [options]

General Options:
    -h                 Print this help message
    -f PATH            Path to IPC channel

Client Options:
    add COMMAND        Add COMMAND to queue
    status             Query status of queue
    running            Query running jobs
    waiting            Query waiting jobs
    flush              Remove all jobs from queue

Server Options:
    -n NCPUS           Number of CPUs
    -p POLICY          Scheduling policy (fifo, rdrn, mlfq)
    -t MICROSECONDS    Time between scheduling

For instance, to start the server with 4 cores and with the Round Robin scheduling policy, we would run:

$ ./pq -n 4 -p rdrn

To add the command echo DOING_IT_FOR_THE_MONEY to the queue, we would use the client as follows:

$ ./pq add echo DOING_IT_FOR_THE_MONEY

/afs/nd.edu/user15/pbui/pub/bin/pq

$ /afs/nd.edu/user15/pbui/pub/bin/pq -f /tmp/pq.$USER

Traces

Here are some example traces of pq in action:

FIFO

Round Robin

Multi-Level Feedback Queue

Deliverables

As noted above, you are to work in groups of one or two (three is permitted, but discouraged) to implement pq. You may use either C or C++ as the implementation language. Any test scripts or auxillary tools can be written in any reasonable scripting language.

Timeline

Here is a timeline of events related to this project:

Repository

To start this project, one group member must fork the Project 02 repository on GitLab:

https://gitlab.com/nd-cse-30341-fa17/cse-30341-fa17-project02

Once this repository has been forked, follow the instructions from Reading 00 to:

1. Make the repository private

2. Configure access to the repository

   Make sure you add all the members of the team in addition to the instructional staff.

Source Code

As you can see, the base Project 02 repository contains a README.md file and a worksim.py. Unlike in CSE.20289.SP17, you are to write most of the source code for this project yourself.

That said, you must include a Makefile that builds and cleans up the project (and all its components):

$ make          # Builds pq
$ make clean    # Remove pq and any intermediate files

One script that is provided is worksim.py, which is a workload simulator. You can use it to create a job that simulates a job with a particular I/O workload and duration. For example, to create a job that is 30% I/O and 70% compute that runs for 10 seconds, you can run the following:

$ ./worksim.py 0.3 10

If you wish to suppress the debugging messages from worksim.py you can set the NDEBUG environmental variable to 1 as follows:

$ NDEBUG=1 ./worksim.py 0.3 10

This script will be useful for testing and benchmarking the different scheduling policies.

Demonstration

As part of your grade, you will need perform a series of benchmarks on your implementation of pq and then present these results face-to-face to a TA where you will demonstrate the correctness of your implementation and to discuss the results of the project.

Benchmarks

Once you have completed your implementation of pq, you must perform a series of benchmarks that answer the following questions:

1. What type of workloads are best for FIFO? Round Robin? Multi-Level Feedback Queue? That is, where does each shine and where does each falter?

2. How well does each scheduling policy perform when we have multiple cores and many processes (> 100) in the queue?

3. How well does each scheduling policy perform when jobs arrive in the queue at different time intervals?

To answer these questions, you will need to write some scripts, collect some data, and make some graphs. How you do this is up to you.

Presentation

To present the results of your benchmarks, you need to create a presentation (between 5 - 10 slides) with the following content:

1. Procedure: A short description of what you benchmarked and how you benchmarked.

2. Results: Graphs and tables that show the results of your testing.

3. Analysis: Answers to the questions above in light of your results.

4. Summary: Describe what you learned.

Please upload these slides to Google Drive and place a link in your README.md.

Be prepared to be asked about different aspects of your project, as the TA may ask you questions to probe your understanding of the material and your work.

Documentation

As noted above, the Project 02 repository includes a README.md file with the following sections:

1. Members: This should be a list of the project members.

2. Design: This is a list of design questions that you should answer before you do any coding as they will guide you towards the resources you need.

3. Demonstration: This is where you should provide a Google Drive link to your demonstration slides.

4. Errata: This is a section where you can describe any deficiencies or known problems with your implementation.

You must complete this document report as part of your project.

Extra credit

Once you have completed your project, you many extend your implementation of pq by performing either (or both) of the following modifications:

1. Protocol: In the current protocol for pq, the server only handles one command per client request. Modify the server to handle multiple commands from a single client. This will require implementing a new protocol where the client can send a message to the server, receive a result, and then send another message without having to reconnect.

2. Multiple Clients: In the current project description, the server only needs to be able to handle one client at a time. Modify the server so it can communicate with multiple clients at once.

Each of these modifications is worth 1 Point of extra credit each.

Grading

Your project will be graded on the following metrics: