The second 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, you are to utilize low-level system calls to
create this pqsh
shell by noon on Saturday, September 28, 2019.
More details about this project and your deliverables are described below.
To interact with the shell, the user has access to two commands:
add COMMAND
: This command adds the specified COMMAND
as a job to the
shell's internal waiting queue.
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).
The order in which jobs should be executed is determined by one of the following scheduling policies:
FIFO: Execute jobs in the order in each they arrival in the process queue.
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.
This project relates directly to our discussion on schedulers. Refer to your textbook, Operating Systems: Three Easy Pieces and the slides on scheduling: Scheduling (FIFO, Round Robin) and Scheduling (MLFQ, Lottery).
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:
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.
While it is unlikely that you will write an operating system scheduler in your career, you may need to implement or at least interact with things like load balancers or batch queues, especially in parallel or distributed environments such as the cloud.
For instance, many websites use Cloudflare which performs load balance to prevent denial-of-service attacks. Similarly, we have used HTCondor in the past to schedule many jobs on the distributed computing cluster at Notre Dame. In both of these situations some decision making is required to map jobs to a particular set of resources.
This project will allow to explore the challenges in this type of decision making by having you implementing and test different types of scheduling policies for a process queue.
As noted above, you are to work individually 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.
Here is a timeline of events related to this project:
Date | Event |
---|---|
Monday, September 09 | Project description and repository are available. |
Saturday, September 21 | Brainstorming should be completed. |
Saturday, September 28 | Implementation of pqsh must be completed. |
For the final submission, please open a Merge Request on your
repository (for your pqsh
branch to the master
branch) and assign
it to your grader from the Reading 04 TA List.
To start this project, you must fork the Project 02 repository on GitLab:
https://gitlab.com/nd-cse-30341-fa19/cse-30341-fa19-project02
Once this repository has been forked, follow the instructions from Reading 00 to:
Make the repository private.
Configure access to the repository.
Make sure you add all the members of the team in addition to the instructional staff.
Note: Do your work in a separate git branch that can be later merged
into the master
branch (ie. make a pqsh
branch, DO NOT COMMIT OR
MERGE TO MASTER).
The Project 02 repository includes a README.md
file with the following
sections:
Student: This should be your name and email address.
Brainstorming: This should contain your responses to the provided brainstorming questions (optional for this project).
Reflection: This should contain your responses to the provided reflection questions.
Errata: This should contain a description of any known errors or deficiencies in your implementation.
Extra Credit: This should contain a description of any extra credit you attempted or completed.
You must complete this document report as part of your project.
While it is tempting to write a long response to the brainstorming and reflection questions, please limit yourself to a few sentences at the most for each response.
This will facilitate more efficient grading and it will help you practice distilling ideas into their absolute essentials (which is useful for real world communication and for answering questions on exams).
As you can see, the base Project 02 repository contains a README.md
file
and the following folder hierarchy:
project02
\_ Makefile # This is the project Makefile
\_ bin # This contains the executables
\_ include # This contains the header files
\_ lib # This contains the libraries
\_ src # This contains the C99 source code
\_ tests # This contains test scripts and source code
You must maintain this folder structure for your project and place files in their appropriate place.
While the exact organization of the project code is up to you, keep in mind that you will be graded in part on coding style, cleaniness, and organization. This means your code should be consistently formatted, not contain any dead code, have reasonable comments, and appropriate naming among other things:
Break long functions into smaller functions.
Make sure each function does one thing and does it well.
Abstract, but don't over do it.
Please refer to these Coding Style slides for some tips and guidelines on coding style expectations.
To help you get started, we have provided a Makefile that will build the
pq
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
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 uou 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.
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 timerstamp (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
To verify the correctness of the Process
, Queue
, and timestamp
functions, three test programs are provided:
$ make test-units
Testing test_process
Testing test_queue
Testing test_timestamp
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 directory:
$ ./tests/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.
Once you have completed your project, you many extend your implementation
of pqsh
by performing either (or both) of the following modifications:
Readline: Currently, pqsh
does not have shell niceties such as
tab-completion or history. Use GNU Readline to implement these quality
of life improvements.
Cleanup: Currently, pqsh
does not have a method of clearing a
queue. Add a clear
command that removes and terminates all processes in
a specified queue (ie. clear running
removes all processes in the
running queue, terminates each process, and frees the allocated
memory).
Each of these modifications is worth 1 Point of extra credit each.
Note: Do your work in a separate git branch that can be later merged
into the master
branch (ie. make a ec-readline
or ec-clear
branch,
DO NOT COMMIT OR MERGE TO MASTER).
Your project will be graded on the following metrics:
Metric | Points |
---|---|
Source Code
|
20.0
|
Documentation
|
4.0
|
To encourage you to work on the project regularly (rather than leaving it until the last second) and to practice performing incremental development, part of your grade will be based on whether or not you have regular and reasonably sized commits in your git log.
That is, you will lose a point if you commit everything at once near the project deadline.
In addition to meeting the functional requirements of the project (as described above), your program must not exhibit any memory leaks or invalid memory accesses as would be detected by Valgrind.
Additionally, because system calls can fail, your program must implement robust error handling and ensure your code checks the status of system calls when reasonable.
Moreover, you code must compile without any warnings (and -Wall
must
be one of the CFLAGS
).