Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 1 of 6
Assignment #2
The Kernel and Process Execution
Due: Fe
uary 26, 2019 at 23:55 on myCourses
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 li
aries your
program uses (if any) so that the TA can run it from their MS Windows machine. It is not the TA’s
esponsibility 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 simple memory. 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.
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.
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 UI function (maybe your previous main() function),
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
gcc -o mysh shell.o interpreter.o shellmemory.o kernel.o cpu.o pcb.o
am.o
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 2 of 6
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 Fe
uary 2019
$
The above dollar sign is the prompt. The cursor flashes 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 e
or 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 concu
ent 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 e
or, “E
or: Script
already loaded”. It will however continue to load/exec the other scripts.
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 a
ay of FILE pointers.
▪ FILE *ram[10];
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 concu
ently, therefore the programs need to be in ram[] at
the same time. To simplify this, RAM is an a
ay of FILE pointers. This RAM has space
for 10 FILE pointers, which relates to 10 programs. A program is said to be in memory
when its file pointer occupies one of the cells of ram[]. A NULL pointer indicates that
there is no program in ram[].
o When a program is loaded to ram[] the following operations happen:
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 3 of 6
▪ Step 1: fopen the script
▪ Step 2: find the next available cell in ram[]
▪ Step 3: assign the FILE pointer from the fopen to that cell
▪ Notes:
• To read a line from the program do:
fgets(ram[k],buffer,limit);
Where k is the cu
ent executing program.
• When the program has finished executing do :
fclose(ram[k])) and then ram[k]=NULL;
• 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 a program counter.
Since the executed programs are files, the program counter will be a file pointer.
▪ struct PCB { FILE *PC; };
o Note: the PCB PC filed is not the CPU instruction pointer, so only at each task switch
does the PCB PC field get updated.
o Note: when a program is launched, a PCB is created, and the PCB PC field points to the
first line of the program. This means at program launch the PCB PC field and the ram[]
FILE pointer are pointing to the beginning of the file. This will change after the next
quanta. The ram[] FILE pointer will still point to the beginning of the file, but the PCB PC
field will point to the cu
ent line to be executed the next time the PCB gets the CPU.
• 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 the file. The cu
ently executing instruction is stored in the IR.
▪ struct CPU { FILE *IP; char IR[1000]; int quanta=2; }
o Note: the IR stores the instruction that will be sent to the Interpreter() for execution.
o Note: since we are not implementing threads, all concu
ent programs access the same
shell memory space.
o Note: for this assignment we assume the quanta is 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
Operating Systems COMP 310 – ECSE 427 McGill University
Vybihal Assignment #2 Page 4 of 6
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 FILE pointer is assigned to a cell in ram[].
(2) a PCB is created (malloc) for that program and the same FILE pointer that was assigned to
am[] is assigned to the PCB PC field.
(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[] cell is assigned NULL,
(b) the PCB is removed from the Ready Queue, and
(c) free(PCB) 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 First-
out (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 e
or. 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