[SOLVED] Cs333 programming projects 1 to 5 solution

Overview and Goal
In this course you will be creating an operating system kernel. You’ll be using the BLITZ software
tools, which were written for this task. The goals of this project are to make sure that you can use the
BLITZ tools and to help you gain familiarity with them.
Step 1: Print the Documentation
There are a number of documents describing the BLITZ tools. You may obtain the documents by going
to the BLITZ homepage:
https://www.cs.pdx.edu/~harry/Blitz/index.html
From there you can access pdf versions. Print out the following documents:
An Overview of the BLITZ System (7 pages)
An Overview of the BLITZ Computer Hardware (8 pages)
The BLITZ Architecture (71 pages)
Example BLITZ Assembly Program (7 pages)
BLITZ Instruction Set (4 pages)
The BLITZ Emulator (44 pages)
An Overview of KPL, A Kernel Programming Language (66 pages)
Context-Free Grammar of KPL (7 pages)
BLITZ Tools: Help Information (13 pages)
The Format of BLITZ Object and Executable Files (12 pages)
Step 2: Read the Overview Document
Read the first document (“An Overview of the BLITZ System”) before proceeding to Step 3.
Project 1 Operating Systems
Page 2
Step 3: Choose Your Host Platform
You will develop your operating system code on a “host” computer and you will be running the BLITZ
tools on that host computer. You should decide now which host computer you will be using.
The BLITZ tools run on the follow host platforms:
Apple Macintosh, OS X, either PPC-based or Intel-based machines
Sun Solaris
Unix / Linux Systems
Windows, using Cygwin which emulates the Unix POSIX interface (see www.cygwin.com)
For the following host platforms, the tools are precompiled and you can simply download the
executables:
Apple Macintosh, OS X, Intel-based machines
Apple Macintosh, OS X, PPC-based machines
Sun Solaris
For other systems, you can download the tools (which are written in “C” and “C++”. You must then
compile them on your computer.
The source code for all the BLITZ tools is available, but you should not need to look at it. Nevertheless,
it is available for anyone who is interested.
The BLITZ Tools
Here are the programs that constitute the BLITZ tool set.
kpl
The KPL compiler
asm
The BLITZ assembler
lddd
The BLITZ linker
blitz
The BLITZ machine emulator (the virtual machine and debugger)
diskUtil
A utility to manipulate the simulated BLITZ “DISK” file
dumpObj
A utility to print BLITZ .o and a.out files
hexdump
A utility to print any file in hex
check
A utility to run through a file looking for problem ASCII characters
endian
A utility to determine if this machine is Big or Little Endian
Project 1 Operating Systems
Page 3
These tools are listed more-or-less in the order they would be used. You will probably only need to use
the first 4 or 5 tools and you may pretty much ignore the remaining tools. (The last three tools are only
documented by the comments at the beginning of the source code files, which you may read if
interested.)
Organization of the Course Material
The BLITZ system is accessible via the following URL:
https://www.cs.pdx.edu/~harry/Blitz/
The Blitz directory contains the following material:
Blitz/
BlitzDoc/
…files containing the documents mentioned above…
BlitzBin/
MacIntel/
…executables for the Mac/Intel host platform…
MacPPC/
…executables for the Mac/PPC host platform…
Sun/
…executables for the Sun/Solaris host platform…
BlitzSrc/
…source code for the BLITZ tools…
OSProject/
p1/
…files related to project 1…
p2/
…files related to project 2…
…etc…
You may access this material through the BLITZ Home page. You should also be able to “ftp” directly
to these directories.
Step 4A: For Mac Users…
Step 1: Create a directory to put the BLITZ tools into. For example, you may wish to create a
directory called BlitzTools in your home directory:
/Users/YourUserName/BlitzTools
Project 1 Operating Systems
Page 4
Then copy all the files from
www.cs.pdx.edu/~harry/Blitz/BlitzBin/MacIntel
to your BlitzTools directory. These are binary files, not text files.
(I use an application called “Fetch” (www.fetchsoftworks.com) to do “ftp” file transfers.)
People using an older PPC-based Mac should use this directory instead:
www.cs.pdx.edu/~harry/Blitz/BlitzBin/MacPPC
Step 2: Set the protection bits on these programs to include “executable”, with a command such as:
chmod ugo+rx BlitzTools/*
Step 4B: For Portland State University Students…
See section 4C.
Step 4C: For Users in a Shared Environment…
This section applies to users who have an account on a shared system, such as a Sun/Solaris system.
It is assumed that the BLITZ tools have already been downloaded by someone else and are available
in some shared directory. All you need to do is modify your PATH variable so that your shell will
search the appropriate directory.
For example, students at Portland State University who have an account on the shared Sun/Solaris
system can find the executables in this directory:
~harry/public_html/Blitz/BlitzBin/Sun
Students at other institutions can find the executables in this directory:
_________________________________________________________________________
Step 4D: For Unix/Linux Users…
This section applies to users who have a Unix/Linux box and wish to download and re-compile the
BLITZ tools for their machine.
Project 1 Operating Systems
Page 5
Step 1: Create a directory to put the BLITZ source code into. For example, you may wish to create
a directory called BlitzSrc in your home directory:
~YourUserName/BlitzSrc
Then copy all the files from
www.cs.pdx.edu/~harry/Blitz/BlitzSrc
to your BlitzSrc directory.
Step 2: Compile the programs in
~YourUserName/BlitzSrc
There is a “makefile” so you should be able to execute the following commands to compile the tools.
cd ~YourUserName/BlitzSrc
make
This will invoke the “C” and “C++” compilers to produce the following executables:
kpl
asm
lddd
blitz
diskUtil
dumpObj
hexdump
check
endian
Step 3: Create a directory for the executables and move them into it:
mkdir ~YourUserName/BlitzTools
cd ~YourUserName/BlitzSrc
mv kpl asm lddd blitz diskUtil dumpObj hexDump check endian
~YourUserName/BlitzTools
Step 4E: For Windows Users…
Consult the document:
www.cs.pdx.edu/~harry/Blitz/OSProject/p1/BlitzOnWindows.pdf
www.cs.pdx.edu/~harry/Blitz/OSProject/p1/BlitzOnWindows.htm
Project 1 Operating Systems
Page 6
Step 5: Modify Your Search Path and Verify the Tools are Working
You must add the BlitzTools directory to your shell’s search path so that when you type in the name of
a BLITZ tool (such as kpl or blitz), your shell can locate the executable file and execute it.
The Unix “shell” program maintains a “shell variable” called PATH which it uses to locate an
executable whenever a command name is typed. Details of how to change the PATH variable will vary
between the different shells.
One approach might be to alter the .aliases file in your home directory.
For example, this file may already contain a line that looks something like this:
setenv PATH ${PATH}:${HOME}/bin
(Between each colon (:) is a directory specification. The above command sets PATH to whatever it was
before followed by the bin directory in your home directory.)
What you need to do is add the BLITZ tools directory in front of whatever else is in the PATH.
Unix / Linux / Mac users who have placed the executables into a subdirectory in their home directory
might add the following command to prepend the appropriate directory to the front of the PATH.
setenv PATH ${HOME}/BlitzTools:${PATH}
Users in a shared Sun/Solaris environment will need to know the shared directory containing the tools.
Assume it is:
~instructorUserid/BlitzTools
Be sure to get the exact directory name, then add the following command after the last place PATH is
set.
setenv PATH ~instructorUserid/BlitzTools:${PATH}
Portland State University students can add the following command after the last place PATH is set.
setenv PATH ~harry/public_html/Blitz/BlitzBin/Sun:${PATH}
The “bash” shell is a little different; these people should add something like this to .bashaliases:
export PATH=${HOME}/BlitzTools:${PATH}
Project 1 Operating Systems
Page 7
The shell builds an internal hash table that speeds up the location of programs whenever you type a
command. After changing your PATH, you’ll need to restart your shell so that it uses the new PATH
when it builds this hash table.
You can do this several ways. A Mac user can quit the “Terminal” application and then restart
“Terminal”. A Unix / Linux / Solaris user can log out and log back in. In some shells you can simply
type the command “source .aliases” instead.
Next, verify that whatever you did to the PATH variable worked.
At the UNIX/Linux prompt, type the command.
kpl
You should see the following:
***** ERROR: Missing package name on command line
********** 1 error detected! **********
If you see this, good. If you see anything else, then something is wrong.
Step 6: Set up a Directory for Project 1
Create a directory in which to place all files concerned with this class. We recommend a name matching
your course number, for example:
~YourUserName/cs333
Create a directory in which to place the files concerned with project 1. We recommend the following
name:
~YourUserName/cs333/p1
Copy all files from:
https://www.cs.pdx.edu/~harry/Blitz/OSProject/p1/
to your cs333/p1 directory.
Project 1 Operating Systems
Page 8
The BLITZ Assembly Language
In this course you will not have to write any assembly language. However, you will be using some
interesting routines which can only be written in assembly. All assembly language routines will be
provided to you, but you will need to be able to read them.
Take a look at Echo.s and Hello.s to see what BLITZ assembly code looks like.
Step 7: Assemble, Link, and Execute the “Hello” Program
The p1 directory contains an assembly language program called “Hello.s”. First invoke the assembler
(the tool called “asm”) to assemble the program. Type:
asm Hello.s
This should produce no errors and should create a file called Hello.o.
The Hello.s program is completely stand-alone. In other words, it does not need any library functions
and does not rely on any operating system. Nevertheless, it must be linked to produce an executable
(“a.out” file). The linking is done with the tool called “lddd”. (In UNIX, the linker is called “ld”.)
lddd Hello.o –o Hello
Normally the executable is called a.out, but the “-o Hello” option will name the executable Hello.
Finally, execute this program, using the BLITZ virtual machine. (Sometimes the BLITZ virtual
machine is referred to as the “emulator.”) Type:
blitz –g Hello
The “-g” option is the “auto-go” option and it means begin execution immediately. You should see:
Project 1 Operating Systems
Page 9
Beginning execution…
Hello, world!
**** A ‘debug’ instruction was encountered *****
Done! The next instruction to execute will be:
000080: A1FFFFB8 jmp 0xFFFFB8 ! targetAddr = main
Entering machine-level debugger…
======================================================
===== =====
===== The BLITZ Machine Emulator =====
===== =====
===== Copyright 2001-2007, Harry H. Porter III =====
===== =====
======================================================
Enter a command at the prompt. Type ‘quit’ to exit or ‘help’ for
info about commands.
>
At the prompt, quit and exit by typing “q” (short for “quit”). You should see this:
> q
Number of Disk Reads = 0
Number of Disk Writes = 0
Instructions Executed = 1705
Time Spent Sleeping = 0
Total Elapsed Time = 1705
This program terminates by executing the debug machine instruction. This instruction will cause the
emulator to stop executing instructions and will throw the emulator into command mode. In command
mode, you can enter commands, such as quit. The emulator displays the character “>” as a prompt.
After the debug instruction, the Hello program branches back to the beginning. Therefore, if you
resume execution (with the go command), it will result in another printout of “Hello, world!”.
Step 8: Run the “Echo” Program
Type in the following commands:
asm Echo.s
lddd Echo.o –o Echo
blitz Echo
Project 1 Operating Systems
Page 10
On the last line, we have left out the auto-go “-g” option. Now, the BLITZ emulator will not
automatically begin executing; instead it will enter command mode. When it prompts, type the “g”
command (short for “go”) to begin execution.
Next type some text. Each time the ENTER/RETURN key is pressed, you should see the output echoed.
For example:
> g
Beginning execution…
abcd
abcd
this is a test
this is a test
q
q
**** A ‘debug’ instruction was encountered *****
Done! The next instruction to execute will be:
cont:
0000A4: A1FFFFAC jmp 0xFFFFAC ! targetAddr = loop
>
(For clarity, the material entered on the input is underlined.)
This program watches for the “q” character and stops when it is typed. If you resume execution with the
go command, this program will continue echoing whatever you type.
The Echo program is also a stand-alone program, relying on no library functions and no operating
system.
The KPL Programming Language
In this course, you will write code in the “KPL” programming language. Begin studying the document
titled “An Overview of KPL: A Kernel Programming Language”.
Step 9: Compile and Execute a KPL Program called “HelloWorld”
Type the following commands:
kpl -unsafe System
asm System.s
kpl HelloWorld
asm HelloWorld.s
asm Runtime.s
lddd Runtime.o System.o HelloWorld.o -o HelloWorld
Project 1 Operating Systems
Page 11
There should be no error messages.
Take a look at the files HelloWorld.h and HelloWorld.c. These contain the program code.
The HelloWorld program makes use of some other code, which is contained in the files System.h and
System.c. These must be compiled with the “-unsafe” option. Try leaving this out; you’ll get 17
compiler error messages, such as:
System.h:39: ***** ERROR at PTR: Using ‘ptr to void’ is unsafe;
you must compile with the ‘unsafe’ option
if you wish to do this
Using the UNIX compiler convention, this means that the compiler detected an error on line 39 of file
System.h.
KPL programs are often linked with routines coded in assembly language. Right now, all the assembly
code we need is included in a file called Runtime.s. Basically, the assembly code takes care of:
Starting up the program
Dealing with runtime errors, by printing a message and aborting
Printing output (There is no mechanism for input at this stage… This system really needs an OS!)
Now execute this program. Type:
blitz –g HelloWorld
You should see the “Hello, world…” message. What happens if you type “g” at the prompt, to resume
instruction execution?
The “makefile”
The p1 directory contains a file called makefile, which is used with the UNIX make command.
Whenever a file in the p1 directory is changed, you can type “make” to re-compile, re-assemble, and relink as necessary to rebuild the executables.
Notice that the command
kpl HelloWorld
will be executed whenever the file System.h is changed. In KPL, files ending in “.h” are called “header
files” and files ending in “.c” are called “code files.” Each package (such as HelloWorld) will have
both a header file and a code file. The HelloWorld package uses the System package. Whenever the
header file of a package that HelloWorld uses is changed, HelloWorld must be recompiled. However,
if the code file for System is changed, you do not need to recompile HelloWorld. You only need to relink (i.e., you only need to invoke lddd to produce the executable).
Project 1 Operating Systems
Page 12
Consult the KPL documentation for more info about the separate compilation of packages.
Step 10: Modify the HelloWorld Program
Modify the HelloWorld.c program by un-commenting the line
–foo (10)
In KPL, comments are “–” through end-of-line. Simply remove the hyphens and recompile as
necessary, using “make”.
The foo function calls bar. Bar does the following things:
Increment its argument
Print the value
Execute a “debug” statement
Recursively call itself
When you run this program it will print a value and then halt. The keyword debug is a statement that
will cause the emulator to halt execution. In later projects, you will probably want to place debug in
programs you write when you are debugging, so you can stop execution and look at variables.
If you type the go command, the emulator will resume execution. It will print another value and halt
again. Type go several times, causing bar to call itself recursively several times. Then try the st
command (st is short for “stack”). This will print out the execution stack. Try the fr command (short
for “frame”). You should see the values of the local variables in some activation of bar.
Try the up and down commands. These move around in the activation stack. You can look at different
activations of bar with the fr command.
Step 11: Try Some of the Emulator Commands
Try the following commands to the emulator.
Project 1 Operating Systems
Page 13
quit (q)
help (h)
go (g)
step (s)
t
reset
info (i)
stack (st)
frame (fr)
up
down
Abbreviations are shown in parentheses.
The “step” command will execute a single machine-language instruction at a time. You can use it to
walk through the execution of an assembly language program, line-by-line.
The “t” command will execute a single high-level KPL language statement at a time. Try typing “t”
several times to walk through the execution of the HelloWorld program. See what gets printed each
time you enter the “t” command.
The i command (short for info) prints out the entire state of the (virtual) BLITZ CPU. You can see the
contents of all the CPU registers. There are other commands for displaying and modifying the registers.
The h command (short for help) lists all the emulator commands. Take a look at what help prints.
The reset command re-reads the executable file and fully resets the CPU. This command is useful
during debugging. Whenever you wish to re-execute a program (without recompiling anything), you
could always quit the emulator and then start it back up. The reset command does the same thing but is
faster.
Make sure you get familiar with each of the commands listed above; you will be using them later. Feel
free to experiment with other commands, too.
The “DISK” File
The KPL virtual machine (the emulator tool, called “blitz”) simulates a virtual disk. The virtual disk is
implemented using a file on the host machine and this file is called “DISK”. The programs in project 1
do not use the disk, so this file is not necessary. However, if the file is missing, the emulator will print a
warning. We have included a file called “DISK” to prevent this warning. For more information, try the
“format” command in the emulator.
Project 1 Operating Systems
Page 14
What to Hand In
Complete all the above steps.
To verify that you did all this, create a transcript of a terminal session showing what happened. In
particular, please include the output associated with the following steps in what you hand in.
Step 7
Step 8
Step 9
Step 11
We do not need to see the other steps.
Hand in a hardcopy print-out showing what happened. If you do not know about creating a script file,
check out the UNIX script command by typing
man script
In LARGE BLOCK LETTERS, write your full name.
Note that if you try to use a text editor while running script, a bunch of garbage characters may be put
into the file. Please do not do this. After you have created your script file, it is okay to edit it to remove
the entire editing session. We really don’t want to see a transcript of your editing session. Alternately,
you can start and stop script, creating several script files and then concatenate them.
PLEASE STAPLE ALL PAGES!
Grading for this Project
This project will be graded pass/fail.

Overview and Goal
In this project you will learn about threads and gain familiarity writing programs involving concurrency
control. You will begin by studying the thread package, which implements multi-threading. You will
make modifications and additions to the existing code. Then you will use the threads package to solve
some traditional concurrency problems.
In addition, you will gain familiarity programming in the KPL language.
If you have difficulties with this project or want to go into more depth, take a look at the document
called “The Thread Scheduler and Concurrency Control Primitives”:
https://web.cecs.pdx.edu/~harry/Blitz/BlitzDoc/ThreadScheduler.htm
https://web.cecs.pdx.edu/~harry/Blitz/BlitzDoc/ThreadScheduler.pdf
Step 1: Download the Files
Start by creating a directory for the files you’ll need for this project. You might call it:
~YourUserName/cs333/p2
Then download all the files from:
https://www.cs.pdx.edu/~harry/Blitz/OSProject/p2/
into your directory. You should get the following files:
makefile
DISK
System.h
System.c
Runtime.s
Switch.s
List.h
List.c
Thread.h
Project 2 Operating Systems
Page 2
Thread.c
Main.h
Main.c
Synch.h
Synch.c
In this project, you will modify and hand in the following files:
Main.c
Synch.h
Synch.c
After getting the files, you should be able to compile all the code (as is) with the UNIX make command.
The program executable we are building will be called “os”. You can execute the program by typing:
% make
% blitz –g os
In the course of your experimentation, you may modify other files besides Synch.h, Synch.c and
Main.c, but the code you are required to write and turn in doesn’t require any changes to the other files.
For example, you may wish to uncomment some of the print statements, to see what happens. However,
your final versions of Synch.h, Synch.c and Main.c must work with the other files, exactly as they are
distributed.
Be sure you copy all files. Even though there are similarities with some of the files used for the
previous project, there may be some subtle but important differences.
Step 2: Study the Existing Code
The code provided in this project provides the ability to create and run multiple threads, and to control
concurrency through several synchronization methods.
Start by looking over the System package. Focus on the material toward the beginning of file System.c,
namely the functions:
print
printInt
printHex
printChar
printBool
nl
MemoryEqual
StrEqual
StrCopy
StrCmp
Project 2 Operating Systems
Page 3
Min
Max
printIntVar
printHexVar
printBoolVar
printCharVar
printPtr
Get familiar with the printing functions; you’ll be calling them a lot. Some are implemented in
assembly code and some are implemented in KPL in the System package.
The following functions are used to implement the heap in KPL:
KPLSystemInitialize
KPLMemoryAlloc
KPLMemoryFree
Objects can be allocated on the heap and freed with the alloc and free statements. The HEAP
implementation is very rudimentary in this implementation. In your kernel, you may allocate objects
during start-up but after that, YOU MUST NOT ALLOCATE OBJECTS ON THE HEAP! Why? Because
the heap might fill up and then what is a kernel supposed to do? Crash.
In this project, you should not allocate anything on the heap.
The following functions can be ignored since they concern aspects of the KPL language that we will not
be using:
KPLUncaughtThrow
UncaughtThrowError
KPLIsKindOf
KPLSystemError
The Runtime.s file contains a number of routines coded in assembly language. It contains the program
entry point and the interrupt vector in low memory. Take a look at it. Follow what happens when
program execution begins at location 0x00000000 (the label “_entry”). The code labeled “_mainEntry”
is included in code the compiler produces. The “_mainEntry” code will call the main function, which
appears in the file Main.c.
In Runtime.s, follow what happens when a timer interrupt occurs. It makes an “up-call” to a routine
called _P_Thread_TimerInterruptHandler. This name refers to “a function called
TimerInterruptHandler in a package called Thread.” (_P_Thread_TimerInterruptHandler is the
name the compiler will give this function.)
All the code in this project assumes that no other interrupt types (such as a DiskInterrupt) occur. In
Runtime.s, follow what would happen if another sort of interrupt should ever occur.
Project 2 Operating Systems
Page 4
The KPL language will check for lots of error conditions, such as the use of a null pointer. Try changing
the program to make this error. Follow in Runtime.s what happens when this occurs.
Next take a look at the List package. Read the header file carefully. This package provides code that
implements a linked list. We’ll use linked lists in this project. For example, the threads that are ready to
run (and waiting for time on the CPU) will be kept in a linked list called the “ready list”. Threads that
become BLOCKED will sit on other linked lists. Also look over the List.c code file.
The key class in this project is named Thread, and it is located in the Thread package along with other
stuff (see Thread.h, Thread.c). For each thread, there will be a single Thread object. Thread is a
subclass of Listable, which means that each Thread object contains a next pointer and can be added to
a linked list.
The Thread package is central and you should study this code thoroughly. This package contains one
class (called Thread) and several functions related to thread scheduling and time-slicing:
InitializeScheduler ()
IdleFunction (arg: int)
Run (nextThread: ptr to Thread)
PrintReadyList ()
ThreadStartMain ()
ThreadFinish ()
FatalError (errorMessage: ptr to array of char)
SetInterruptsTo (newStatus: int) returns int
TimerInterruptHandler ()
FatalError is the simplest function. We will call FatalError whenever we wish to print an error
message and abort the program. Typically, we’ll call FatalError after making some check and finding
that things are not as expected. FatalError will print the name of the thread invoking it, print the
message, and then shut down. It will throw us into the BLITZ emulator command line mode. Normally,
the next thing to do might be to type the “st” command (short for “stack”), to see which functions and
methods were active.
(Of course the information printed out by the emulator will pertain to only the thread that invoked
FatalError. The emulator does not know about threads, and it is pretty much impossible to extract
information about other threads by examining bytes in memory.)
The next function to look at is SetInterruptsTo, which is used to change the “I” interrupt bit in the
CPU. We can use it to disable interrupts with code like this:
… = SetInterruptsTo (DISABLED)
and we can use it to enable interrupts:
… = SetInterruptsTo (ENABLED)
Project 2 Operating Systems
Page 5
This function returns the previous status. This is very useful because we often want to DISABLE
interrupts (regardless of what they were before) and then later we want to return the interrupt status to
whatever it was before. In our kernel, we’ll often see code like:
var oldIntStat: int
…
oldIntStat = SetInterruptsTo (DISABLED)
…
oldIntStat = SetInterruptsTo (oldIntStat)
Next take a look at the Thread class. Here are the fields of Thread:
name: ptr to array of char
status: int
systemStack: array [SYSTEM_STACK_SIZE] of int
regs: array [13] of int
stackTop: ptr to void
initialFunction: ptr to function (int)
initialArgument: int
Here are the operations (i.e., methods) you can do on a Thread:
Init (n: ptr to array of char)
Fork (fun: ptr to function (int), arg: int)
Yield ()
Sleep ()
CheckOverflow ()
Print ()
Each thread is in one of the following states: JUST_CREATED, READY, RUNNING, BLOCKED, and
UNUSED, and this is given in the status field. (The UNUSED status is given to a Thread after it has
terminated. We’ll need this in later projects.)
Each thread has a name. To create a thread, you’ll need a Thread variable. First, use Init to initialize
it, providing a name.
Each thread needs its own stack and space for this stack is placed directly in the Thread object in the
field called systemStack. Currently, this is an array of 1000 words, which should be enough. (It is
conceivable our code could overflow this limit; there is a check to make sure we don’t overflow this
limited area.)
All threads in this project will run in System mode. Therefore the stack is called the “system stack”. In
later projects, we’ll see that this stack is used only for kernel routines. User programs will have their
own stacks in their virtual address spaces, but we are getting ahead of ourselves.
Project 2 Operating Systems
Page 6
The Thread object also has space to store the state of the CPU, namely the registers. Whenever a thread
switch occurs, the registers will be saved in the Thread object. These fields (regs and stackTop) are
used by the assembly code routine named Switch.
The Thread object also has space to store a pointer to a function (the initialFunction field) and an
argument for this function (the initialArgument field). This pointer will point to the “main” function of
this thread; this is the function that will get executed when this thread begins execution. We are storing
a pointer to the function because this is a variable: different threads may execute different functions.
We are also able to supply an initial argument to this thread, through the initialArgument field. This
argument must be an integer. Often there will be several threads executing the same “main” function.
The argument is a handy way to let each thread know what its role should be. For example, we might
create 10 threads each using the same “main” function, but passing each thread a different integer (say,
between 1 and 10) to let it know which thread it is.
After initializing a new Thread, we can start it running with the Fork method. This doesn’t
immediately begin the thread execution; instead it makes the thread READY to run and places it on the
readyList. The readyList is a linked list of Threads. All Threads on the readyList have status
READY. ReadyList is a global variable. There is another global variable named currentThread,
which points to the currently executing Thread object; i.e., the Thread whose status is RUNNING.
The Yield method should only be invoked on the currently running thread. It will cause a switch to
some other thread.
Follow the code in Yield closely to see what happens when a thread switch occurs. First, interrupts are
disabled; we don’t want any interference during a thread switch. The readyList and currentThread are
shared variables and, while switching threads, we want to be able to access and update them safely.
Then Yield will find the next thread from the readyList. (If there is no other thread, then Yield is
effectively a nop.) Then Yield will make the currently running process READY (i.e., no longer
RUNNING) and it will add the current thread to the tail end of the readyList. Finally, it will call the
Run function to do the thread switch.
The Run method will check for stack overflow on the current thread. It will then call Switch to do the
actual Switch.
Switch may be the most fascinating function you ever encounter! It is located in the assembly code file
Switch.s, which you should look at carefully. Switch does not return to the function that called it.
Instead, it switches to another thread. Then it returns. Therefore, the return happens to another function
in another thread!
The only place Switch is called is from the Run function, so Switch returns to some invocation of the
Run function in some other thread. That copy (i.e., invocation) of Run will then return to whoever
called it. This could have been some other call to Yield, so we’ll return to another Yield which will
return to whoever called it.
Project 2 Operating Systems
Page 7
And this is exactly the desired functionality of Yield! A call to Yield should give up the processor for a
while, and eventually return after other threads have had a chance to execute.
Run is also called from Sleep, so we might be returning from a call to Sleep after a thread switch.
How is everything set up when a thread is first created? How can we “return to a function” when we
have not ever called it? Take a look at function ThreadStartMain in file Thread.c and look at function
ThreadStartUp in file Switch.s.
What happens when a thread is terminated? Take a look at ThreadFinish in file Thread.c. Essentially,
the thread is put to sleep with no hope of ever being awakened. (No wonder they call it “Thread
Death!”)
Next, take a look at what happens when a Timer interrupt occurs while some thread is executing. This is
an interrupt, so the CPU begins by interrupting the current routine’s execution and pushing some state
onto its (system) stack. Then it disables interrupts and jumps to the assembly code routine called
TimerInterruptHandler in Runtime.s, which just calls the TimerInterruptHandler function in
Thread.c.
In TimerInterruptHandler, we call Yield, which then switches to another thread. Later, we’ll come
back here, when this thread gets another chance to run. Then, we’ll return to the assembly language
routine which will execute a “reti” instruction. This will restore the state to exactly what it was before
and the interrupted routine (whatever it was) will get to continue.
Note that this code maintains a variable called currentInterruptStatus. This is because it is rather
difficult to query the “I” bit of the CPU. It is easier to just change the variable whenever a change to the
interrupt status changes. We see this occurring in the TimerInterruptHandler function. Clearly
interrupts will be disabled immediately after the interrupt occurs. And the Yield function will preserve
the interrupt status. So when we return from Yield, interrupts will once again be disabled. Before
returning to the interrupted thread, we set the currentInterruptStatus to ENABLED. (They must have
been enabled before the interrupt occurred—or else it could not have occurred—so after we execute the
“reti” instruction, the status will revert to what it was before, namely ENABLED.)
Now you are ready to start playing with and modifying the code! Please experiment with the code we
have just discussed, as necessary to understand it.
Step 3: Run the “SimpleThreadExample” Code
Execute and trace through the output of SimpleThreadExample in file Main.c.
In TimerInterruptHandler there is a statement
printChar (‘_’)
Project 2 Operating Systems
Page 8
which is commented out. Try uncommenting it. Make sure you understand the output.
In TimerInterruptHandler, there is a call to Yield. Why is this there? Try commenting this
statement? What happens. Make sure you understand how Yield works here.
Step 4: Run the “MoreThreadExamples” Code
Trace through the output. Try changing this code to see what happens.
Step 5: Implement the “Mutex” Class
In this part, you must implement the class Mutex. The class specification for Mutex is given to you in
Synch.h:
class Mutex
superclass Object
methods
Init ()
Lock ()
Unlock ()
IsHeldByCurrentThread () returns bool
endClass
You will need to provide code for each of these methods. In Synch.c you’ll see a behavior construct
for Mutex. There are methods for Init, Lock, Unlock, and IsHeldByCurrentThread, but these have
dummy bodies. You’ll need to write the code for these four methods.
You will also need to add a couple of fields to the class specification of Mutex to implement the desired
functionality.
How can you implement the Mutex class? Take a close look at the Semaphore class; your
implementation of Mutex will be quite similar.
First consider the IsHeldByCurrentThread method, which may be invoked by any thread. The code of
this method will need to know which thread is holding a lock on the mutex; then it can compare that to
the currentThread to see if they are the same. So, you might consider adding a field (perhaps called
heldBy) to the Mutex class, which will be a pointer to the thread holding the mutex. Of course, you’ll
need to set it to the current thread whenever the mutex is locked. You might use a null value in this field
to indicate that no thread is holding a lock on the mutex.
Project 2 Operating Systems
Page 9
When a lock is requested on the mutex, you’ll need to see if any thread already has a lock on this mutex.
If so, you’ll need to put the current process to sleep. For putting a thread to sleep, take a look at the
method Semaphore.Down. At any one time, there may be zero, one, or many threads waiting to acquire
a lock on the mutex; you’ll need to keep a list of these threads so that when an Unlock is executed, you
can wake up one of them. As in the case of Semaphores, you should use a FIFO queue, waking up the
thread that has been waiting longest.
When a mutex lock is released (in the Unlock method), you’ll need to see if there are any threads
waiting to acquire a lock on the mutex. You can choose one and move it back onto the readyList. Now
the waiting thread will begin running when it gets a turn. The code in Semaphore.Up does something
similar.
It is also a good idea to add an error check in the Lock method to make sure that the current thread
asking to lock the mutex doesn’t already hold a lock on the mutex. If it does, you can simply invoke
FatalError. (This would probably indicate a logic error in the code using the mutex. It would lead to a
deadlock, with a thread frozen forever, waiting for itself to release the lock.) Likewise, you should also
add a check in Unlock to make sure the current thread really does hold the lock and call FatalError if
not. You’ll be using your Mutex class later, so these checks will help your debugging in later projects.
The function TestMutex in Main.c is provided to exercise your implementation of Mutex. It creates 7
threads that compete vigorously for a single mutex lock.
Step 6: Implement the Producer-Consumer Solution
Both the Tanenbaum and Silberschatz, et al. textbooks contain a discussion of the Producer-Consumer
problem, including a solution. Implement this in KPL using the classes Mutex and Semaphore. Deal
with multiple producers and multiple consumers, all sharing a single bounded buffer.
The Main package contains some code that will serve as a framework. The buffer is called buffer and
contains up to BUFFER_SIZE (e.g., 5) characters. There are 5 producer processes, each modeled by a
thread, and 3 consumer processes, each modeled by a thread. Thus, there are 8 threads in addition to the
main thread that creates the others.
Each producer will loop, adding 5 characters to the buffer. The first producer will add five ‘A’
characters, the second producer will add five ‘B’s, etc. However, since the execution of these threads
will be interleaved, the characters will be added in a somewhat random order.
Step 7: Implement the Dining Philosopher’s Solution Using a Monitor
A starting framework for your solution is provided in Main.c. Each philosopher is modeled with a
thread and the code we’ve provided sets up these threads. The synchronization will be controlled by a
“monitor” called ForkMonitor.
Project 2 Operating Systems
Page 10
The code for each thread/philosopher is provided for you. Look over the PhilosophizeAndEat method;
you should not need to change this code.
The monitor to control synchronization between the threads is implemented with a class called
ForkMonitor. The following class specification of ForkMonitor is provided:
class ForkMonitor
superclass Object
fields
status: array [5] of int — For each philosopher: HUNGRY,
— EATING, or THINKING
methods
Init ()
PickupForks (p: int)
PutDownForks (p: int)
PrintAllStatus ()
endClass
You’ll need to provide the code for the Init, PickupForks and PutDownForks methods. You’ll also
need to add additional fields and perhaps even add another method.
The code for PrintAllStatus is provided. You should call this method whenever you change the status
of any philosopher. This method will print a line of output, so you can see what is happening.
How can you proceed? You’ll need a mutex to protect the monitor itself. There are two main methods
(PickupForks and PutDownForks) which are called by the philosopher threads. Upon beginning each
of these methods, the first thing is to lock the monitor mutex. This will ensure that only one thread at a
time is executing within the monitor. Just before each of these methods returns, it must unlock the
monitor (by unlocking the monitor’s mutex) so that other threads can enter the monitor code.
You’ll also need to use the Condition class, which is provided in the Synch package. (The Condition
class uses the class Mutex, so it is assumed that you’ve finished and tested the Mutex class.)
The BLITZ emulator has a number of parameters and one of these is how often a timer interrupt occurs.
The default value is every 5000 instructions. You might try changing this parameter to see how it
affects your programs behavior. To change the simulation parameters, type the sim command into the
emulator. This command will give you the option to create a file called
.blitzrc
After creating this file, you can edit it by hand. The next time you run the emulator, it will use this new
value. Also note that too small a value—like 1000—will cause the program to hang. What do you
suppose causes this effect?
Project 2 Operating Systems
Page 11
QUESTION: Both textbooks discuss the semantics of signaling a condition variable. They mention
“Hoare semantics.” The comments in the code in Synch.c say that this version implements “Mesastyle” semantics. Is this the same or different from Hoare semantics?
An Example of Correct Output
The following files contain an example of what correct output should look like:
DesiredOutput1.pdf
DesiredOutput2.pdf
DesiredOutput3.pdf
What to Hand In
Complete all the above steps.
Please submit hardcopy of the following files:
Synch.h
Synch.c
Main.c
Also include hardcopy showing the output for steps 5, 6, and 7.
Please print both your code and the output using a fixed-width font like this, in this
and all future assignments. Much of the output is designed to look nice when printed with a fixed-width
font, but is more difficult to read in a standard variable-width font.
In LARGE BLOCK LETTERS, write your full name on the first page.
PLEASE STAPLE ALL PAGES!
Basis for Grading
In this course, the code you submit will be graded on both correctness and style. Correctness means
that the code must work right and not contain bugs. Style means that the code must be neat, well
commented, well organized, and easy to read.
In style, your code should match the code we are distributing to you. The indentation should be the
same and the degree of commenting should be the same.

Overview and Goal
In this project you will gain additional familiarity writing programs involving concurrency control. You
will implement a couple of classical IPC problems to become more comfortable with Semaphores,
Mutexes, Condition Variables, and the Monitor approach.
Download New Files
Start by creating a directory for the files you’ll need for this project:
~YourUserName/cs333/p3
Then download all the files from:
https://www.cs.pdx.edu/~harry/Blitz/OSProject/p3/
Even though some of the files have the same names, be sure to get new copies for each project. In
general some files may be modified.
Please keep your old files from previous projects separate and don’t modify them once you submit them.
This is a good rule for all programming projects in all classes. If there is ever any question about
whether code was completed on time, we can always go back and look at the Unix “file modification
date” information.
For this project, you should get the following files:
makefile
DISK
System.h
System.c
Runtime.s
Switch.s
List.h
List.c
Project 3 Operating Systems
Page 2
Thread.h
Thread.c
Synch.h
Synch.c
Main.h
Main.c
The file Synch.c contains our solution for project 2. You may use either our version of this file, or the
version of Synch.c you created.
We have also included the file
Proj2Sol.pdf
which contains my solution code for Producer-Consumer and Dining Philosophers. If you had difficulty
with it, you can take a look at the solution code.
You will modify and submit the following files:
Main.h
Main.c
Task 1: Implement the Sleeping Barber Problem
An older edition of the Tanenbaum textbook describes the “Sleeping Barber” problem and gives a
solution in “C”. (This material can also be found in a separate file called SleepingBarberProblem.pdf
in the p3 directory.)
Translate this into a working KPL program. You’ll also need to create some code to print out what
happens when you run the program.
What will you do for the “cut_hair” and the “get_haircut” methods? You’ll need at least one print
statement in each routine, but be careful: they both should run at more-or-less the same time.
One barber is okay, but how many customers will you model? Will you just throw a bunch of customers
at the barbershop all at once? This might not test your code very well.
How long will the haircut last? You can implement waiting with a busy loop, such as
for i = 1 to 100
.. want to yield here?…
endFor
The goals are:
Project 3 Operating Systems
Page 3
(1) Practice creating a KPL class from scratch
(2) Practice testing your code
(3) Gain experience with semaphores, mutex locks, and thread synchronization
Task 2: The Gaming Parlor Problem
Here is the problem scenario: groups of customers come in to a “gaming parlor” to play games. They go
to the front desk to obtain one or more dice, which are used by the group while they are playing their
game, and then returned to the front desk. The front desk is in charge of lending out the dice and
collecting them after each game is finished.
The gaming parlor owns only 8 dice, which are available at the front desk before the first group comes
in.
The customers can play the following games. Listed after each game in parentheses is the number of
dice required to play that game.
Backgammon (4)
Risk (5)
Monopoly (2)
Pictionary (1)
You should model the front desk as a monitor with the following entry methods:
Request (numberOfDice: int)
Return (numberOfDice: int)
Model each group of customers as a thread. When a group is ready to play, it must obtain the necessary
number of dice. If the required number of dice is not available, then the group (i.e., the thread) must
wait. You might use a condition variable that “more dice have become available.”
You should model the following eight different groups. Each group plays one game, as shown below,
but each group plays its game 5 times. Each group must return their dice after each game and then reacquire the dice before playing again.
A – Backgammon
B – Backgammon
C – Risk
D – Risk
E – Monopoly
F – Monopoly
G – Pictionary
H – Pictionary
Project 3 Operating Systems
Page 4
To simulate playing the game, simply call the Yield method.
This problem is a generalization of the problem of resource allocation where (1) there are a number of
resources (dice) but each is identical; (2) every requesting process needs a one or more units of the
resource, (3) each requesting thread knows how many units it will need before requesting any units and
that info is included in the request, (4) all units are returned before any further requests are made.
In a monitor, each method is either an “entry” method or a local method. A monitor will always have
one Mutex lock, which is associated with entering the monitor. Every monitor will also have zero or
more condition variables, as required by the particular application.
An entry method must always begin by locking the monitor’s mutex. Before it returns, it must always
unlock the mutex. Within the entry method, the code may Signal some of the condition variables and
may Wait on condition variables. (In some applications, it may make sense to Broadcast to a condition
variable.) However, once inside of an entry method, the code should never touch the monitor’s mutex
lock, or try to look inside the condition variables.
You should model the front desk as a monitor and you should use condition variables instead of
semaphores.
If deadlock occurs, the program will freeze up and some requests for dice will go unsatisfied forever.
This is a disaster! Regardless of the order in which the groups make their requests, your solution should
be structured such that deadlock can never occur.
Your solution must not be subject to any race conditions. In other words, regardless of the order in
which the groups make their requests and return their dice, each die must never be allocated to more
than one group at a time. It should never be the case that groups are allowed to proceed when there are
too few dice. Likewise, if a group has returned its dice, other groups which are waiting must be allowed
to proceed once enough dice have become available.
Starvation can occur if it is possible that one thread can be delayed infinitely by other threads’ requests.
If the game parlor problem is extended to assume that each group will continue to play game after game
forever, then starvation might be possible, if you are not careful in your solution. If some group X
comes in requesting a lot of dice, it will be made to wait until enough dice are available. If it is possible
that other groups can come in, request a small number of dice, and have their requests granted, then
group X might get delayed forever, since there are never enough dice at the front desk at once to satisfy
group X’s needs. In other words, it might be possible for starvation of X to occur. In your solution
starvation should not be possible. (Of course, with each group limited to playing only 5 games, all the
outstanding dice will always get returned eventually and starvation can never occur, but your solution
should also avoid starvation in the presence of a never-ending sequence of Request and Return
operations.)
To verify that your code is working, please insert print statements to produce output like this…
Project 3 Operating Systems
Page 5
Initializing Thread Scheduler…
A requests 4
——————————Number of dice now avail = 8
A proceeds with 4
——————————Number of dice now avail = 4
B requests 4
——————————Number of dice now avail = 4
B proceeds with 4
——————————Number of dice now avail = 0
D requests 5
——————————Number of dice now avail = 0
E requests 2
——————————Number of dice now avail = 0
A releases and adds back 4
——————————Number of dice now avail = 4
B releases and adds back 4
——————————Number of dice now avail = 8
C requests 5
——————————Number of dice now avail = 8
H requests 1
——————————Number of dice now avail = 8
B requests 4
——————————Number of dice now avail = 8
D proceeds with 5
——————————Number of dice now avail = 3
…etc…
This output makes it fairly easy to see what the program is doing and verify that it is correct.
Below is a method you should use to produce your output. Feel free to copy this method straight into
your program.
behavior GameParlor
… Other methods…
method Print (str: String, count: int)
—
— This method prints the current thread’s name and the arguments.
— It also prints the current number of dice available.
—
print (currentThread.name)
print (” “)
print (str)
print (” “)
printInt (count)
nl ()
print (“——————————Number of dice now avail = “)
printInt (numberDiceAvail)
nl ()
endMethod
Project 3 Operating Systems
Page 6
endBehavior
This method would be called in several places…
At the beginning of the Request method:
self.Print (“requests”, numNeeded)
At the end of the Request method:
self.Print (“proceeds with”, numNeeded)
In the Return method:
self.Print (“releases and adds back”, numReturned)
What to Hand In
Please submit hardcopy of the following files:
Main.h
Main.c
Also hand in hardcopy showing your output for both tasks.
For the Sleeping Barber problem, I am not providing any testing material; you’ll have to devise some
tests on your own. Please hand in something showing how you have tested your code.
In LARGE BLOCK LETTERS, write your full name on the first page. PLEASE STAPLE ALL
PAGES!
Basis for Grading
In this course, the code you submit will be graded on both correctness and style. Correctness means
that the code must work right and not contain bugs. Style means that the code must be neat, well
commented, well organized, and easy to read.
In style, your code should match the code we are distributing to you. The indentation should be the
same and the degree of commenting should be the same.

Overview and Goal
In this project, you will implement three monitors that will be used in our Kernel. These are the
ThreadManager, the ProcessManager, and the FrameManager. The code you write will be similar to
other code from the previous projects in that these three monitors will orchestrate the allocation and
freeing of resources.
There is also an additional task—re-implement the Condition and Mutex classes to provide Hoare
Semantics—but that code will not be used in the Kernel.
Download New Files
Start by creating a new directory for this project and then download all the files from:
https://www.cs.pdx.edu/~harry/Blitz/OSProject/p4/
Even though some of the files have the same names, be sure to get new copies for each project. In
general some files may be modified.
Please keep your old files from previous projects separate and don’t modify them once you submit them.
This is a good rule for all programming projects in all classes. If there is ever any question about
whether code was completed on time, we can always go back and look at the Unix “file modification
date” information.
For this project, you should get the following files:
makefile
DISK
Runtime.s
Switch.s
System.h
System.c
List.h
Project 4 Operating Systems
Page 2
List.c
BitMap.h
BitMap.c
Main.h
Main.c
Kernel.h
Kernel.c
The packages called Thread and Synch have been merged together into one package, now called
Kernel. This package contains quite a bit of other material as well, which will be used for later projects.
In this and the remaining projects, you will be modifying the Kernel.c and Kernel.h files. Don’t
modify the code that is not used in this project; just leave it in the package.
The Kernel.c file contains the following stuff, in this order:
Thread scheduler functions
Semaphore class
Mutex class
Condition class
Thread class
ThreadManager class
ProcessControlBlock class
ProcessManager class
FrameManager class
AddrSpace class
TimerInterruptHandler
other interrupt handlers
SyscallTrapHandler
Handle functions
In this project, you can ignore everything after TimerInterruptHandler. The classes called
ThreadManager, ProcessManager, and FrameManager are provided in outline, but the bodies of the
methods are unimplemented. You will add implementations. Some other methods are marked
“unimplemented;” those will be implemented in later projects.
The BitMap package contains code you will use; read over it but do not modify it.
The makefile has been modified to compile the new code. As before, it produces an executable called
os.
You may modify the file Main.c while testing, but when you do your final run, please use the Main.c
file as it was distributed. In the final version of our kernel, the Main package will perform all
initialization and will create the first thread. The current version performs initialization and then calls
some testing functions.
Project 4 Operating Systems
Page 3
Task 1: Threads and the ThreadManager
In this task, you will modify the ThreadManager class and provide implementations for the following
methods:
Init
GetANewThread
FreeThread
In our kernel, we will avoid allocating dynamic memory. In other words, we will not use the heap. All
important resources will be created at startup time and then we will carefully monitor their allocation
and deallocation.
An example of an important resource is Thread objects. Since we will not be able to allocate new
objects on the heap while the kernel is running, all the Thread objects must be created ahead of time.
Obviously, we can’t predict how many threads we will need, so we will allocate a fixed number of
Thread objects (e.g., 10) and re-use them.
When a user process starts up, the kernel will need to obtain a new Thread object for it. When a
process dies, the Thread object must be returned to a pool of free Thread objects, so it can be recycled
for another process.
Kernel.h contains the line:
const MAX_NUMBER_OF_PROCESSES = 10
Since each process in our OS will have at most one thread, we will also use this number to determine
how many Thread objects to place into the free pool initially.
To manage the Thread objects, we will use the ThreadManager class. There will be only one instance
of this class, called threadManager, and it is created and initialized at startup time in Main.c.
Whenever you need a new Thread object, you can invoke threadManger.GetANewThread. This
method should suspend and wait if there are currently none available. Whenever a thread terminates, the
scheduler will invoke FreeThread. In fact, the Run function has been modified in this project to
invoke FreeThread when a thread terminates—thereby adding it to the free list—instead of setting its
status to UNUSED.
Here is the definition of ThreadManager as initially distributed:
Project 4 Operating Systems
Page 4
class ThreadManager
superclass Object
fields
threadTable: array [MAX_NUMBER_OF_PROCESSES] of Thread
freeList: List [Thread]
methods
Init ()
Print ()
GetANewThread () returns ptr to Thread
FreeThread (th: ptr to Thread)
endClass
When you write the Init method, you’ll need to initialize the array of Threads and you’ll need to
initialize each Thread in the array and set its status to UNUSED. (Each Thread will have one of the
following as its status: READY, RUNNING, BLOCKED, JUST_CREATED, and UNUSED.)
Threads should have the status UNUSED iff they are on the freeList. You’ll also need to initialize the
freeList and place all Threads in the threadTable array on the freeList during initialization.
You will need to turn the ThreadManager into a “monitor.” To do this, you might consider adding a
Mutex lock (perhaps called threadManagerLock) and a condition variable (perhaps called
aThreadBecameFree) to the ThreadManager class. The Init method will also need to initialize
threadManagerLock and aThreadBecameFree.
The GetANewThread and FreeThread methods are both “entry methods,” so they must obtain the
monitor lock in the first statement and release it in the last statement.
GetANewThread will remove and return a Thread from the freeList. If the freeList is empty, this
method will need to wait on the condition of a thread becoming available. The FreeThread method will
add a Thread back to the freeList and signal anyone waiting on the condition.
The GetANewThread method should also change the Thread status to JUST_CREATED and the
FreeThread method should change it back to UNUSED.
We have provided code for the Print method to print out the entire table of Threads.
Note that the Print method disables interrupts. The Print method is used only while debugging and will
not be called in a running OS so this is okay. Within the Print method, we want to get a clean picture of
the system state—a “snapshot”—(without worrying about what other threads may be doing) so disabling
interrupts seems acceptable. However, the other methods—Init, GetAThread and FreeThread—must
NOT disable interrupts, beyond what is done within the implementations of Mutex, Condition, etc.
In Main.c we have provided a test routine called RunThreadManagerTests, which creates 20 threads
to simultaneously invoke GetAThread and FreeThread. Let’s call these the “testing threads” as
opposed to the “resource threads,” which are the objects that the ThreadManager will allocate and
monitor. There are 20 testing threads and only 10 resource thread objects.
Every thread that terminates will be added back to the freeList (by Run, which calls FreeThread).
Since the testing threads were never obtained by a call to GetANewThread, it would be wrong to add
Project 4 Operating Systems
Page 5
them back to the freeList. Therefore, each testing thread does not actually terminate. Instead it freezes
up by waiting on a semaphore that is never signaled. By the way, the testing threads are allocated on the
heap, in violation of the principle that the kernel must never allocate anything on the heap, but this is
okay, since this is only debugging code, which will not become a part of the kernel.
In the kernel, we may have threads that are not part of the threadTable pool (such as the IdleThread),
but these threads must never terminate, so there is no possibility that they will be put onto the freeList.
Thus, the only things on the freeList should be Threads from threadTable.
You will also notice that the Thread class has been changed slightly to add the following fields:
class Thread
…
fields
…
isUserThread: bool
userRegs: array [15] of int — Space for r1..r15
myProcess: ptr to ProcessControlBlock
methods
…
endClass
These fields will be used in a later project. The Thread methods are unchanged.
Task 2: Processes and the ProcessManager
In our kernel, each user-level process will contain only one thread. For each process, there will be a
single ProcessContolBlock object containing the per-process information, such as information about
open files and the process’s address space. Each ProcessControlBlock object will point to a Thread
object and each Thread object will point back to the ProcessControlBlock.
There may be other threads, called “kernel threads,” which are not associated with any user-level
process. There will only be a small, fixed number of kernel threads and these will be created at kernel
start-up time.
For now, we will only have a modest number of ProcessControlBlocks, which will make our testing
job a little easier, but in a real OS this constant would be larger.
const MAX_NUMBER_OF_PROCESSES = 10
All processes will be preallocated in an array called processTable, which will be managed by the
ProcessManager object, much like the Thread objects are managed by the ThreadManager object.
Each process will be represented with an object of this class:
Project 4 Operating Systems
Page 6
class ProcessControlBlock
superclass Listable
fields
pid: int
parentsPid: int
status: int — ACTIVE, ZOMBIE, or FREE
myThread: ptr to Thread
exitStatus: int
addrSpace: AddrSpace
fileDescriptor: array [MAX_FILES_PER_PROCESS] of ptr to OpenFile
methods
Init ()
Print ()
PrintShort ()
endClass
Each process will have a process ID (the field named pid). Each process ID will be a unique number,
from 1 on up.
Processes will be related to other processes in a hierarchical parent-child tree. Each process will know
who its parent process is. The field called parentsPid is a integer identifying the parent. One parent
may have zero, one, or many child processes. To find the children of process X, we will have to search
all processes for processes whose parentsPid matches X’s pid.
The ProcessControlBlock objects will be more like C structs than full-blown C++/Java objects: the
fields will be accessed from outside the class but the class will not contain many methods of its own.
Other than initializing the object and a couple of print methods, there will be no other methods for
ProcessControlBlock. We are providing the implementations for the Init, Print and PrintShort
methods.
Since we will have only a fixed, small number of ProcesControlBlocks, these are resources which must
be allocated. This is the purpose of the monitor class called ProcessManager.
At start-up time, all ProcessControlBlocks are initially FREE. As user-level processes are created,
these objects will be allocated and when the user-level process dies, the corresponding
ProcessControlBlock will become FREE once again.
In Unix and in our kernel, death is a two stage process. First, an ACTIVE process will execute some
system call (e.g., Exit()) when it wants to terminate. Although the thread will be terminated, the
ProcessControlBlock cannot be immediately freed, so the process will then become a ZOMBIE. At
some later time, when we are done with the ProcessControlBlock it can be FREEd. Once it is FREE, it
is added to the freeList and can be reused when a new process is begun.
The exitStatus is only valid after a process has terminated (e.g., a call to Exit()). So a ZOMBIE process
has a terminated thread and a valid exitStatus. The ZOMBIE state is necessary just to keep the exit
status around. The reason we cannot free the ProcessControlBlock is because we need somewhere to
store this integer.
Project 4 Operating Systems
Page 7
For this project, we will ignore the exitStatus. It need not be initialized, since the default initialization
(to zero) is fine. Also, we will ignore the ZOMBIE state. Every process will be either ACTIVE or
FREE.
Each user-level process will have a virtual address space and this is described by the field addrSpace.
The code we have supplied for ProcessControlBlock.Init will initialize the addrSpace. Although the
addrSpace will not be used in this project, it will be discussed later in this document.
The myThread field will point to the process’s Thread, but we will not set it in this project.
The fileDescriptors field describes the files that this process has open. It will not be used in this
project.
Here is the definition of the ProcessManager object.
class ProcessManager
superclass Object
fields
processTable: array [MAX_NUM_OF_PROCESSES] of ProcessControlBlock
processManagerLock: Mutex
aProcessBecameFree: Condition
freeList: List [ProcessControlBlock]
aProcessDied: Condition
methods
Init ()
Print ()
PrintShort ()
GetANewProcess () returns ptr to ProcessControlBlock
FreeProcess (p: ptr to ProcessControlBlock)
TurnIntoZombie (p: ptr to ProcessControlBlock)
WaitForZombie (proc: ptr to ProcessControlBlock) returns int
endClass
There will be only one ProcessManager and this instance (initialized at start-up time) will be called
processManager.
processManager = new ProcessManager
processManager.Init ()
The Print() and PrintShort() methods for ProcessControlBlocks are provided for you. You are to
implement the methods Init, GetANewProcess, and FreeProcess. The methods TurnIntoZombie and
WaitForZombie will be implemented in a later project and can be ignored for now.
The freeList is a list of all ProcessControlBlocks that are FREE. The status of a ProcessControlBlock
should be FREE if and only if it is on the freeList.
We assume that several threads may more-or-less simultaneously request a new ProcessControlBlock
by calling GetANewProcess. The ProcessManager should be a “monitor,” in order to protect the
freeList from concurrent access. The Mutex called processManagerLock is for that purpose. When a
Project 4 Operating Systems
Page 8
ProcessControlBlock is added to the freeList, the condition aProcessBecameFree can be Signaled to
wake up any thread waiting for a ProcessControlBlock.
Initializing the ProcessControlManager should initialize
the processTable array
all the ProcessControlBlocks in that array
the processManagerLock
the aProcessBecameFree and the aProcessDied condition variables
the freeList
All ProcessControlBlocks should be initialized and placed on the freeList.
The condition called aProcessDied is signaled when a process goes from ACTIVE to ZOMBIE. It will
not be used in this project, but should be initialized nonetheless.
The GetANewProcess method is similar to the GetANewThread method, except that it must also
assign a process ID. In other words, it must set the pid. The ProcessManager will need to manage a
single integer for this purpose. (Perhaps you might call it nextPid). Every time a ProcessControlBlock
is allocated (i.e., everytime GetANewProcess is called), this integer must be incremented and used to
set the process’s pid. GetANewProcess should also set the process’s status to ACTIVE.
The FreeProcess method must change the process’s status to FREE and add it to the free list.
Both GetANewProcess and FreeProcess are monitor entry methods.
Task 3: The Frame Manager
The lower portion of the physical memory of the BLITZ computer, starting at location zero, will contain
the kernel code. It is not clear exactly how big this will be, but we will allocate 1 MByte for the kernel
code. After that will come a portion of memory (called the “frame region”) which will be allocated for
various purposes. For example, the disk controller may need a little memory for buffers and each of the
user-level processes will need memory for “virtual pages.”
The area of memory called the frame region will be viewed as a sequence of “frames”. Each frame will
be the same size and we will have a fixed number of frames. For concreteness, here are some constants
from Kernel.h.
PAGE_SIZE = 8192 — in hex: 0x00002000
PHYSICAL_ADDRESS_OF_FIRST_PAGE_FRAME = 1048576 — in hex: 0x00100000
NUMBER_OF_PHYSICAL_PAGE_FRAMES = 512 — in hex: 0x00000200
This results in a frame region of 4 MB, so our kernel would fit into a 5 MByte memory.
Project 4 Operating Systems
Page 9
The frame size and the page size are the same, namely 8K. In later projects, each frame will hold a page
of memory. For now, we can think of each frame as a resource that must be managed. We will not
really do anything with the frames. This is similar to the dice in the gaming parlor and the forks for the
philosophers… we were concerned with allocating them to threads, but didn’t really use them in any
way.
Each frame is a resource, like the dice of the game parlor, or the philosophers’ forks. From time to time,
a thread will request some frames; the frameManager will either be able to satisfy the request, or the
requesting thread will have to wait until the request can be satisfied.
For the purposes of testing our code, we will work with a smaller frame region of only a few frames.
This will cause more contention for resources and stress our concurrency control a little more. (For later
projects, we can restore this constant to the larger value.)
NUMBER_OF_PHYSICAL_PAGE_FRAMES = 27 — For testing only
Here is the definition of the FrameManager class:
class FrameManager
superclass Object
fields
framesInUse: BitMap
numberFreeFrames: int
frameManagerLock: Mutex
newFramesAvailable: Condition
methods
Init ()
Print ()
GetAFrame () returns int — returns addr of frame
GetNewFrames (aPageTable: ptr to AddrSpace, numFramesNeeded: int)
ReturnAllFrames (aPageTable: ptr to AddrSpace)
endClass
There will be exactly one frameManager object, created at kernel start-up time.
frameManager = new FrameManager
frameManager.Init ()
With frames (unlike the ProcessControlBlocks) there is no object to represent each resource. So to
keep track of which frames are free, we will use the BitMap package. Take a look at it. Basically, the
BitMap class gives us a way to deal with long strings of bits. We can do things like (1) set a bit, (2)
clear a bit, and (3) test a bit. We will use a long bit string to tell which frames are in use and which are
free; this is the framesInUse field. For each frame, there is a bit. If the bit is 1 (i.e., is “set”) then the
frame is in use; if the bit is 0 (i.e., is “clear”) then the frame is free.
The frameManager should be organized as a “Monitor class.” The frameManagerLock is used to
make sure only one method at a time is executing in the FrameManager code.
We have provided the code for the Init, Print, and GetAFrame methods; you’ll need to implement
GetNewFrames, , and ReturnAllFrames.
Project 4 Operating Systems
Page 10
The method GetANewFrame allocates one frame (waiting until at least one is available) and returns the
address of the frame. (Since there is never a need to return frames one at a time, there is no
“ReturnOneFrame” method.)
When the frames are gotten, the GetNewFrames method needs to make a note of which frames have
been allocated. It does this by storing the address of each frame it allocates (the address of the first byte
in each frame) into an AddrSpace object.
An AddrSpace object is used to represent a virtual address space and to tell where in physical memory
the virtual pages are actually located. For example, for a virtual address space with 10 pages, the
AddrSpace object will contain an ordered list of 10 physical memory addresses. These are the
addresses of the 10 “frames” holding the 10 pages in the virtual address space. However, the
AddrSpace object contains more information. For each page, it also contains information about
whether the page has been modified, whether the page is read-only or writable, etc. The information in
an AddrSpace object is stored in exactly the format required by the CPU’s memory management
hardware. In later projects, this will allow us to use the AddrSpace object as the current page table for a
running user-level process. At that time, when we switch to a user-level process, we’ll have to tell the
CPU which AddrSpace object to use for its page table. In addition to looking over the code in
AddrSpace, you may want to review the BLITZ architecture manual’s discussion of page tables.
The code in method
GetNewFrames (aPageTable: ptr to AddrSpace, numFramesNeeded: int)
needs to do the following:
(1) Acquire the frame manager lock.
(2) Wait on newFramesAvailable until there are enough free frames to satisfy the request.
(3) Do a loop for each of the frames
for i = 0 to numFramesNeeded-1
(a) determine which frame is free (find and set a bit in the framesInUse BitMap)
(b) figure out the address of the free frame
(c) execute the following
aPageTable.SetFrameAddr (i, frameAddr)
to store the address of the frame which has been allocated
(4) Adjust the number of free frames
(5) Set aPageTable.numberOfPages to the number of frames allocated.
(6) Unlock the frame manager
The code in method
ReturnAllFrames (aPageTable: ptr to AddrSpace)
needs to do more or less the opposite. It can look at aPageTable.numberOfPages to see how many are
being returned. It can then go through the page table and see which frames it possessed. For each, it can
clear the bit.
Project 4 Operating Systems
Page 11
for i = 0 to numFramesReturned-1
frameAddr = aPageTable.ExtractFrameAddr (i)
bitNumber = …frameAddr…
framesInUse.ClearBit(bitNumber )
endFor
It will also need to adjust the number of free frames and “notify” any waiting threads that more frames
have become available.
You’ll need to do a Broadcast, because a Signal will only wake up one thread. The thread that gets
awakened may not have enough free frames to complete, but other waiting threads may be able to
proceed. A broadcast should be adequate, but perhaps after carefully studying the Game Parlor problem,
you will find a more elegant approach which wakes up only a single thread.
Also note that there is a possibility of starvation here. It is possible that one large process will be
waiting for a lot of frames (e.g., 100 frames). Perhaps there are many small processes which free a few
frames here and there, but there are always other small processes that grab those frames. Since there are
never more than a few free frames at a time, the big process will get starved.
This particular scenario for starvation, where processes are competing for frames) is a very real danger
in an OS and a “real” OS would need to ensure that starvation could not happen. However, in our
situation, it is acceptable to provide a solution that risks starvation.
Do not modify the code for the AddrSpace class.
Task 4: Change Condition Variables to Hoare Semantics
The code we have given you for the Signal method in the Condition class uses MESA semantics.
Change the implementation so that it uses Hoare semantics.
With MESA semantics, you tend to see code like this in monitors:
NewResourcesHaveBecomeAvail: Condition
In method A:
…
numberAvail = numberAvail + 1
NewResourcesHaveBecomeAvail.Signal()
…
In method B:
…
while (numberAvail == 0)
NewResourcesHaveBecomeAvail.Wait()
endWhile
…
Project 4 Operating Systems
Page 12
The code in method B contains a while loop because there is a possibility that some other thread has
snuck in between the Signal and the Wait. When method A increments numberAvail, the condition
(“resources are now available for some other thread to use”) has been made true. Method A invokes
Signal to wake up some thread that is waiting for resources. The problem is that some other thread may
have run between the Signal and the reawakening of the Wait in method B. Other threads may have
come in and grabbed all the resources. So when the waiting thread is reawakened, it must always recheck for resources (or more generally, it must check to ensure the condition is still true.)
Unfortunately, the condition may have changed back to false (i.e., no resources are available), so the
thread will have to wait some more.
And with MESA semantics, starvation becomes a bigger problem. What if the thread waits, wakes up,
and then goes back to sleep, over and over. Each time a Signal occurs, some other thread just happens
to get in first and steal the resource. Then the unlucky thread keeps waking up, testing, and going back
into a waiting sleep. This is a very real possibility if you have three threads and they are scheduled in
round-robin fashion. Thread A runs and signals thread C. Thread B runs and takes the resource.
Thread C runs, finds the condition is false and goes back to sleep. Then thread A runs again, and so on.
With Hoare semantics, the thread needing the resources can use code like this:
…
if (numberAvail == 0)
NewResourcesHaveBecomeAvail.Wait()
endIf
…
Once the thread is reawakened, it can be sure that nothing has happened between the Signal and it; it can
be sure that no other thread has gotten into the monitor.
Starvation is easier to ensure against, too. If a thread needs a resource, it waits. We assume the waiting
queue is FIFO, so that the waiting thread will eventually be awakened. And when it wakes, it will
proceed forward, without looping. Therefore, each Signal wakes one thread which proceeds and, given
enough Signals to awaken any thread who went to sleep first, the thread in question will eventually get
awakened.
(Of course starvation-related bugs are still possible! For example, it might be that the code fails to
Signal the condition enough times, leaving some thread waiting forever. The contribution of the
monitor concept is to make it easier to write bug-free code, not to make it impossible to create bugs!)
All further design choices are up to you. We are not providing any testing code at all; you’ll have to
figure out how to test your code.
If you have time, you may go back to the previous tasks to incorporate your Hoare Semantics code in
their solutions, but remember to complete the above tasks before starting on the Hoare Semantics task.
Project 4 Operating Systems
Page 13
Do not modify…
Do not modify any files except:
Kernel.h
Kernel.c
Do not create global variables (except for testing purposes). Do not modify the methods we have
provided.
Policy Concerning Project Deadlines
The previous projects were designed to get you up to speed and to let you know how much time the
programming portion of this class will take. Some of the tasks were intentionally quite difficult, in order
to challenge the ambitious students and to motivate all students to pay close attention to the subtleties of
concurrency problems and their solutions. The previous projects were independent, in the sense your
solution code did not need to be 100% correct in order to continue with the BLITZ kernel project.
Things change with this project. Buggy code in this project is not acceptable and will make it
impossible to complete the future projects.
In particular, you must complete tasks 1, 2 and 3 in this project before you can begin the next project.
You must get your code working and pass the test programs before going on, unlike the previous
projects in which successful completion was not a barrier to moving on. However, task 4 (the Hoare
Semantics task) is somewhat optional, in the sense that this code will not be needed in future projects.
If you are able to complete tasks 1, 2 and 3 on time, then hand in whatever you were able to achieve on
task 4 and move on to the next project. The Hoare Semantics task is provided as an extra challenge; if
you don’t have time for it, then do not allow yourself to fall behind on the next project.
If you are unable to complete tasks 1, 2 and 3, keep working on them until your code works 100%
correctly.
Students who have difficulty completing the projects on time will start to fall behind. Perhaps such a
student can worker a little harder to catch up on the next project and can still get the entire kernel
finished on time. Or perhaps the student will remain behind schedule and will be unable to complete
one or more of the later projects. Such a student will not be able to get the completed kernel working by
the end of the class.
We recommend that your instructor base grades, from this project onward, on program “style” only. We
recommend they simply not accept any programs that fail to work correctly, as defined by our test suite.
If there are problems with the output, the student must finish / fix the code and re-submit it when it is
working correctly, regardless of how long it takes. The final course grade will then be determined in
part by how many of the projects the student was able to complete before the end of the course.
Project 4 Operating Systems
Page 14
Your instructor may alter this policy. Of course, your instructor’s policy takes precedence over what is
written here.
What to Hand In
Please submit hardcopy of your output and hardcopy your new versions of the following files:
Kernel.h
Kernel.c
For both files, please take a colored pen and circle exactly those parts you have added or changed.
Please submit all of Kernel.h.
For Kernel.c, please submit only the pages that have something circled. In other words, please discard
all pages that contain ONLY material that we are distributing. Please keep the remaining pages in order.
Also, if you have modified any part of a method or function, please hand in the entire function, so there
is a little context surrounding your code modifications.
As a second option, which will save on wasted paper, you may perform the deletions with an editor,
instead of discarding physical pages. You can cut out large sections of code, but please indicate where
material has been clipped out. Please replaced deleted material with a line like this
XXXXXXXXXXXXXXXXXXX skipping XXXXXXXXXXXXXXXXXXX
to indicate which lines were removed. But please remember to circle your material with a colored pen.
In the course of testing, you will probably want to modify Main.c; but please hand in output using our
version. In other words, after you are done testing, make a new run using our version of the Main
package and hand in the output it produces.
For the Hoare Semantics task, we are not providing any testing material; you’ll have to devise some tests
on your own. Please hand in something showing how you have tested your code.
Please print your output in a fixed-width font. We don’t want to see output that looks like this:
2 ProcessControlBlock pid=2, status=ACTIVE, parentsPid=0, exitStatus=0, name=”———-“,
addrSpace=
addr entry Logical Physical Undefined Bits Dirty Referenced Writeable Valid
========== ========== ========== ========== ============== =====
========== ========= =====
0x00093174: 0x00100003 0x00000000 0x00100000 YES YES
Project 4 Operating Systems
Page 15
We prefer to see something more like this. Even though the long lines wrap around, at least things still
line up properly.
2 ProcessControlBlock pid=2, status=ACTIVE, parentsPid=0, exitStatus=0, name=”———-
“, addrSpace=
addr entry Logical Physical Undefined Bits Dirty Referenced
Writeable Valid
========== ========== ========== ========== ============== ===== ==========
========= =====
0x00093174: 0x00100003 0x00000000 0x00100000
YES YES
In LARGE BLOCK LETTERS, write your full name on the first page. PLEASE STAPLE ALL
PAGES!
Sample Output
Here is the output produced by our solution code. You should see something similar, if your program
works correctly:
==================== KPL PROGRAM STARTING ====================
Initializing Thread Scheduler…
Initializing Process Manager…
Initializing Thread Manager…
Initializing Frame Manager…
***** THREAD-MANAGER TEST *****
123.4..1562.7839.1041112.13141.15….16….3295.17.8184..76.192010.111315…14..12..161..9.173188..7.19.
52.20….14410.12.91113…616…15571..18320….122..17..10..9161114586157…….4.123.1.18217.13..20…
9.19.516.1411.2..8..110.15.64.12.1618.9.7.132019..11.3.15..14.812..61.9…2.2018..10165.15.78..9…4.112
013.3..191815….714…17.11.151216.194…18.9.102076..11.12..15…14.84191013..93..2…1511518..8.714..
9.616.19..1..2015…813.42.1210.9……520.4.2.181116.14915..4.2.1.1117..5.8.1018.15.2.4.14.9.11..1.56.8
.2.15..4.1410..93..18.2013.2.15..7.17…1210914.8.20.2…..17515123.14.9.20..16.819.12.5.3.15.1.16.14.20
.8.3..513.12.15.18..1.8..209.193.5.6.18.7.8….20.14153.511.12.4.7.8.3.14.15.9.11.12…1518.16.3..14..11
17.12..4.5..1710..14.26.1.7..123.16.8.19.17.6.20.2.10..12.165.3.19.1.17..4…6.8.1220216.19..7.13.13.6.1
1.19.16..20.4.2.1.7..13.6.11.17.19..16.14.7..1….18….1013619.16.1711.4.7.20..13.18.16.19.10.6.17..411
.7..13.18.19…17.10.6..7.13..1918.17.10.6…..131817.19.106.13..17…10.13.17..13..
***** THREAD-MANAGER TEST COMPLETED SUCCESSFULLY *****
***** PROCESS-MANAGER TEST *****
123.4..1562783.9.104…1…11.738.12132149.156.5.1016.17..184…19..201.11138.714.12.3….5.26.17164.3.2
0.19..1812..629.14..1015…17.137..16.84.1820.1912…116.15.14…..572.3.89.116….10417513..15.12.1814.
..23..19.716.1204.1511…14..5..9.6131237..162….18.10.1718..5..1119.61620….9184..13.17..14108….612
711.159..2..11317….20.11..16..7146.119515.10.4.168…714..11.92.12.1..181720..14..6319…1219..7.168..
.2513…411.15..129.181.14..19.32.4..6.15.128.16..19.1410.5.20.9.7..46.16.11.3.13.17.14.9.8.7.1.16.2..5.
.192010.9.7..164.1.11…31317.5.9.7.6.12…19.13.11.20161.5.7.12.19.3.6..1110..113.5.12..719.11.6.2.3.20
.16.12.5.19.11.6..207.2..9.1416.5.19.15.6.11.20.2.14.9.12.4.5.17..1118.20.2.14.9…12.5154.11.20.6..152.
.18.16.14.10.5.20..63.17..9.102.1.14.11.18.13.10…739.2.16.20.14.11.10.8.3..76.16..20.13…8.3…18….
12194.10.138.3…918..20.1310..124.19.3.1.15.17.13..4.14.10.12…20.8..1913.4.17.10..18.8…13.19.17.4.1
8.15.8.10.17.13.19.18..15.8.18.17.10…15.8.18.17.15…18.17.15.18.17.15.18..15..15.
***** PROCESS-MANAGER TEST COMPLETED SUCCESSFULLY *****
Project 4 Operating Systems
Page 16
***** FRAME-MANAGER TEST *****
1234.57.68.9110…32.5..74…8.69..101.32.45.7…..6.9.8.310215.4……10967138…2…5107.946…1.25..3
8.9..10.64..79.21..5..710.8.1.3.9.2..684.19..5..6310..48..9..65.1.7.53..2.8..93.10..12.47..1..4.1086..11
0..48.6..35..9.710..9.85.3..4.78.6..310.4.7.3..58.10.6..94.1..37.8..6.92.5..74..12.4.2.3.1..5.26.10.3.1.
7.5.8.10.3.1.9.6.8.10.3.1.4.6.10.8.3..31…134…513..1.83…3101..43..81..8..93.8.4..1.8.34..17.8.3.2.1
.4.8.6.4.2.8.47…83.1.5.34..1.84.3.1..84..28..10..4107…4110..5.410..18.3.1.8.3..41..105..8..4510…71
05..610..75..71…1085..7..410.75…175..9.75.10..58.7..4.52.7.6..7.6.5.4.10.85..10.6.7.47..5..106.7.510
.7..56..26..69..2..652..28.6.1.2..36..52..36..7.29…912..97..16…10.129..76…139..7.91..24..79..101..
82.6..91.2.6.9..71..93..61.10.9.1..62.8…298..810..48.1..6.810..1.210..8.510.8..110..9.8.10..2810..98..
710..79.8..7.210.6…27.109.8…1017.2.10.7.8.10.7..47.10.8.1.10..48.7..4.17..84.5.4.1.7..8.45.4..58.4..
7.5.104..56…56.4..765..10.5.67.4..9.5.6.7.5.6.45.8.6.4.7.6.1.5.9.6..26..105.4.6.10.2..23..3.1.23..6.5.
23…623.10.2.6..54.2..5.3.26.3.7.2.3.1.3.1.9.2…613..41.10…1410..10.6.1.104.1..9.10..219….31019.7.
.10.93..10.1.910..32.1.3..109.2.5.1.2.3.10..97.1.10.5.9.4.9.1.2.10.3.9.2.9..110..93.9.1.7..71.7..27.5.7.
4.7..42..7.410.7..48…18.75..87.10..4.8.2.8.46.7…984.5.8..9.5..74.58..10.54..7.8.5.47.8..65.4.7..5.84
.5.1.5.4.9.5.3.5.8..95.6.6..10.65.8.7.6..26…926..72..6.2.54.2.3.6..102..56.10.2…7610…8610.1..2..11
0.4..1210.6..5.101.9..21.6..110.2..410..81.4.10..71..410.8.2.6.1.7..76.10.5.1..7.10.2.71..106.1..102.7.1
0.1.2.7..74.7..57.9..95.9..39..5..931..57..3.6..39.510.7..2.95.8.7…1039.2.9.8.9..2.5.310.5.2.5.7.9.1..
73.5..54..5.1.43.10.4.2…3.25.4.9..34.25.9..34.5..79..2.3.4.21.4.7.3.5..24.9..3.52.3.4.5.2..82.6.2.5.4.
7.2..94..3.2.9.6.1.6..69.6..56.7.6.4.2..46.9..46.9.6..3.69..49.6..92.6..39.5.9.3.9..9..79.8.8.1.9..86.2.
.89.6..29.6..89.8.2.8..96.8..8.6.8..98.4.8.9.8.4.8.6.8.4.8.6..3..3.2.3..93.8.3..63..83.9.3..3.2.3.8.9…
3..3.3.3.3.3.3.3.3.
Here is a histogram showing how many times each frame was used:
0:
********************************************************************************************************
********************************************************************************************************
********************************************************************************************************
********************************************************************************************************
**********
1:
********************************************************************************************************
********************************************************************************************************
********************************************************************************************************
********************************************************************************************************
**********
2:
********************************************************************************************************
********************************************************************************************************
********************************************************************************************************
********************************************************************************************************
**********
XXXXXXXXXXXXXXXXXXX skipping XXXXXXXXXXXXXXXXXXX
24:
********************************************************************************************************
********************************************************************************************************
*
25:
********************************************************************************************************
***************************************************************************
26:
********************************************************************************************************
*****
***** FRAME-MANAGER TEST COMPLETED SUCCESSFULLY *****
==================== KPL PROGRAM TERMINATION ====================
Project 4 Operating Systems
Page 17
Coding Style
For all projects, please follow our coding style. Make your code match our code as closely as possible.
The goal is for it to be impossible to tell, just by looking at the indentation and commenting, whether we
wrote the code or you wrote the code. (Of course, your code will be circled!)
Please use our convention in labeling and commenting functions:
—————————– Foo ———————————
function Foo ()
—
— This routine does….
—
var x: int
x = 1
x = 2
…
x = 9
endFunction
Methods are labeled like this, with both class and method name:
———- Condition . Wait ———-
method Wait (mutex: ptr to Mutex)
…
Note that indentation is in increments of 2 spaces. Please be careful to indent statements such as if,
while, and for properly.

Overview and Goal
In this project, you will explore user-level processes. You will create a single process, running in its
own address space. When this user-level process executes, the CPU will be in “user mode.”
The user-level process will make system calls to the kernel, which will cause the CPU to switch into
“system mode.” Upon completion, the CPU will switch back to user mode before resuming execution of
the user-level process.
The user-level process will execute in its own “logical address space.” Its address space will be broken
into a number of “pages” and each page will be stored in a frame in memory. The pages will be resident
(i.e., stored in frames in physical memory) at all times and will not be swapped out to disk in this
project. (Contrast this with “virtual” memory, in which some pages may not be resident in memory.)
The kernel will be entirely protected from the user-level program; nothing the user-level program does
can crash the kernel.
Download New Files
The files for this project are available in:
https://www.cs.pdx.edu/~harry/Blitz/OSProject/p5/
Please retain your old files from previous projects and don’t modify them once you submit them.
You should get the following files:
Switch.s
Runtime.s
System.h
System.c
Project 5 Operating Systems
Page 2
List.h
List.c
BitMap.h
BitMap.c
makefile
FileStuff.h
FileStuff.c
Main.h
Main.c
DISK
UserRuntime.s
UserSystem.h
UserSystem.c
MyProgram.h
MyProgram.c
TestProgram1.h
TestProgram1.c
TestProgram2.h
TestProgram2.c
The following files are unchanged from the last project and you should not modify them:
Switch.s
Runtime.s
System.h
System.c — except HEAP_SIZE has been modified
List.h
List.c
BitMap.h
BitMap.c
The following files are not provided; instead you will modify what you created in the last project. Copy
these files to your p5 directory, so that you keep the previous p4 versions in your p4 directory, and
modify the new copies.
Kernel.h
Kernel.c
Merging New “File Stuff” Code
For this project, we are distributing additional code which you should add to the Kernel package.
Please add the material in FileStuff.c to the end of file Kernel.c. It should be inserted directly before
the final endCode keyword.
Project 5 Operating Systems
Page 3
Also, please add the material in FileStuff.h to the end of file Kernel.h. It should be inserted directly
before the final endHeader keyword.
This code adds the following classes:
DiskDriver
FileManager
FileControlBlock
OpenFile
You will use these classes, but you should not modify them.
There will be a single DiskDriver object (called diskDriver) which is created and initialized at start-up
time. There will be a single FileManager object (called fileManager) which is created and initialized
at start-up time. The new main function contains statements to create and initialize the diskDriver and
the fileManager objects.
FileControlBlock and OpenFile objects will be handled much like Threads and
ProcessControlBlocks. They are a limited resource. A limited supply is created at start-up time and
then they are managed by the fileManager. There is a free list of FileControlBlock objects and a free
list of OpenFile objects. The fileManager oversees both of these free lists. Threads may make
requests and may return resources, by invoking methods in the fileManager.
The diskDriver object encapsulates all the hardware specific details of the disk. It provides a method
that allows a thread to read a sector from disk into a memory frame and it provides a method that writes
a frame from memory to a sector on disk.
Other Changes To Your Kernel Code
Please make the following changes to your copy of Kernel.h:
Change
NUMBER_OF_PHYSICAL_PAGE_FRAMES = 27 — for testing only
to:
NUMBER_OF_PHYSICAL_PAGE_FRAMES = 100 — for testing only
Change
–diskDriver: DiskDriver
–fileManager: FileManager
to:
diskDriver: DiskDriver
fileManager: FileManager
Project 5 Operating Systems
Page 4
Add a function prototype for the function InitFirstProcess. You can add it after the other function
prototypes:
Change
ProcessFinish (exitStatus: int)
to:
ProcessFinish (exitStatus: int)
InitFirstProcess ()
Please make the following changes to your copy of Kernel.c:
Change the DiskInterruptHandler function from:
FatalError (“DISK INTERRUPTS NOT EXPECTED IN PROJECT 4”)
to:
currentInterruptStatus = DISABLED
— print (“DiskInterruptHandler invoked!
”)
if diskDriver.semToSignalOnCompletion
diskDriver.semToSignalOnCompletion.Up()
endIf
Task 1:
Your first task is to load and execute the user-level program called MyProgram. Since the user-level
program must be read from a file on the BLITZ disk, you’ll first need to understand how the BLITZ disk
works, how files are stored on the disk, and how the FileManager code works.
MyProgram invokes the SystemShutdown syscall, which you’ll need to implement.
Task 2:
Modify all the syscall handlers so they print the arguments that are passed to them. In the case of
integer arguments, this should be straightforward, but the following syscalls take a pointer to an array of
char as one of their arguments.
Exec
Create
Open
This pointer is in the user-program’s logical address space. You must first move the string from userspace to a buffer in kernel space. Only then can it be safely printed.
Project 5 Operating Systems
Page 5
Also, some of the syscalls return a result. You must modify the handlers for these syscalls so that the
following syscalls return these values. (These are just arbitrary values, to make sure you can return
something.)
Fork 1000
Join 2000
Exec 3000
Create 4000
Open 5000
Read 6000
Write 7000
Seek 8000
For this task, you should modify only the handler methods (e.g., Handle_Sys_Fork, Handle_Sys_Join,
etc.) You should not modify SyscallTrapHandler or the wrapper functions in UserSystem.
Task 3:
Implement the Exec syscall. The Exec syscall will read a new executable program from disk and copy
it into the address space of the process which invoked the Exec. It will then begin execution of the new
program. Unless there are errors, there will not be a return from the Exec syscall.
The User-Level View
First, let’s look at our operating system from the users’ point of view. User-level programs will be able
to invoke the following kernel routines:
Exit
Shutdown
Yield
Fork
Join
Exec
Create
Open
Read
Write
Seek
Close
(This is the grand plan for our OS; these system calls will not be implemented in this project.)
Project 5 Operating Systems
Page 6
These syscalls are quite similar to kernel syscalls of the same names in Unix. We describe their precise
functionality later.
A user-level program will be written in KPL and linked with the following files:
UserSystem.h
UserSystem.c
UserRuntime.s
We are providing a sample user-level program in MyProgram.h / .c.
The UserSystem package includes a wrapper (or “jacket”) function for each of the system calls. Here
are the names of the wrapper functions. There is a one-to-one correspondence between the system calls
and the wrapper functions.
System call Wrapper function name
Exit Sys_Exit
Shutdown Sys_Shutdown
Yield Sys_Yield
Fork Sys_Fork
Join Sys_Join
Exec Sys_Exec
Create Sys_Create
Open Sys_Open
Read Sys_Read
Write Sys_Write
Seek Sys_Seek
Close Sys_Close
(In Unix, the wrapper function often has the same name as the syscall. All wrapper functions have
names beginning with Sys_ just to help make the distinction between wrapper and syscall.)
Each wrapper function works the same way. It invokes an assembly language routine called DoSyscall,
which executes a “syscall” machine instruction. When the kernel call finishes, the DoSyscall function
simply returns to the wrapper function, which returns to the user’s code.
Arguments may be passed to and from the kernel call. In general, these are integers and pointers to
memory. The wrapper function works with DoSyscall to pass the arguments. When the wrapper
function calls DoSyscall, it will push the arguments onto the stack. The DoSyscall will take the
arguments off the stack and move them into registers. Since it runs as a user-level function, it places
them in the “user” registers. (Recall that the BLITZ machine has a set of 16 “system registers” and a set
of 16 “user registers.”)
Each wrapper function also uses an integer code to indicate which kernel function is involved. Here is
the enum giving the different codes. For example, the code for “Fork” is 4.
Project 5 Operating Systems
Page 7
enum SYSCALL_EXIT = 1,
SYSCALL_SHUTDOWN,
SYSCALL_YIELD,
SYSCALL_FORK,
SYSCALL_JOIN,
SYSCALL_EXEC,
SYSCALL_CREATE,
SYSCALL_OPEN,
SYSCALL_READ,
SYSCALL_WRITE,
SYSCALL_SEEK,
SYSCALL_CLOSE
These code numbers are used both by the user-level program and by the kernel. Consequently, there is
an identical copy of this enum in both Kernel.h and UserSystem.h. (You should not change the system
call interface, but if one were to change these code numbers, it would be critical that both enums were
changed identically.)
As an example, here is the code for the wrapper function for “Read.” It simply invokes DoSyscall and
returns whatever DoSyscall returns.
function Sys_Read (fileDesc: int,
buffer: ptr to char,
sizeInBytes: int) returns int
return DoSyscall (SYSCALL_READ,
fileDesc,
buffer asInteger,
sizeInBytes,
0)
endFunction
Here is the function prototype for DoSyscall:
external DoSyscall (funCode, arg1, arg2, arg3, arg4: int) returns int
The DoSyscall routine is set up to deal with up to 4 arguments. Since the Read syscall only needs 3
arguments, the wrapper function must supply an extra zero for the fourth argument.
DoSyscall treats all of its arguments as untyped words (i.e., as int), so the wrapper functions must
coerce the types of the arguments if they are not int. Whatever DoSyscall returns, the wrapper function
will return.
DoSyscall is in UserRuntime.s, which will be linked with all user programs. The code is given next.
It moves each of the 4 arguments into registers r1, r2, r3, and r4. It then moves the function code into
register r5 and executes the syscall instruction. It assumes the kernel will place the result (if any) in r1,
so after the syscall instruction, it moves the return value from r1 to the stack, so that the wrapper
function can retrieve it.
Project 5 Operating Systems
Page 8
DoSyscall:
load [r15+8],r1 ! Move arg1 into r1
load [r15+12],r2 ! Move arg2 into r2
load [r15+16],r3 ! Move arg3 into r3
load [r15+20],r4 ! Move arg4 into r4
load [r15+4],r5 ! Move funcCode into r5
syscall r5 ! Do the syscall
store r1,[r15+4] ! Move result from r1 onto stack
ret ! Return
Some of the kernel routines require no arguments and/or return no result. As an example, consider the
wrapper function for Yield. The compiler knows that DoSyscall returns a result, so it insists that we do
something with this value. The wrapper function simply moves it into a variable and ignores it.
function Sys_Yield ()
var ignore: int
ignore = DoSyscall (SYSCALL_YIELD, 0, 0, 0, 0)
endFunction
Here is a list of all the wrapper functions, including their arguments and return types.
Sys_Exit (returnStatus: int)
Sys_Shutdown ()
Sys_Yield ()
Sys_Fork () returns int
Sys_Join (processID: int) returns int
Sys_Exec (filename: String) returns int
Sys_Create (filename: String) returns int
Sys_Open (filename: String) returns int
Sys_Read (fileDesc: int, buffer: ptr to char, sizeInBytes: int)
returns int
Sys_Write (fileDesc: int, buffer: ptr to char, sizeInBytes: int)
returns int
Sys_Seek (fileDesc: int, newCurrentPos: int) returns int
Sys_Close (fileDesc: int)
In addition to the wrapper functions, the UserSystem package contains a few other routines that support
the KPL language. These are more-or-less duplicates of the same routines in the System package.
Likewise, some of the material from Runtime.s is duplicated in UserRuntime.s. This duplication is
necessary because user-level programs cannot invoke any of the routines that are part of the kernel.
For example the functions print, printInt, nl, etc. have been duplicated at the user level so the userlevel program has the ability to print.
[Note that, at this point, all printing is done by cheating, using a “trapdoor” in the emulator. Normally, a
user-level program would need to invoke syscalls (such as Sys_Write) to perform any output, since
user-level programs can’t access the I/O devices directly. However, since we are not yet ready to
address questions about output to the serial device, we are including these cheater print functions, which
rely on a trapdoor in the emulator.]
Every user-level program needs to “use” the UserSystem package and be linked with the
UserRuntime.s code. For example:
Project 5 Operating Systems
Page 9
MyProgram.h
header MyProgram
uses UserSystem
functions
main ()
endHeader
MyProgram.c
code MyProgram
function main ()
print (“My user-level program is running!
”)
Sys_Shutdown ()
endFunction
endCode
Here are the commands to prepare a user-level program for execution. The makefile has been modified
to include these commands.
asm UserRuntime.s
comp UserSystem -unsafe
asm UserSystem.s
comp MyProgram -unsafe
asm MyProgram.s
lddd UserRuntime.o UserSystem.o MyProgram.o -o MyProgram
Note that there is no connection with the kernel. The user-level programs are compiled and linked
independently. All communication with the kernel will be through the syscall interface, via the wrapper
functions.
This is exactly the way Unix works. For user-level programs, library functions and wrapper functions
are brought into the “a.out” file at link-time, as needed. This explains why a seemingly small “C”
program can produce a rather large “a.out” executable. One small use of printf in a program might pull
in, at link-time, more output formatting and buffering routines than you can possibly imagine.
When an OS wants to execute a user-level program, it will go to a disk file to find the executable. Then
it will read that executable into memory and start up the new process.
In order to execute MyProgram, we need to introduce the BLITZ “disk.” The disk is simulated with a
Unix file called “DISK.” After the user-level program is compiled, it must be placed on the BLITZ disk
with the following Unix commands:
diskUtil -i
diskUtil -a MyProgram MyProgram
The first command creates an empty file system on the disk. The second command copies a file from
the Unix file system to the BLITZ disk. It creates a directory entry and moves the data to the proper
place on the simulated BLITZ disk. Commands to initialize the BLITZ disk have also been added to the
makefile.
Project 5 Operating Systems
Page 10
Once the kernel is running, it will read the file from the simulated BLITZ disk and copy it into memory.
The Syscall Interface
In our OS, each process will have exactly one thread. A process may also have several open files and
can do I/O via the Read and Write syscalls. The I/O will go to the BLITZ disk. For now, there is no
serial (i.e., terminal) device.
Next we describe each syscall in more detail.
function Sys_Exit (returnStatus: int)
This function causes the current process and its thread to terminate. The returnStatus will be
saved so that it can be passed to a Sys_Join executed by the parent process. This function never
returns.
function Sys_Shutdown ()
This function will cause an immediate shutdown of the kernel. It will not return.
function Sys_Yield ()
This function yields the CPU to another process on the ready list. Once this process is scheduled
again, this function will return. From the caller’s perspective, this routine is similar to a “nop.”
function Sys_Fork () returns int
This function creates a new process which is a copy of the current process. The new process will
have a copy of the virtual memory space and all files open in the original process will also be
open in the new process. Both processes will then return from this function. In the parent
process, the pid of the child will be returned; in the child, zero will be returned.
function Sys_Join (processID: int) returns int
This function causes the caller to wait until the process with the given pid has terminated, by
executing a call to Sys_Exit. The returnStatus passed by that process to Sys_Exit will be
returned from this function. If the other process invokes Sys_Exit first, this returnStatus will
be saved until either its parent executes a Sys_Join naming that process’s pid or until its parent
terminates.
function Sys_Exec (filename: String) returns int
This function is passed the name of a file. That file is assumed to be an executable file. It is read
in to memory, overwriting the entire address space of the current process. Then the OS will
Project 5 Operating Systems
Page 11
begin executing the new process. Any open files in the current process will remain open and
unchanged in the new process. Normally, this function will not return. If there are problems, this
function will return -1.
function Sys_Create (filename: String) returns int
This function creates a new file on the disk. If all is okay, it returns 0, otherwise it returns a nonzero error code. This function does not open the file; so the caller must use Sys_Open before
attempting any I/O.
function Sys_Open (filename: String) returns int
This function opens a file. The file must exist already exist. If all is OK, this function returns a
file descriptor, which is a small, non-negative integer. It errors occur, this function returns -1.
function Sys_Read (fileDesc: int, buffer: ptr to char, sizeInBytes: int) returns int
This function is passed the fileDescriptor of a file (which is assumed to have been successfully
opened), a pointer to an area of memory, and a count of the number of bytes to transfer. This
function reads that many bytes from the current position in the file and places them in memory.
If there are not enough bytes between the current position and the end of the file, then a lesser
number of bytes are transferred. The current file position will be advanced by the number of
bytes transferred.
If the input is coming from the serial device (the terminal), this function will wait for at least one
character to be typed before returning, and then will return as many characters as have been
typed and buffered since the previous call to this function.
This function will return the number of characters moved. If there are errors, it will return -1.
function Sys_Write (fileDesc: int, buffer: ptr to char, sizeInBytes: int) returns int
This function is passed the fileDescriptor of a file (which is assumed to have been successfully
opened), a pointer to an area of memory, and a count of the number of bytes to transfer. This
function writes that many bytes from the memory to the current position in the file.
If the end of the file is reached, the file’s size will be increased.
The current file position will be advanced by the number of bytes transferred, so that future
writes will follow the data transferred in this invocation.
The output may also be directed to the serial output, i.e., to the terminal.
This function will return the number of characters moved. If there are errors, it will return -1.
Project 5 Operating Systems
Page 12
function Sys_Seek (fileDesc: int, newCurrentPosition: int) returns int
This function is passed the fileDescriptor of a file (which is assumed to have been successfully
opened), and a new current position. This function sets the current position in the file to the
given value and returns the new current position.
Setting the current position to zero causes the next read or write to refer to the very first byte in
the file. If the file size is N bytes, setting the position to N will cause the next write to append
data to the end of the file.
The current position is always between 0 and N, where N is the file’s size in bytes.
If -1 is supplied as the new current position, the current position will be set to N (the file size in
bytes) and N will be returned.
It is an error to supply a newCurrentPosition that is less than -1 or greater than N. If so, -1 will
be returned.
function Sys_Close (fileDesc: int)
This function is passed the fileDescriptor of a file, which is assumed to be open. It closes the
file, which includes writing out any data buffered by the kernel.
Asynchronous Interrupts
From time-to-time an asynchronous interrupt will occur. Consider a DiskInterrupt as an example.
When this happens, an assembly routine called DiskInterruptHandler in Runtime.s will be jumped to.
It begins by saving the system registers (after all, a Disk Interrupt might occur while a kernel routine is
executing and we’ll need to return to it). Then DiskInterruptHandler performs an “upcall” to the
function named DiskInterruptHandler in Kernel.c. Perhaps it is a little confusing to have an assembly
routine and a KPL routine with the same name, but, oh well…
The high-level DiskInterruptHandler routine simply signals a semaphore and returns to the assembly
DiskInterruptHandler routine, which restores the system registers and returns to whatever code was
interrupted. All the time while these routines are running, interrupts are disabled and no other interrupts
can occur.
Also note that the interrupt handler uses space on the system stack of whichever thread was interrupted.
It might be that some unsuspecting user-level code was running. Although the interrupt handler will use
the system stack of that thread, the thread will be none-the-wiser. While the interrupt handler is running,
it is running as part of some more-or-less randomly selected thread. The interrupt handler is not a thread
on its own.
Project 5 Operating Systems
Page 13
Error Exception Handling
When a runtime error is detected by the CPU, the CPU performs exception processing, which is similar
to the way it processes an interrupt. Here are the sorts of runtime errors that can occur in the BLITZ
architecture:
Illegal Instruction
Arithmetic Exception
Address Exception
Page Invalid Exception
Page Read-only Exception
Privileged Instruction
Alignment Exception
As an example, consider what happens when an Alignment Exception occurs. (The others are handled
the same way.)
The CPU will consult the interrupt vector in low memory (see Runtime.s) and will jump to an assembly
language routine called AlignmentExceptionHandler. The assembly routine first checks to see if the
interrupted code was executing in system mode or not. If it was in system mode, then the assumption is
that there is a bug in the kernel, so the assembly routine prints a message and halts execution.
However, if the CPU was in user mode, the assumption is that the user-level program has a bug. The
OS will need to handle that bug without itself stopping. So the assembly AlignmentExceptionHandler
routine makes an upcall to a KPL routine with the same name.
The high-level AlignmentExceptionHandler routine simply prints a message and terminates the
process. Process termination is performed in a routine called ProcessFinish, which is not yet written.
(For now, we’ll assume that user-level programs do not have any bugs.)
When ProcessFinish is implemented in a later project, it will need to return the ProcessControlBlock
(PCB) to the free pool. It will also need to free any additional resources held by the process, such as
OpenFile objects. Of course, any open files will need to be closed first. Finally, ProcessFinish will
call ThreadFinish and will not return.
(Note that a Thread object cannot be added back to the free thread pool by the thread that is running.
Instead, in ThreadFinish the thread is added to a list called threadsTobeDestroyed. Later, after
another thread begins executing (in Run) the first thing it will do is add any threads on that list back to
the free pool by calling threadManager.FreeThread.)
Project 5 Operating Systems
Page 14
Syscalls
When a user-level thread executes a syscall instruction, the assembly routine SyscallTrapHandler in
Runtime.s will be invoked. The assembly routine will then call a KPL routine with the same name.
The assembly routine does not need to save registers because the interrupted code was executing in user
mode and the handler will be executed in system mode.
Recall that just before the syscall, the DoSyscall routine placed the arguments in the (user) registers r1,
r2, r3, and r4, with an integer indicating which kernel function is wanted in register r5. The
SyscallTrapHandler assembly routine takes the values from the user registers. Since it is running in
system mode, it must use a special instruction called “readu” to get values from the user registers. It
pushes them on to the system stack so that the high-level routine can access them. Then it calls the
high-level SyscallTrapHandler routine. When the high-level routine returns, it takes the returned
value from the stack and moves it into user register r1, using an instruction called “writeu,” and then
executes a “reti” instruction to return to the interrupted user-level process. Execution will resume back
in DoSyscall directly after the “syscall” instruction.
The high-level routine called SyscallTrapHandler simply takes a look at the function code and calls the
appropriate routine to finish the work. For every kind of syscall, there is a corresponding “handler
routine” in the OS.
System call Handler function in the kernel
Exit Handle_Sys_Exit
Shutdown Handle_Sys_Shutdown
Yield Handle_Sys_Yield
Fork Handle_Sys_Fork
Join Handle_Sys_Join
Exec Handle_Sys_Exec
Create Handle_Sys_Create
Open Handle_Sys_Open
Read Handle_Sys_Read
Write Handle_Sys_Write
Seek Handle_Sys_Seek
Close Handle_Sys_Close
It is these routines that you will need to implement, in this and other projects.
Note that interrupts will be disabled when the SyscallTrapHandler routine begins. The first thing the
high-level routine does is set the global variable currentInterruptStatus to DISABLED so that it is
accurate. In fact, all the interrupt and exception handlers begin by setting currentInterruptStatus to
DISABLED for this reason.
Also note that after the handler routines return to the interrupted routine, interrupts will be re-enabled.
Why? Because the Status Register in the CPU will be restored as part of the operation of the reti
instruction, restoring the interrupt (and paging and system mode) status bits to what they were when the
Project 5 Operating Systems
Page 15
interrupt occurred. (Note that we do not bother to change currentInterruptStatus to ENABLED
before returning to user-level code, because any re-entry to the kernel code must be through
SyscallTrapHandler, or an interrupt or exception handler, and each of these begins by setting
currentInterruptStatus.)
Implementing the Shutdown syscall is straightforward. The handler should call FatalError with the
following message:
Syscall ‘Shutdown’ was invoked by a user thread
The BLITZ Disk
The BLITZ computer includes a disk which is emulated using a file called DISK on the host computer.
In other words, a write to the BLITZ disk will cause data to be written to a Unix file and a read from the
BLITZ disk will cause a read from the Unix file. The emulator will simulate the delays involved in
reading, by taking account of the current (simulated) disk head position. When the I/O is complete—
that is the simulated time when the emulator has calculated the disk I/O will have completed—the
emulator causes a DiskInterrupt to occur.
To interface with the BLITZ disk, we have supplied a class called DiskDriver, which makes it
unnecessary for you to write the code that actually reads and writes disk sectors. You can just use the
code in the class DiskDriver. There is only one DiskDriver object; it is created and initialized at
startup time.
class DiskDriver
superclass Object
fields
…
semToSignalOnCompletion: ptr to Semaphore
semUsedInSynchMethods: Semaphore
diskBusy: Mutex
methods
Init ()
SynchReadSector (sectorAddr, numberOfSectors, memoryAddr: int)
StartReadSector (sectorAddr, numberOfSectors, memoryAddr: int,
whoCares: ptr to Semaphore)
SynchWriteSector (sectorAddr, numberOfSectors, memoryAddr: int)
StartWriteSector (sectorAddr, numberOfSectors, memoryAddr: int,
whoCares: ptr to Semaphore)
endClass
This class provides a way to read and write sectors synchronously as well as a way to read and write
sectors asynchronously.
To perform a disk operation without blocking the calling thread, you can call StartReadSector or
StartWriteSector. These methods are passed the number of the sector on the disk at which to begin the
transfer, the number of sectors to transfer and the location in memory to transfer the data to or from.
Project 5 Operating Systems
Page 16
These methods are also passed a pointer to a Semaphore; upon completion of the operation (possibly in
error!) this semaphore will be signaled with an Up() operation. This is exactly the semaphore that is
signaled whenever a DiskInterrupt occurs. So to perform asynchronous I/O, the caller will invoke
StartReadSector (or StartWriteSector) giving it a Semaphore. Then the caller can either do other
stuff, or wait on the Semaphore.
Since it may be a little tricky to manage asynchronous I/O correctly, the DiskDriver class also provides
a couple of methods to make it easy to do I/O synchronously.
When you call SynchReadSector or SynchWriteSector, the caller will be suspended and will be
returned to only after a successful completion of the I/O. These routines will deal with transient errors
by retrying the operation until it works. Other errors (such as a bad sectorAddr or bad memoryAddr)
will be dealt with by a call to FatalError.
In order to implement these methods, the DiskDriver contains a mutex called diskBusy and a
semaphore called SemUsedInSynchMethods. Each synch method makes sure the disk is not busy with
I/O from some other thread and, if so, waits until it is completed. This is the purpose of the diskBusy
mutex. After acquiring the lock, each synch method will call StartReadSector (or StartWriteSector)
supplying the semaphore. The synch method will then wait until the disk operation is complete. The
calling thread will remain blocked for the duration.
The “Stub” File System
As a later project, you might want to implement a full file system, more like the one used by Unix
systems. For now, you are supplied with a very minimal file system, called the “stub” file system. In
Unix, directories are structured in a tree shape and there are lots of complexities concerning how files
are stored on the disk.
In the stub file system, the disk will contain only one directory, and several files. The directory is
limited in size to one sector and is kept in sector 0 of the disk. The exact number of files that can be
accommodated depends on how long the file names are.
Each file has a name and a file length (in bytes). Each file is stored on disk in a sequence of consecutive
sectors. Once a file is placed on the disk, and more files are added after it, it is impossible to increase
the size of the file. Each file is allocated an integral number of sectors. (Since the last sector in each file
may be only partially full, it would be possible to increase the size of a file up to the next sector
boundary. However, it is not worth the effort. Instead, the solution is to design a better file system!)
For now, the directory is read-only, so files may not be created and the size of files may not be changed.
The classes FileManager, FileControlBlock, and OpenFile are provided for you, to make it easier to
use the file system from within the kernel.
Project 5 Operating Systems
Page 17
The “diskUtil” Tool
The BLITZ tool called diskUtil can be used to create a file system on the BLITZ disk, to add files to the
disk, to remove files, and to print out the directory.
The BLITZ DISK is organized as follows. The disk contains a single directory and this is kept in sector
0. The files are placed sequentially on the disk, one after the other. Each file will take up an integral
number of sectors. Each file has an entry in the directory. Each entry contains
(1) The starting sector
(2) The file length, in bytes (possibly zero)
(3) The number of characters in the file name
(4) The file name
The directory begins with three numbers:
(1) Magic Number (0x73747562 = “stub”)
(2) Number of files (possibly zero)
(3) Number of the next free sector
These are followed by the entries for each file.
Once created, a BLITZ file may not have its size increased. When a file is removed, the free sectors
become unusable; there is no compaction or any attempt to reclaim the lost space.
Each time the diskUtil program is run, it performs one of the following functions:
Initialize set up a new file system on the BLITZ disk
List list the directory on the BLITZ disk
Create create a new file of a given size
Remove remove a file
Add copy a file from Unix to BLITZ
Extract copy a file from BLITZ to Unix
Write write sectors from a Unix file to the BLITZ disk
The following command line options tell which function is to be performed by diskUtil:
-h
Print help info.
-d DiskFileName
The file used to emulate the BLITZ disk. If missing, “DISK” will be used.
Project 5 Operating Systems
Page 18
-i
Initialize the file system on the BLITZ “DISK” file. This will
effectively remove all files on the BLITZ disk and reclaim all available
space.
-l
List the directory on the BLITZ disk.
-c BlitzFileName SizeInBytes
Create a file of the given size on the BLITZ disk. The BLITZ
disk must not already contain a file with this name. Only the
directory will be modified; the actual data in the file will be
whatever bytes happened to be on the disk already.
-r BlitzFileName
Remove the file with the given name from the directory on the BLITZ disk.
-a UnixFilename BlitzFileName
Copy a file from Unix to the BLITZ disk. If BlitzFileName already
exists, it must be large enough to accommodate the new data.
-e BlitzFileName UnixFileName
Extract a file from the BLITZ disk to Unix. This command will copy
the data from the BLITZ disk to a Unix file. The Unix file may or may
not already exist; its size will be shortened or lengthened as necessary.
-w UnixFileName SectorNumber
The UnixFileName must be an existing Unix file. The SectorNumber is an
integer. The Unix file data will be written to the BLITZ disk, starting
at sector SectorNumber. The directory will not be modified.
We are providing a DISK file which should be large enough, but if you want, you may create a new
BLITZ disk file of a different size. The new disk file must also be initialized properly; it can be created
and initialized with the format command in the BLITZ emulator. For example:
% blitz
…
> format
…
The name of the disk file is “DISK”.
The file “DISK” did not previously exist. (It could not
be opened for reading.)
Enter the number of tracks (e.g., 1000; type 0 to abort):
3
…
Initializing sectors 0 through 47…
Successful completion.
Project 5 Operating Systems
Page 19
Next, we use diskUtil to create a file system, add several files, and print the directory, by typing these
commands at the Unix prompt:
% diskUtil –i
% diskUtil -a temp1 MyFileA
% diskUtil -a temp2 MyFileB
% diskUtil -a MyProgram MyProgram
% diskUtil –l
StartingSector SizeInSectors SizeInBytes FileName
============== ============= =========== =====================
0 1 8192 < directory >
1 1 8192 MyFileA
2 3 17000 MyFileB
5 8 60264 MyProgram
The FileManager
There is only one FileManager object; it is created and initialized at startup time.
We are supplying several methods to help you access files on the “stub” file system; these methods are
located in this class. You’ll need to know how to access files in order to create the first user-level
process. You’ll need to open the executable file, read the bytes from disk, then close the file. You’ll
also need to use the fileManager when you implement the Exec syscall.
Some of the following material pertains more to the next project than this project. Read it all now to get
familiar with the framework. You may want to review it again during the next project.
Associated with the FileManager class, there are two other classes called FileControlBlock and
OpenFile. These two classes contain fields, but do not contain many methods of their own (besides
Init() and Print() methods). Instead, most of the work associated with the file system is done by the
FileManager methods.
The FileControlBlock (FCB) objects and the OpenFile objects are limited resources. The
FileManager maintains a free list for each of these, as well as code to allocate new FCB objects and
new OpenFile objects and maintain the free lists.
The FileManager also deals with opening files. This involves finding the file in the file system, that is,
determining the file’s location on disk. In the “stub” file system this is pretty simple since there is only
one directory and it fits into a single sector. The FileManager—as programmed now—reads the
directory sector (sector 0) into a frame as part of the FileManager.Init method. Subsequent attempts to
open a file require no disk accesses. (Of course, for a “real” file system, things won’t be so simple!)
Project 5 Operating Systems
Page 20
FileControlBlock (FCB) and OpenFile
The semantics of files in the kernel you are building will be similar to the semantics of files in Unix.
Consider the case where one process has opened a file and does a kernel call to read, say, 10 bytes. The
kernel must read the appropriate sector, extract the 10 bytes out of that sector, and finally copy those 10
bytes into the process’s virtual memory space. This requires the kernel to maintain a frame of memory
to use as a buffer; the sector will be read into this buffer by the OS.
If the 10 bytes happen to span the boundary between sectors, the kernel must read both sectors in order
to complete the Read syscall. And of course, during the I/O operations other threads must be allowed to
run.
Now consider what happens when a process wants to write, say, 20 bytes to a file. The kernel will need
to bring in the appropriate sector and copy the 20 bytes from the process’s virtual address space to the
buffer. Should the kernel write the buffer back to disk immediately? No; it is likely that the process
will want to write some more bytes to that very same sector, so it is more efficient to leave the sector in
memory.
When should the kernel write the sector back to disk? When the process closes the file, the kernel must
write it back. Also, other I/O operations on the file may need different sectors, so the kernel should
write the sector back to disk when the buffer is needed for another sector. However, if the buffer has not
been modified, then there is no need to write it back to the disk. Therefore, we associate a Boolean
called bufferIsDirty with each buffer frame. When a buffer is first read in from disk, it is considered to
be “clean,” but after any operation modifies the buffer, it should be marked “dirty.”
Next consider the case in which two processes have both opened the same file. (Let’s call them
processes “A” and “B.”) Any update by process A must be immediately visible to process B. If process
A writes to a file and B reads from that same file, even before A has closed the file, then B should see
the new data. Since the kernel may not actually write to the disk for a long time after process A does the
write, it means that processes A and B must share the buffer.
Also, when one process finally closes a file, the buffer must be written back to the disk. The guarantee
the kernel makes is that once we return from a call to Sys_Close, the disk has been updated. The
program can stop worrying about failures, etc., and can tell the user that it has completed its task. Any
changes the program has made—even if the system crashes in the next instance—will be permanent and
will not be lost. After a Sys_Close, the kernel must not return to the user-level program until the buffer
(or all buffers, if there are more than one) is written to the disk successfully.
The purpose of a FileControlBlock (FCB) is to record all the data associated with a single file. This
includes the buffer and the bufferIsDirty bit. Here is the definition of FCB:
Project 5 Operating Systems
Page 21
class FileControlBlock
superclass Listable
fields
fcbID: int
numberOfUsers: int — count of OpenFiles pointing here
startingSectorOfFile: int — or -1 if FCB not in use
sizeOfFileInBytes: int
bufferPtr: int — addr of a page frame
relativeSectorInBuffer: int — or -1 if none
bufferIsDirty: bool — Set to true when buffer is modified
methods
Init ()
Print ()
endClass
A small number FCBs are preallocated and kept in a table called fcbTable, which is maintained by the
FileManager. The FileManager is responsible for allocating new FileControlBlock objects and for
returning unused FileControlBlock objects to a free pool called fcbFreeList.
The startingSectorOfFile tells where the file is located on the disk. Since all the sectors in a file are
contiguous, the starting address and the length are all we need. The meaning of sizeOfFileInBytes is…
well, obvious. [Descriptive variable names like we tend to use are a HUGE help in understanding and
reading code!] A single memory frame is allocated for each FCB at kernel startup time and bufferPtr is
set to point to that memory region. relativeSectorInBuffer tells which sector of the file is currently in
the buffer and is –1 if there is no valid data in the buffer.
Next consider a process “A” that has opened a file. All of the “read” and “write” operations that the
user-level process executes are relative to a “current position” in the file. Several processes may have
the same file open. All processes that have file “F” open will share a single FCB. However, they will
each have a different “current position” in the file.
To handle the current position, we have the class OpenFile, which is defined as:
class OpenFile
superclass Listable
fields
kind: int — FILE, TERMINAL, or PIPE
currentPos: int — 0 = first byte of file
fcb: ptr to FileControlBlock — null = not open
numberOfUsers: int — count of Processes pointing here
methods
Print ()
ReadBytes (targetAddr, numBytes: int) returns bool — true=All Okay
ReadInt () returns int
LoadExecutable (addrSpace: ptr to AddrSpace) returns int — -1 = problems
endClass
Like the FCBs, there is a preallocated pool of OpenFile objects, which are created at system startup
time. The FileManager is responsible for allocating new OpenFile objects and for returning unused
OpenFile objects to a free pool called openFileFreeList.
Project 5 Operating Systems
Page 22
When process “A” opens a file, a new OpenFile object must be allocated and made to point to an FCB
describing the file. If there is already an FCB for that file, then the OpenFile should be made to point to
it; otherwise, we’ll have to get a new FCB, check the directory, and set up the FCB.
When do we return an FCB to the free pool? When there are no more OpenFiles using it. This is the
reason we have a field called numberOfUsers in the FCB. This field is a “reference counter.” It tells
the number of OpenFile objects that point to the FCB. When a new OpenFile is allocated and made to
point to an FCB, the count must be incremented. When an OpenFile is closed, the count should be
decremented. When the count becomes zero, the FCB must be returned to the free pool.
When a process is terminated, for example due to an error such as an AlignmentException, the kernel
must close any and all OpenFiles the process is using. The process may explicitly close an OpenFile
with the Close syscall. Once a file is closed, the process should attempt no further I/O on the file and if
the process does, the kernel should catch it and treat it as an error (by returning an error code from the
Sys_Read or Sys_Write kernel call).
Our file I/O will follow the semantics of Unix. When a process is cloned with the Fork syscall, all open
files in the parent process must be shared with the child process. Consider what happens when a parent
and a child are both writing to the same file, which was originally opened in the parent. Since both
processes share the OpenFile object, they will share the current position. If the child writes 5 bytes, the
current position will be incremented by 5. Then, if the parent writes 13 bytes, these 13 bytes will follow
the 5 bytes written by the child.
In order to implement these semantics, it will be possible for several PCBs to point to the same
OpenFile object. We need to maintain a reference count for the OpenFiles, just like the reference count
for the FCBs. Whenever a process opens a file, we need to allocate a new OpenFile object and set its
count to 1. Whenever a process forks, we’ll need to increment the count. When a process closes a file
(either by invoking the Close syscall or by dying), we’ll need to decrement the count. If the count goes
to zero, we’ll need to return the OpenFile to the free pool and decrement the count associated with the
FCB.
User-level processes must not be allowed to use pointers into kernel memory and cannot be allowed to
touch kernel data structures such as OpenFiles and FCBs. So how does a user process refer to an
OpenFile object? Indirectly, through an integer. Here’s how it works.
Each Process will have a small array of pointers to OpenFiles called fileDescriptor.
class ProcessControlBlock
…
fields
…
fileDescriptor: array [MAX_FILES_PER_PROCESS] of ptr to OpenFile
methods
…
endClass
When a process invokes the Open syscall, a new OpenFile will be set up. Then the kernel will select an
unused position in this array and make it point to the OpenFile. For example, positions 0, 1, and 2
Project 5 Operating Systems
Page 23
might be in use, so the kernel may assign a file descriptor of 3 for the newly opened file. The kernel
must make fileDescriptor[3] point to the OpenFile and should return “3” as the fileDescriptor to the
user-level process.
When the user-level process wants to do an I/O operation, such as Read, Write, Seek, or Close, it must
supply the fileDescriptor. The kernel must check that (1) this number is a valid index into the array,
and (2) the array element points to a valid OpenFile. When closing the file, the kernel will need to
decrement the reference count for the OpenFile object and also set fileDescriptor[3] to null. Then, if
the user process attempts any future I/O operations with file descriptor 3, the kernel can detect that it is
an error.
Since user-level file I/O will not be implemented in this project, you will not need to worry about
fileDescriptors yet.
When a user-level program does a Read or Write syscall—in Unix or in our OS—the data may be
transferred from/to either
• a file on the disk
• an I/O device such as a keyboard or display (these are called “special files” in Unix)
• another process, via a “pipe”
In all three cases, an OpenFile object will be used. The field called kind tells whether the object
corresponds to a FILE, the TERMINAL, or a PIPE. In this project, we will only use OpenFiles to
perform the Exec syscall, so the kind will be only FILE (and not TERMINAL or PIPE).
To Read in an Executable File
To read in an executable file from disk, your code will need to:
• Open the file
• Invoke LoadExecutable to do the work
• Close the file
Read through the code for FileManager.Open:
method Open (filename: String) returns ptr to OpenFile
Open is passed a ptr to array of char; this is the name of the file on the BLITZ disk that you want to
read from. It will allocate a new OpenFile object and a new FCB object and set them up. Then it will
return a pointer to the OpenFile object, which you’ll use when calling LoadExecutable. If anything
goes wrong, Open returns null. The only real danger is getting the filename wrong.
In BLITZ, like Unix, executable files have rather complex format. For details, you can read through the
document titled “The Format of BLITZ Object and Executable Files.” So that you don’t have to write
all this code, we are providing a method called OpenFile.LoadExecutable:
method LoadExecutable (addrSpace: ptr to AddrSpace) returns int
Project 5 Operating Systems
Page 24
Look through LoadExecutable; it will
• Create a new address space (by calling frameManager.GetNewFrames)
• Read the executable program into the new address space
• Determine the starting address (the initial program counter, also called the “entry point”)
• Return the entry point
If there are any problems with the executable file, this method will return –1. Otherwise it will return
the entry point of the executable. This is the address (in the logical address space) at which execution
should begin. Normally, this will be 0x00000000.
User-Level Processes
Each user-level process will have a single thread which will normally execute in User mode, with
“paging” turned on and interrupts enabled.
Each user-level process will have a logical address space, which will consist of
• A Page for “environment” data
• Pages for the text segment
• Pages for the data segment
• Pages for the BSS segment
• Pages for the user’s stack
These are shown in order, with the stack pages in the highest addresses of the logical address space.
The environment page will sit at address 0 and will contain information that the OS wishes to pass to a
new user-level process. This includes userID, working directory, etc. We will not use an environment
page, so the text pages will begin at address 0.
Kernel.h contains this:
const
NUMBER_OF_ENVIRONMENT_PAGES = 0
USER_STACK_SIZE_IN_PAGES = 1
MAX_PAGES_PER_VIRT_SPACE = 20
The text pages contain the program and any constant values.
The data pages will contain the static (global) program variables.
The BSS pages will contain space for uninitialized program variables (such as large arrays). The OS
will set all bytes in the BSS pages to zero. Most KPL programs do not use a BSS segment, so there will
usually be zero BSS pages.
Project 5 Operating Systems
Page 25
The user-level program will have a stack, which will grow downward. Each logical address space will
have a predetermined small number of pages (in our case, this is one page) set aside for its stack. In
Unix, if a user process’s stack grows beyond its initial allocation, more stack pages would be added. In
our OS, if a user process’s stack grows beyond this, it will begin overwriting the BSS and data pages,
and the program will probably get an error of some sort soon thereafter.
As an example, a program might use:
0 environment pages
2 text pages
1 data page
0 BSS pages
1 stack page
This process’s logical address space will have 4 pages. Each page has PAGE_SIZE bytes (8 Kbytes), so
the entire address space will be 32 Kbytes. Any address between 0x00000000 and 0x00007FFF (which
is 32K-1 in hex) would be legal for this program. If the program tries to use any other address, a
PageInvalid Exception will occur.
In Unix, the environment and text pages would be marked read-only and any attempt to update bytes in
those pages would cause an exception. In this project, all pages of the logical address space will be
read-write, so our OS will not be able to catch that sort of error in the user-level program.
Each page in the logical address space will be stored in one frame in memory. The frames do not have
to be contiguous and the pages may be stored in pretty much any order. However, all pages will be in
memory throughout the process’s lifetime.
The page table will keep track of where each page is kept. While the process is executing, “paging” will
be turned on so that the memory management unit (MMU) will translate all logical addresses into
physical addresses. Our example program will not be able to read or write anything outside of its 4
pages.
There may be several processes in the system at any time. Each ProcessControlBlock contains an
AddrSpace, which tells how many pages the process’s address space has and which frame in physical
memory holds each page.
When some process (call it “P”) is ready to be scheduled and given a time-slice, the MMU will be need
to be set up so that it points to the page table for process P. You can do this with the method:
AddrSpace.SetToThisPageTable ()
which calls an assembly routine to load the MMU registers. This method must be invoked before
paging is turned on. When paging is turned off (i.e., whenever kernel code is being executed), the
MMU registers are ignored.
Project 5 Operating Systems
Page 26
Note that each thread will have two stacks: a user stack and a system stack. We have already seen the
system stack; it is used when one kernel function calls another kernel function. The user stack will be
used when the thread is running in user mode. The system stack, which is fairly small, normally
contains nothing while the user-level program is running. In other words, the system stack is completely
empty.
After the user-level program begins executing, execution can re-enter the kernel in only through
exception processing. That is, the only ways to get back into the kernel are:
• an interrupt,
• a program exception, or
• a syscall
In each of these cases, the exact same thing happens: some information is pushed onto the system stack,
the mode is changed to system mode, paging is turned off, and a jump is made to a kernel “handler”
routine.
The BLITZ computer has two sets of registers: one for user-mode code and one for system-mode code.
Thus, the user registers do not need to be saved, unless the kernel will switch to another thread. This is
done in the Run method, which contains this code:
if prevThread.isUserThread
SaveUserRegs (&prevThread.userRegs[0])
endIf
…
Switch (prevThread, nextThread)
…
if currentThread.isUserThread
RestoreUserRegs (&currentThread.userRegs[0])
currentThread.myProcess.addrSpace.SetToThisPageTable ()
endIf
If the kernel handler code wishes to return to the same user-level code that was interrupted, it can merely
return to the assembly language handler routine, which will perform a “reti” instruction. The user
registers and the MMU registers will (presumably) be unchanged, so when the mode reverts to “user
mode” and the paging reverts to “paging enabled,” the user-level program will resume execution with
the same values in the user registers and the same logical address space.
Creating a User-Level Process
The main function calls function InitFirstProcess, which you must implement. The first thing you’ll
need to do is get a new thread object by invoking GetANewThread. Since the InitFirstProcess
function should return, you cannot use the current thread. Next you’ll need to initialize the thread and
invoke Fork to start it running. (You can name this new thread something like “UserProgram,” but the
name is only used in the debugging printouts.)
Project 5 Operating Systems
Page 27
The new thread should execute the StartUserProcess function, which will do the remainder of the work
in starting up a user-level process. InitFirstProcess can supply a zero as an argument to
StartUserProcess and can return after forking the new thread.
The first thing you’ll need to do in StartUserProcess is allocate a new PCB (with GetANewProcess)
and connect it with the thread. So initialize the myThread field in the PCB and the myProcess field in
the current thread.
Next, you’ll need to open the executable file. It is acceptable to “hardcode” the filename (e.g.,
“TestProgram1”) into the call to Open, although changing the name of the initial process will require a
recompile of the kernel. If there are problems with the Open, this is a fatal, unrecoverable error and the
kernel startup process will fail.
Next, you’ll need to create the logical address space and read the executable into it. The method
OpenFile.LoadExecutable will take care of both tasks. If this fails, the kernel cannot start up.
LoadExecutable returns the entry point, which you might call initPC.
Don’t forget to close the executable file you opened earlier, or else a system resource will be
permanently locked up.
Next, you’ll need to compute the initial value for the user-level stack, which you might call
InitUserStackTop. It should be set to the logical address just past the end of the logical address space,
since the initial push onto the user stack will first decrement the top pointer. The logical address space
starts at zero. The logical address space contains
addrSpace.numberOfPages
pages. Each page has size PAGE_SIZE bytes.
The StartUserProcess function will end by jumping into the user-level program. This is a one way
jump; execution will never return. (Instead, if the user-level program needs to re-enter the kernel, it will
execute a syscall). As such, nothing on the system stack will ever be needed again. We want to have a
full-sized system stack available for processing any syscalls or interrupts that happen later, so you need
to reset the system stack top pointer, effectively clearing the system stack.
You might call the new value initSystemStackTop. You’ll need to set it to:
& currentThread.systemStack[SYSTEM_STACK_SIZE-1]
Project 5 Operating Systems
Page 28
Next, you’ll need to turn this thread into a user-level thread. This involves these actions:
1. Disable interrupts
2. Initialize the page table registers for this logical address space
3. Set the isUserThread variable in the current thread to true
4. Set system register r15, the system stack top
5. Set user register r15, the user stack top
6. Clear the System mode bit in the condition code register to switch into user mode
7. Set the Paging bit in the cond. code register, causing the MMU to do virtual memory mapping
8. Set the Interrupts Enabled bit in the cond. code register, so that future interrupts will be handled
9. Jump to the initial entry point in the program
Recall that every thread begins life with interrupts enabled, so your StartUserProcess function will be
executing with interrupts enabled. The first step is to disable interrupts, since there are possible race
conditions with steps (2) and (3).
[What is the race problem? Consider what happens if a context switch (i.e., timer interrupt) were to
occur between setting the page table registers and setting isUserThread to true. Look at the Run
method. The MMU registers would be changed for the other process; then when this thread is once
again scheduled, the code in Run will see isUserThread==false so it will not restore the MMU
registers. Merely swapping the order of steps (2) and (3) results in a similar race condition.]
The first 3 steps can be done in high-level KPL code, but steps (4) through (9) must be done in assembly
language.
Read through the BecomeUserThread assembly routine in the file Switch.s., which will take care of
steps (4) through (9). StartUserProcess should end with a call to this routine:
BecomeUserThread (initUserStackTop, initPC, initSystemStackTop)
The BecomeUserThread will change the mode bits and perform the jump “atomically.” This must be
done atomically since the target jump address is a logical address space. (The way it does this is a little
tricky: it pushes some stuff onto the system stack to make it look like syscall or interrupt has occurred,
and then executes a “reti” instruction.)
BecomeUserThread jumps to the user-level main routine and never returns.
Approach to Implementing the Exec Syscall
The sequence of steps in InitFirstProcess and StartUserProcess is very similar to what you’ll need
when implementing the Exec syscall. You should be able to copy much of this code when
implementing Sys_Handle_Exec.
Project 5 Operating Systems
Page 29
One difference is that during an Exec, you already have a process and a thread, so you will not need to
allocate a new ProcesControlBlock, allocate a new Thread object, or do a fork. However, you will
have to work with two virtual address spaces. The LoadExecutable method requires an empty
AddrSpace object; it will then allocate as many frames as necessary and initialize the new address
space.
Unfortunately, LoadExecutable may fail and, if so, your kernel must be able to return to the process
that invoked Exec (with an error code, of course). So you better not get rid of the old address space
until after the new one has been initialized and you can be sure that no more errors can occur.
One approach is to create a local variable of type AddrSpace. Don’t allocate it on the heap, just use
something like:
var newAddrSpace: AddrSpace = new AddrSpace
Then, after the new address space has been set up, you can copy it into the ProcessControlBlock, e.g.,
currentThread.myProcess.addrSpace = newAddrSpace
Don’t forget to free the frames in the previous address space first, or else valuable kernel resources will
remain forever unavailable and the kernel will eventually freeze up!
Another tricky thing is copying the filename string from a virtual address space into the kernel address
space where it can be used. The filename argument is a virtual address, but since the kernel is running
in Handle_Sys_Exec, paging will be turned off.
You’ll need to copy the characters into an array variable, not something newly allocated on the heap. It
is okay to put a maximum size on this array and then check that it is not exceeded. In fact, there is a
constant in Kernel.h for this purpose:
const
MAX_STRING_SIZE = 20
(In a real OS, the maximum string size would be much larger or even nonexistent. Here, we use a small
size to make testing the limits easier.)
Note that the filename pointer is virtual address, which must be translated into a physical address; you
can’t just use it, as is. This requires some code to perform the page table lookup in software.
Furthermore, since the filename string is in virtual space, it may cross page boundaries. (In fact, the test
program contains cases where this happens!)
Dealing with the filename is fairly complex, but it turns out that we are giving you a method
GetStringFromVirtual (kernelAddr: String, virtAddr, maxSize: int) returns int
which will do most of the work. (GetStringFromVirtual calls CopyBytesFromVirtual to do the
copying.) The GetStringFromVirtual method can be used like this:
Project 5 Operating Systems
Page 30
var
strBuffer: array [MAX_STRING_SIZE] of char
…
i = currentThread.myProcess.addrSpace.GetStringFromVirtual (
& strBuffer,
filename asInteger,
MAX_STRING_SIZE)
if i < 0
…error…
endIf
You might think of allocating a temporary buffer on the heap, but remember that we do not want to
allocate anything on the heap after kernel start-up.
[ Recall that the “alloc” expression in KPL always allocates bytes on the heap. Once the kernel has
booted and is running, you must avoid further allocations. Why? One problem is automatic garbage
collection like you see in Java; we can’t use automatic garbage collection since it would produce
unpredictable delays and might cause the kernel to miss interrupts or, in the case of a real-time system,
miss deadlines. Also, there is the possibility that the heap might fill up, and dealing with a “heap full”
error in the kernel is difficult. Another option might be to try to manage the heap without automatic
garbage collection, but years of C++ experience has taught everybody that this is very difficult to do
correctly. This explains why we have gone to the trouble to create classes like ThreadManager and
ProcessManager, instead of simply allocating new Thread and ProcessControlBlock objects. ]
AllocateRandomFrames
The main function includes a function named AllocateRandomFrames, which is aimed only at
catching bugs in the kernel. This function will allocate every other frame in the physical memory and
never release them, creating a “checkerboard pattern” in memory. Henceforth, no two pages will ever
be allocated to contiguous page frames.
Large, multi-byte chunks of data in the user-level process’s address space will occasionally span page
boundaries. Since these pages may not be in adjacent frames, your kernel will have to be careful about
moving data to and from user space. What may appear to the user-level program as a string of adjacent
bytes may in fact be spread all over memory.
Some of the user-level syscalls pass pointers to the kernel. For example, Open passes a pointer to a
string of characters. Keep in mind that this pointer is a logical address, not a physical address. As such,
you cannot simply use the pointer as is. Take a look at these methods AddrSpace:
CopyBytesFromVirtual (kernelAddr, virtAddr, numBytes: int) returns int
CopyBytesToVirtual (virtAddr, kernelAddr, numBytes: int) returns int
GetStringFromVirtual (kernelAddr: String, virtAddr, maxSize: int) returns int
An invocation of AllocateRandomFrames has been added just after the FrameManager is initialized.
Please leave this in and do not modify the AllocateRandomFrames routine.
Project 5 Operating Systems
Page 31
What to Hand In
Please submit hardcopy of your output and hardcopy your new versions of the following files:
Kernel.h
Kernel.c
For both files, please take a colored pen and circle exactly those parts you have added or changed.
Please submit all of Kernel.h.
For Kernel.c, please submit only the pages that have something circled. In other words, please discard
all pages that contain ONLY material that we are distributing. Please keep the remaining pages in order.
Also, if you have modified any part of a method or function, please hand in the entire function, so there
is a little context surrounding your code modifications.
As a second option, which will save on wasted paper, you may perform the deletions with an editor,
instead of discarding physical pages. You can cut out large sections of code, but please indicate where
material has been clipped out. Please replaced deleted material with a line like this
XXXXXXXXXXXXXXXXXXX skipping XXXXXXXXXXXXXXXXXXX
to indicate which lines were removed. But please remember to circle your material with a colored pen.
For the output, please run TestProgram1 (which exec’s TestProgram2) and submit what it produces.
Coding Style
For all projects, please follow our coding style. Make your code match our code as closely as possible.
The goal is for it to be impossible to tell, just by looking at the indentation and commenting, whether we
wrote the code or you wrote the code. (Of course, your code will be circled!)
Please use our convention in labeling and commenting functions:
Project 5 Operating Systems
Page 32
—————————– Foo ———————————
function Foo ()
—
— This routine does….
—
var x: int
x = 1
x = 2
…
x = 9
endFunction
Methods are labeled like this, with both class and method name:
———- Condition . Wait ———-
method Wait (mutex: ptr to Mutex)
…
Note that indentation is in increments of 2 spaces. Please be careful to indent statements such as if,
while, and for properly.
If you follow these conventions, then even if you throw away other pages, it should be clear which class
the method belongs to.
Sample Output
If your program works correctly, you should see something like this:
=================== KPL PROGRAM STARTING ===================
Initializing Thread Scheduler…
Initializing Process Manager…
Initializing Thread Manager…
Initializing Frame Manager…
AllocateRandomFrames called. NUMBER_OF_PHYSICAL_PAGE_FRAMES = 100
Initializing Disk Driver…
Initializing Serial Driver…
Serial handler thread running…
Initializing File Manager…
Loading initial program…
User-level program ‘TestProgram1’ is running…
***** Testing Syscall Parameter Passing *****
***** About to call Sys_Yield…
***** Should print:
***** Handle_Sys_Yield invoked!
Handle_Sys_Yield invoked!
***** About to call Sys_Fork…
***** Should print:
***** Handle_Sys_Fork invoked!
Handle_Sys_Fork invoked!
Project 5 Operating Systems
Page 33
***** About to call Sys_Join…
***** Should print:
***** Handle_Sys_Join invoked!
***** processID = 1111
Handle_Sys_Join invoked!
processID = 1111
***** About to call Sys_Create…
***** Should print:
***** Handle_Sys_Create invoked!
***** virt addr of filename = 0x0000BFF8
***** filename = MyFileName
Handle_Sys_Create invoked!
virt addr of filename = 0x0000BFF8
filename = MyFileName
***** About to call Sys_Open…
***** Should print:
***** Handle_Sys_Open invoked!
***** virt addr of filename = 0x0000BFF8
***** filename = MyFileName
Handle_Sys_Open invoked!
virt addr of filename = 0x0000BFF8
filename = MyFileName
***** About to call Sys_Read…
***** Should print:
***** Handle_Sys_Read invoked!
***** fileDesc = 2222
***** virt addr of buffer = 0x0000B0A8
***** sizeInBytes = 3333
Handle_Sys_Read invoked!
fileDesc = 2222
virt addr of buffer = 0x0000B0A8
sizeInBytes = 3333
***** About to call Sys_Write…
***** Should print:
***** Handle_Sys_Write invoked!
***** fileDesc = 4444
***** virt addr of buffer = 0x0000B0A8
***** sizeInBytes = 5555
Handle_Sys_Write invoked!
fileDesc = 4444
virt addr of buffer = 0x0000B0A8
sizeInBytes = 5555
***** About to call Sys_Seek…
***** Should print:
***** Handle_Sys_Seek invoked!
***** fileDesc = 6666
***** newCurrentPos = 7777
Handle_Sys_Seek invoked!
fileDesc = 6666
newCurrentPos = 7777
***** About to call Sys_Close…
***** Should print:
***** Handle_Sys_Close invoked!
***** fileDesc = 8888
Handle_Sys_Close invoked!
fileDesc = 8888
***** About to call Sys_Exit…
***** Should print:
***** Handle_Sys_Exit invoked!
Project 5 Operating Systems
Page 34
***** returnStatus = 9999
Handle_Sys_Exit invoked!
returnStatus = 9999
***** Syscall Test Complete *****
***** Testing Exec Syscall *****
***** About to call Sys_Exec with a non-existant file…
***** Should print:
***** Okay
Okay
***** About to call Sys_Exec with an overly long file name…
***** Should print:
***** Okay
Okay
***** About to perform a successful Exec and jump to TestProgram2…
***** Should print:
***** User-level program ‘TestProgram2’ is running!
User-level program ‘TestProgram2’ is running!
***** About to call Sys_Shutdown…
***** Should print:
***** FATAL ERROR in UserProgram: “Syscall ‘Shutdown’ was invoked by a user thread” — TERMINATING!
FATAL ERROR in UserProgram: “Syscall ‘Shutdown’ was invoked by a user thread” — TERMINATING!
(To find out where execution was when the problem arose, type ‘st’ at the emulator prompt.)
=================== KPL PROGRAM TERMINATION ===================