Programming Project 4:
Due Date: ______________________________
Duration: One
Week
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.
Start by creating a new
directory for this project and then download all the files from:
http://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
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.
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:
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.
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.
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.
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:
class ProcessControlBlock
fields
pid: int
parentsPid: int
status: int
-- ACTIVE, ZOMBIE, or FREE
myThread: ptr
to Thread
exitStatus: int
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.
There will be only one ProcessManager and this instance
(initialized at start-up time) will be called processManager.
processManager
= new ProcessManager
processManager.Init ()
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 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.
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.
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
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.
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.
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
(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.
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.
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.
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
...
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 re-check 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.
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.
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.
Your instructor may alter
this policy. Of course, your
instructorÕs policy takes precedence over what is written here.
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
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!
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.112013.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..1117.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.11.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.20.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....612711.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.18.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 *****
***** 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..38.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..110..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...7105..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..110.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.10.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 ====================
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.