Description
Labs 3 and 4 will provide some background for this assignment.
The question is presented from a Linux point of view using the computer science server
mimi.cs.mcgill.ca, which you can reach remotely using ssh or putty from your laptop (see lab 1). If you
do this assignment from an MS Windows machine, then make sure to provide the DLL libraries your
program uses (if any) so that the TA can run it from their MS Windows machine. It is not the TA’s
responsibility to make your program run. The TAs will not debug your program.
You must write this assignment in the C Programming language.
Assignment Question: Building a Kernel
This assignment builds from assignment 1. You will add a new command line command:
exec prog1 prog2 prog3
This new command will simulate the kernel run-time environment, which includes the PCB, the ready
queue, the CPU, and a temporary simple memory (which we will upgrade in assignment 3). To make this
easier we will repurpose code from assignment 1.
In assignment 2 you will maintain a fully working assignment 1 and add to it a kernel run time
environment with the additional command line command: exec.
You will need to implement the following data structures: CPU, PCB, ready queue, and RAM. You will
need to implement the following algorithms: schedular, task switch, and basic memory management.
You are NOT implementing threading. You are simulating a single core CPU.
This assignment first provides a description of the files and data structures and how they work. Then a
description of the new shell command and how it works. Lastly a description of the new algorithms.
Your source files:
Your entire application must contain the source files you used from assignment 1: shell.c,
interpreter.c, and shellmemory.c. You must add the following assignment 2 files: kernel.c,
cpu.c, pcb.c, and ram.c. Add .h files as you see fit. These source files must be built using
modular programming techniques (see lab 2).
Move the main() function from shell.c to kernel.c. This is the true home of the main() function.
The kernel.c main() function calls the shell.c int shellUI() function (which is your previous
main() function from assignment #1), to display the command-line to the user. The kernel
main() will also instantiate all the kernel data structures.
Compiling assignment 2:
Compile your application using gcc with the name mykernel. To do modular programming, you
must compile your application in the following manner:
gcc -c shell.c interpreter.c shellmemory.c kernel.c cpu.c pcb.c ram.c
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 2 of 7
gcc -o mykernel shell.o interpreter.o shellmemory.o kernel.o cpu.o
pcb.o ram.o
Running assignment 2:
From the command line prompt type: ./mykernel
What mykernel displays to the user:
Kernel 1.0 loaded!
Welcome to the shell!
Shell version 2.0 Updated February 2020
$
The above dollar sign is the prompt. The cursor waits beside the prompt waiting for the user’s
input. From this prompt the user will type in their command and the shell will display the result
from that command on the screen (or an error message), and then the dollar sign is displayed
again prompting the next command. The user stays in this interface until they ask to quit.
Your shell from assignment #1 is fully functional in this assignment. A single new command is
added to the shell, called exec.
New command supported by your shell:
COMMAND DESCRIPTION
exec p1 p2 p3 Executes concurrent programs
$ exec prog.txt prog2.txt
The exec command takes one to three arguments. Each argument is the name of a different
mysh script filename. For this assignment, exec does not permit us to launch multiple scripts
with the same filename. If you try to do that your shell displays the error, “Error: Script
already loaded”. All program script execution terminates. If there is a load error, then no
programs run. The user will have to input the exec command again.
To simplify the assignment, we will assume that “compiled” programs are the same as mysh
scripts. We will reuse the shell’s interpreter to both run shell scripts and execute the kernel
programs. A more detailed description follows.
Assignment 2 data structures description:
• The RAM
o Implemented as an array of char * pointers.
▪ char *ram[1000];
o Each program executed by the shell’s exec command is loaded into ram[]. This is not
true for the mysh scripts, they are loaded and executed as in assignment 1. The exec
command runs programs concurrently, therefore the programs need to be in ram[] at
the same time. To simplify this, RAM is an array of char * pointers and the entire source
file is loaded into this array. Each line from the source file is loaded into its own cell in
the array. This RAM has space for 1000 lines of code, from at most 3 programs at the
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 3 of 7
same time. This means about 33 lines of code, on average, per program. A program is
said to be in memory when all of its lines of code are copied into cells of the array. If
there is not enough space to store all the lines in the script then the load terminates
with an error. A NULL pointer indicates that there is no code at that cell location in
ram[].
o When a program is loaded to ram[] the following operations happen:
▪ Step 1: fopen the script
▪ Step 2: find the next available cell in ram[]
▪ Step 3: copy all the lines of code into ram[]
▪ Step 4: remember the start cell number and the ending cell number of that
script in ram[]
▪ Notes:
• To read a line from the program do:
fgets(file,buffer,limit);
ram[k] = strdup(buffer);
Where k is the current line of the program.
• When the program has finished executing do:
ram[k]=NULL; For all the lines of code in ram[]
• The Ready Queue
o Implemented as a simple linked list with head and tail pointers.
▪ PCB *head, *tail;
o The ready queue is FIFO and RR. Pointer “head” points to the first PCB in the list. The
first PCB is the one that gets the CPU. Pointer “tail” points to the last PCB in the list.
New PCBs are appended at the tail. Make sure to update “tail” to point to the new PCB
after appending it to the list.
• The PCB
o For this assignment our PCB will be very simple. It will contain only three variables: a
program counter, the program’s start address, and the programs ending address. The
program counter will be an integer number that refers to the cell number of ram[]
containing the instruction to execute. The start variable contains the cell number of
ram[] of the first instruction of the program. The end variable contains the cell number
of ram[] of the last instruction of the program.
▪ struct PCB { int PC; int start; int end; };
o Note: the PCB’s PC field is not the CPU instruction pointer, therefore it is updated only
after a task switch.
o Note: when a program is launched, a PCB is created, and the PCB’s PC field points to the
first line of the program. The PCB’s PC is updated after the quanta is finished.
• The CPU
o The CPU is simulated by a struct having an instruction pointer (IP), instruction register
(IR), and a quanta field. The IP is like the PCB PC field, it points to the next instruction
to execute from ram[]. The currently executing instruction is stored in the IR.
▪ struct CPU { int IP; char IR[1000]; int quanta=2; }
o Note: the IR stores the instruction that will be sent to the Interpreter() for execution.
This simulates how the assembler instruction is loaded from RAM into the CPU’s
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 4 of 7
Instruction Register. The interpreter() function simulates the CPU’s sequencer, which
executes the instruction.
o Note: since we are not implementing threads, all concurrent programs access the same
shell memory space. Yes, we are using the shell memory of assignment #1 as one global
memory space where all the scripts will read and write, even the command line scripts.
We will upgrade this is assignment 3.
o Note: for this assignment we assume the quanta is equal to 2 lines of code for each
program.
Assignment 2 operation of the exec command:
The user, at the command line, can input any of the following:
exec prog.txt
exec prog.txt prog2.txt
exec prog.txt prog2.txt prog3.txt
In the first case only one program is launched in the kernel. In the second case two programs are
launched. In the third case three programs are launched. Launched means the following:
(1) each file is fopened and the source code is loaded completely into ram[].
(2) a PCB is created (malloc) for that program and the PCB’s fields are initialized, assuming the
load was successful.
(3) the PCB is added to the Ready Queue.
This is done for all the programs in the list.
Since we are not implementing threads the shell prompt only displays after the exec command
has finished executing all the programs.
This is how a program completes execution:
(a) the ram[] cells are assigned NULL for all instructions,
(b) the PCB is removed from the Ready Queue, and
(c) free(PCB) is called to release C language memory.
Assignment 2 program execution:
Only after the “exec” command loads all the programs into ram[] and appends the PCBs to the
Ready Queue, do the programs start to run. Each PCB in the Ready Queue is sorted First-in Firstout (FIFO) and Round Robin (RR), in the same order as they appeared in the exec command.
The exec() function is an interpreter function stored in interpreter.c. It handles the filename
argument verification error. It opens each program file. It calls the kernel function to load each
program into the simulation. The final thing it does, it starts the execution of all the loaded
programs. The exec() function does not terminate until all the programs it loaded have all
completed execution.
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 5 of 7
Specifically exec() first calls myinit() for each program to add each program into the simulation.
For example, if there are three programs then myinit() is called three times. It then calls
scheduler() to run the loaded programs.
Kernel.c has the function myinit(char *filename) which does the following:
1. It calls void addToRAM(FILE *p, int *start, int *end) from ram.c to add the source code
to the next available cells in ram[].
2. It calls PCB* makePCB(int start, int end) from pcb.c to create a PCB instance using
malloc.
3. It calls void addToReady(PCB *) from kernel.c to add the PCB to the tail of the Ready
Queue
Kernel.c has the function scheduler() which is called after all the programs have been loaded
into the simulator. The scheduler() function will be our main simulation execution loop. It will
do the following:
a. It checks to see if the CPU is available. This means that the quanta is finished or
nothing is currently assigned to the CPU
b. It copies the PC from the PCB into the IP of the CPU
c. It calls the run(quanta) function within cpu.c to run the script by copying quanta
lines of code from ram[] using IP into the IR, which then calls: interpreter(IR)
d. This executes quanta instructions from the script or until the script file is at end.
e. If the program is not at the end, then the PCB PC pointer is updated with the IP
value and the PCB is placed at the tail of the ready queue.
f. If the program is at the end, then the PCB terminates (as described previously /
above)
When the Ready queue is empty, this means that all the programs have terminated. At this
point the exec() function ends, and the user sees the shell command line prompt.
Testing your kernel:
The TAs will use and modify the provided text file to test your kernel. This text file will contain
the same tests from assignment 1 with additional exec command calls. Since we are not
implementing threads, we will not be testing recursive exec calls. You can also use this file to
test your kernel or you can test it the old fashion way by typing input from the keyboard. To use
the provided text file, you will need to run your program from the OS command line as follows:
$ ./mykernel < testfile.txt
Each line from testfile.txt will be used as input for each prompt your program displays to the
user. Instead of typing the input from the keyboard the program will take the next line from the
file testfile.txt as the keyboard input.
When testfile.txt is exhausted of input the shell command line prompt is displayed to the user
(unless testfile.txt had a quit command, in that case mykernel terminates).
Make sure your program works in the above way.
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 6 of 7
WHAT TO HAND IN
Your assignment has a due date plus two late days. If you choose to submit your assignment during the
late days, then your grade will be reduced by -5% per day. Submit your assignment to the assignment
#2 submission box in myCourses. You need to submit the following:
• A README.TXT file stating what OS you used: mimi.cs.mcgill.ca or MS Windows and any other
special instructions you think the TA needs to know to run your program.
• Your version of TESTFILE.TXT. This will be you telling the TA that you know for sure that your
program can at least do the following. The TA will run your program with this file and they will
also run it with their own version of the file.
• Submit all the .c file described in the assignment (you may want to create .h files, if so, please
hand those in as well)
• Submit a bash file to compile your source files into an executable.
• If you used MS Windows and you used a DLL then upload those as well.
You must submit your own work. You can speak to each other for help but copied code will be handled
as to McGill regulations.
HOW IT WILL BE GRADED
Your assignment is graded out of 20 points and it will follow this rubric:
• The student is responsible to provide a working solution for every requirement.
• The TA grades each requirement proportionally. This means, if the requirement is only 40%
correct (for instance), then the student receives only 40% of the points assigned to that
requirement.
• Your program must run to be graded. If it does not run, then the student receives zero for the
entire assignment. If your program only runs partially or sometimes, you should still hand it in.
You will receive partial points.
• The TA looks at your source code only if the program runs (correctly or not). The TA looks at
your code to verify that you (A) implemented the requirement as requested, and (B) to check if
the submission was copied.
• Mark breakdown:
o 1 point – Source file names. The TA must verify that the student created the specified
source files as the only source files in the application. In addition the source files must
be populated with at least what was specified in the assignment description for each
file. The student is permitted to supply additional helper functions as they see fit, if it
does not hinder the assignment requirements.
o 2 points – Modular programming. If the student wrote their application using modular
programming techniques as described in lab 2 (or seen from another course) then they
receive these points.
o 1 point – Executable named mykernel. The students compiled program must be named
mykernel.
o 1 point – A fully working assignment 1 is contained within mykernel.
o 1 point – Ability to use the shell to input the exec command (and see error message)
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 7 of 7
o 2 points – The myInit() function
o 2 points – The scheduler() function
o 1 point The Ready queue implementation
o 3 points – The run() function
o 2 points – Terminating a program
o 1 point – The ram[] data structure
o 1 point – The CPU data structure
o 2 points – Program can be tested with the TESTFILE.TXT file
You have three weeks for this assignment. Please use that time to your advantage.
