Project 01: Process Queue Shell

Overview¶

The first project is to build a basic shell that serves as a multi-core process queue called pqsh. This program allows the user to enter in a series of commands and then schedules the specified jobs to run on multiple CPU cores as separate processes.

As shown above, the process queue shell has a queue of running jobs (ie. tasks that are actively assigned CPU time), and a queue of 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 either the FIFO or Round Robin scheduling policies.

Unlike a regular shell, commands in pqsh are not executed right away. Instead, new jobs are added to a waiting queue, where they will be processed by an internal scheduling policy such as FIFO or Round Robin. When there are available resouces (ie. CPUs), the scheduler will move the job from the waiting queue to the running queue. When the job terminates, it will then move to the finished queue.

Working individually or in pairs, you are to utilize low-level system calls to create this pqsh shell by noon on Saturday, September 10, 2022. More details about this project and your deliverables are described below.

Commands¶

To interact with the shell, the user has access to two commands:

1. add COMMAND: This command adds the specified COMMAND as a job to the shell's internal waiting queue.

2. status [QUEUE]: This command displays metrics from the internal scheduler (ie. number of jobs in each queue, average turnaround time, and average response time), including the jobs in each of the internal running, waiting, and finished queues (if a QUEUE is specified then only that queue is displayed, otherwise all queues are shown).

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.

You must implement both scheduling disciplines along with any accounting and preemption mechanisms required to build these algorithms.

Usage¶

The full set of pqsh command-line options are shown below:

$ bin/pqsh -h
Usage: ./bin/pqsh [options]

Options:
    -n CORES           Number of CPU cores to utilize
    -p POLICY          Scheduling policy (fifo, rdrn)
    -t MICROSECONDS    Timer interrupt interval
    -h                 Print this help message

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

Here is an example of pqsh running one command using the FIFO scheduler on one CORE:

$ bin/pqsh

PQSH> help
Commands:
  add    command    Add command to waiting queue.
  status [queue]    Display status of specified queue (default is all).
  help              Display help message.
  exit|quit         Exit shell.

PQSH> add bin/worksim 10
Added process "bin/worksim 10" to waiting queue.

PQSH> status
Running =    1, Waiting =    0, Finished =    0, Turnaround =  -nan, Response =  -nan

Running Queue:
  PID COMMAND                        ARRIVAL       START         END
10071 bin/worksim 10                 1568055878.75 1568055878.95          0.00

PQSH> status
Running =    0, Waiting =    0, Finished =    1, Turnaround = 10.00, Response = 00.00

Finished Queue:
  PID COMMAND                        ARRIVAL       START         END
10071 bin/worksim 10                 1568055878.75 1568055878.95 1568055889.19

Here is a video example using of pqsh and the output of its test programs:

Reference Implementation¶

You can find a reference implementation of pqsh in the following location on the student machines:

/escnfs/home/pbui/pub/bin/pqsh

Feel free to play around with this in order to explore how pqsh should behave.

Deliverables¶

As noted above, you are to work individually or in pairs to implement pqsh. You must use (C99) (not C++) as the implementation language for pqsh itself, while any test scripts are to be written in any reasonable scripting language.

Timeline¶

Here is a timeline of events related to this project:

Repository¶

To start this project, you must create a Project 01 repository on GitHub using the following template:

https://classroom.github.com/a/_eBtCKit

Documentation¶

The Project 01 repository includes a README.md file with the following sections:

1. Students: This should be your name and email address.

2. Brainstorming: This contains questions that should help you design and plan your approach to the project. You do not need to fill these out, but they are meant to be helpful.

3. Errata: This should contain a description of any known errors or deficiencies in your implementation.

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

Source Code¶

As you can see, the base Project 01 repository contains a README.md file and the following folder hierarchy:

project01
    \_ Makefile     # This is the project Makefile
    \_ bin          # This contains the executables and test scripts
    \_ include      # This contains the header files
    \_ lib          # This contains the libraries
    \_ src          # This contains the C99 source code
    \_ tests        # This contains test source code

You must maintain this folder structure for your project and place files in their appropriate place.

Compiling¶

To help you get started, we have provided a Makefile that will build the pqsh application for you:

$ make                      # Build pq executable
Compiling src/pqsh.o
Compiling src/options.o
Compiling src/process.o
Compiling src/queue.o
Compiling src/signal.o
Compiling src/scheduler.o
Compiling src/scheduler_fifo.o
Compiling src/scheduler_rdrn.o
Compiling src/timestamp.o
Linking lib/libpqsh.a
Linking bin/pqsh

Running¶

Once you have the pqsh executable, you can run the shell with different number of CORES or with a different scheduling POLICY:

$ ./bin/pqsh -p fifo        # Run shell with FIFO policy

$ ./bin/pqsh -p rdrn -n 2   # Run shell with Round Robin policy and two cores

To help you test your process queue, the bin/worksim script is provided to you. This script is a workload simulator and you can use it to create a job that simulates a job that runs for a specified duration. For example, to create a job that runs for 10 seconds:

$ ./bin/worksim 10

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

Implementation¶

All of the C99 header files are in the include/pq folder while the C99 source code is contained in the src directory. To help you get started, parts of the project are already implemented:

[x] options.c               # PQSH parsing options (implemented)
[~] pqsh.c                  # PQSH main executable (partially implemented)
[ ] process.c               # PQSH process structure (not implemented)
[ ] queue.c                 # PQSH queue structure (not implemented)
[ ] scheduler.c             # PQSH scheduler structure (not implemented)
[ ] scheduler_fifo.c        # PQSH FIFO scheduler policy (not implemented)
[ ] scheduler_rdrn.c        # PQSH Round Robin scheduler policy (not implemented)
[~] signal.c                # PQSH signal handlers (partially implemented)
[ ] timestamp.c             # PQSH timestamp (not implemented)

Basically, some of pqsh shell code, signal utilities, and command-line parsing functions are provided to you, but the scheduling and process management functions are not. Each of the functions in the incomplete files above have comments that describe what needs to be done.

You will need to examine these source files and complete the implementation of the shell. To do so, you will first need to implement a basic Process structure and a corresponding Queue structure:

• process.c: This structure is used to keep track of a process in the system (reference at include/pqsh/process.h).

• queue.c: This structure is used to track a list or queue or Process structures. To enable efficient operations to the front and back of the list, the structure maintains pointers to both the head and tail of the queue. Additionally, it has a size attribute that records the number of items in the queue at all times.

• scheduler.c: This contains the main functions required for the shell include the internal operations and command handlers.

• scheduler_{fifo,rdrn}.c: These contain the implementations to the corresponding scheduling policies.

• timestamp.c: This contains the implementation of a function that returns the current time in the form of a double.

Hints¶

Here are some hints to help you get started with the project:

• process.c: To start a process, you will need to fork and exec. Consider using execvp by using strtok to form a local array of arguments to pass to the system call:

  fork()
  
  Child:
      char *argv[MAX_ARGUMENTS] = {0}
      ...
  
      for (char *token = strtok(command, " "); token; token = strtok(NULL, " ")) {
        argv[i++] = token;
      }
  
      execvp(argv[0], argv);
      ...
  
  Parent:
      Update timestamp
  

• scheduler.c: When waiting, you should consider using waitpid so you do not block or hang. If a child has terminated, then you should remove it from the queue it is in, update its metrics, and then move it to the finished queue.

  while ((pid = waitpid(-1, NULL, WNOHANG)) > 0) {
      Process *found = queue_remove(&s->running, pid);
      ...
  }
  

• signal.c: When the timer goes off, your signal handler should wait on any terminated children and then schedule the next process.

  schedule_wait(&PQShellScheduler);
  schedule_next(&PQShellScheduler);
  

• pqsh.c: To activate a regular timer interval, you should consider using the setitimer system call.

  struct itimerval interval = {
    .it_interval = { .tv_sec = 0, .tv_usec = s->timeout },
    .it_value    = { .tv_sec = 0, .tv_usec = s->timeout },
  };
  if (setitimer(ITIMER_REAL, &interval, NULL) < 0) {
    ...
  }
  

Testing¶

To verify the correctness of the Process, Queue, and timestamp functions, three test programs are provided:

$ make test-units
Testing unit_process          ...
  process_create              ... Success
  process_start               ... Success
  process_pause               ... Success
  process_resume              ... Success

Testing unit_queue            ...
  queue_push                  ... Success
  queue_pop                   ... Success
  queue_remove                ... Success

Testing unit_timestamp        ...
  timestamp                   ... Success

Likewise, to verify the behavior of your pqsh shell, we have provided you a series of test scripts:

$ make test-scripts
Testing test_fifo_checklist  ...
  Running PQSH commands      ... Success
  Verifying PQSH output      ... Success
  Verifying PQSH memory      ... Success

Testing test_fifo_multicore  ...
  Running PQSH commands      ... Success
  Verifying PQSH output      ... Success
  Verifying PQSH memory      ... Success

Testing test_fifo            ...
  Running PQSH commands      ... Success
  Verifying PQSH output      ... Success
  Verifying PQSH memory      ... Success

Testing test_rdrn_checklist  ...
  Running PQSH commands      ... Success
  Verifying PQSH output      ... Success
  Verifying PQSH memory      ... Success

Testing test_rdrn_multicore  ...
  Running PQSH commands      ... Success
  Verifying PQSH output      ... Success
  Verifying PQSH memory      ... Success

Testing test_rdrn            ...
  Running PQSH commands      ... Success
  Verifying PQSH output      ... Success
  Verifying PQSH memory      ... Success

Note, you can always run a specific test directly:

$ ./bin/test_fifo.sh      # Run FIFO test script

If necessary, you should not hesitate in create your own additional test programs or scripts to facilitate verification and debugging.

Reflection¶

To reflect on the project and the concepts involved, you will need to create a group video demonstration of your software artifact and complete an individual quiz (each member will submit their own answers to their own private assignments repository).

Video Demonstration¶

As part of your grade, your group will need to create a video that demonstrates and discusses the following:

1. Your project passing the automated tests.

2. Your project working with manual input.

3. Any errata, quirks, or unresolved issues in your project.

4. What you learned by doing this project.

Individual Quiz¶

Once you have completed the project, answer the following Project 01 Quiz questions individually in your own personal assignments repository on GitHub:

The results of the quiz should look like the following:

Checking project01 quiz ...
      Q1 0.40
      Q2 0.40
      Q3 0.40
      Q4 0.50
      Q5 0.90
      Q6 1.40
   Score 4.00 / 4.00
  Status Success

Grading¶

Your project will be graded on the following metrics: