[2022] WWU - CSCI 447 - Operating Systems - Assignment3: Kernel Resource Management
CSCI 447 - Operating Systems, Spring 2022
Assignment 3: Kernel Resource Management
Due Date: Tuesday, April 19, 2022
Points: 125
1 Overview and Goal
Assignments 3 through 7 are the implementation of our small Blitz OS. This is really one assignment or project with five turn in points. It is important that you keep up as much as possible because a late assignment means you are behind in the entire project and you still must finish an assignment before you start work on the next one.
In this assignment, 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 code from the \game" program in assignment two in that these three monitors will orchestrate the allocation and freeing of resources needed by the Kernel.
4 Task 1: Threads and the ThreadManager (35 points)
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. (Kernel.k will not use the KPL \alloc" feature.) 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 startuptime in Main.k.
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 assignment to invoke FreeThread when a thread terminates-thereby adding it to the free list-instead of setting its status to UNUSED.
Here is the de nition 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 if 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 rst 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.k 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 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 assignment. The Thread methods are unchanged.
5 Task 2: Processes and the ProcessManager (35 points)
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
superclass Listable
fields
pid: int
parentsPid: int
status: int -- ACTIVE, ZOMBIE, or FREE
myThread: ptr to Thread
exitStatus: int
addrSpace: AddrSpace
workingDir: ptr to OpenFile -- The current working directory
error: int -- Error from last system call
fileDescriptor: array [MAX_FILES_PER_PROCESS] of ptr to OpenFile
methods
Init ()
Print ()
PrintShort ()
endClass
Each process will have a process ID (the eld named pid). Each process ID will be a unique number, from 1 on up. It is important that the rst process is given the process ID of 1.
Processes will be related to other processes in a hierarchical parent-child tree. Each process will know who its parent process is. The eld called parentsPid is a integer identifying the parent. One parent may have zero, one, or many child processes. To nd 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 xed, small number of ProcesControlBlocks, these are resourceswhich 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.
