Nothing is permanent but change.
-- Heraclitus
This chapter is intended for users who require a deeper understanding of the RCOS system in order to perform modifications or enhancements. It describes the conventions used in the code style known as "Hungarian Notation" (sometimes referred to as a type calculus).
The use of a type calculus is intended to provide consistency in the naming conventions employed throughout the code. Once understood, it is possible to make an accurate guess at the purpose of an object, its type and the module in which it may be found simply by examining its name.
The RCOS design is built on "Black Boxes" exhibiting low coupling. The intention is to maximise abstraction so that complex modifications may be made with a high confidence that parts of the program not modified will not be affected. RCOS is written in the object oriented language C++ to assist this process and to promote a degree of object re-usability. For instance, if you need a linked list, the DblList class will provide all the functionality required with complete reliability.
This functional isolation is extended so that functions that are not under investigation need not be examined or even understood. For example, the Push Buttons and Radio Buttons that provide interaction to the Supervisor need not be understood if the Supervisor is not involved in the modification. Indeed, the Supervisor itself need not be examined or understood to perform changes to the Kernel or on of the other operating system modules.
All programming texts agree: the use meaningful identifiers will greatly improve
program reliability and maintainability. Research and practice at Xerox, Apple,
Microsoft and other organisations has lead to the emergence of a type calculus known in programming folk-lore as "Hungarian Notation" - after the ancestry of one of its chief architects, Charles Simonyi.
You will find variations of this style coming into increasing use, simply because it works. One reason it works is that its definition is rather "loose"; you can implement it any way you wish.
In the RCOS source code, the purpose and location of the original definition of any object is suggested by its name, with a fair degree of consistency. This is not difficult when a product is produced by a single individual, as was the case with RCOS, but when a project is produced by several teams, each with many programmers, cohesion will definitely suffer unless some naming convention is enforced.
The notation used within the RCOS source places a prefix on identifiers. The prefix, generally no more than three characters, uses capitalisation and mnemonic code to suggest the object's type and usage. Where practical, the individual module names track the prefix, so the file location is also suggested. The usefulness of this concept becomes evident with experience. The following conventions apply:
The first letters of every identifier will suggest what it is. Some conventions are universal: p denotes some kind of pointer; n a signed integer; sz a null (zero) terminated string. The first actual letter of the name as distinct from the prefix is capitalised. So, for example:
Variable Explanation
szTitle a null terminated character array, probably some kind of
title
nCount a signed integer, perhaps a count of something
uID an unsigned integer, an identifier with constant usage
(see below)
psz a pointer to a null terminated character array
Table 7.1.
Example Hungarian Notation Variable Names.
A name of all upper case letters, or a prefix of all upper case letters followed by an underscore signals that the object is a constant or a defined type (the context will provide the distinction).
Identifier Explanation
PMSG a defined (typedef) type denoting a pointer to class
MSG
UINT standard typedef for "unsigned short" (shorter, too)
ID_Kernel a defined constant
TTY_Reset a constant. Good chance it was defined in module
TTY.HPP
PB_Pause a constant, probably used to uniquely identify a Push
Button
Table 7.2.
Example Constant Identifiers.
Functions and function class members will always begin with a single capital. No underscores will be used within function or variable names. If it is necessary to improve understanding, additional caps will be placed at logical word breaks. Usually (but not always), the function will be prefixed to suggest its module location:
Function Explanation GfxTextHeight() A function returning text height, found in module GFX DrawWindow() Function, probably local to the current module. DblGetNext() Member of class DBLLIST (no-one said it was perfect!)
Table 7.3.
Example Function Names.
Classes beginning with a lower case letter contain no functions. In some cases they may be structures. Classes beginning with a capital contain member functions. For example:
Identifier Explanation
message A class/structure with no member functions
Port A class with members (you can't tell, but it's an
abstract class)
MSG A typedef of the message class object
Table 7.4.
Example Class Names.
As noted above, the system is not rigid. If departing from the convention assists logic flow comprehension, or impacts some aspect of practicality, the transgression takes precedence. We will find, for instance, that the prefix "Rb" denotes members of the derived class defining just what it is to be a Radio Button; similarly, "Pb" denotes a Push Button and "Cb" a Check Box - all being derived from the base class "Btn".
For convenience and to limit the number of source modules required, these objects are lumped together under the files named CTRLS, with file extension HPP for the header and CPP for the body code. Largely, however, the intent is obvious and the location of the object definition can be deduced. If your compiler has a facility like Microsoft's "Source Browser", any ambiguities are readily resolved.
During the course of the CQU operating systems subject you will be asked to make modifications of the RCOS code to implement a different algorithm or use a different data structure.
To make it simple for you to recover from your modifications it is suggested that you
For example,
Place #define MY_MODS in a header file and then surround any modifications with
#ifdef MY_MODS
...
#endif
During 1994 RCOS was used for the first time for the CQU Operating Systems subject. The second assignment in that subject is outlined below. It and one solution to the assignment is used as an example of modifying RCOS.
The CPU Scheduling performed by RCOS could be characterised as a priority based version of the Round Robin algorithm. All processes are assigned a priority value when created (P0 = 100, all other processes = 42). The ready queue is maintained in descending order on priority. The process with the highest priority is always at the head of the queue and it gets placed on the CPU next.
This scheduling algorithm suffers from the same problem that any scheduling algorithm that uses priorities can suffer from, indefinite postponement (also known as starvation). It is possible for a process with a low priority to be indefinitely postponed because there is always a process with a higher priority.
The aim of this assignment was to modify the RCOS process scheduling algorithm to remove the problem of starvation.
Exercises
7.1. Start up RCOS and create two processes both running the PRIMES.PCD program. Change the priority of one of these processes to 35. Observe what happens.
Make back up copies of the RCOS source files.
The only source files you will need to modify are exec.cpp and exec.hpp.
There is one limitation on how you implement aging. You must not ignore the current priority mechanism totally. i.e. if processes are the same age they must be ranked in RCOS' current priority order.
There are no strictly right or wrong answers for this question only better and worse solutions. This solution is one of the better ones in that it minimises the amount of extra work that has to be carried out to implement the scheduling algorithm. (However it is not as "fair" as a more complex solution might be.)
Efficiency is an important consideration to remember when making any modifications to an operating system. You want the operating system to be as efficient as possible this implies that the algorithms and the code the operating system uses should be efficient.
The solution is to incorporate into the current RCOS CPU scheduling algorithm some notion of aging. Aging is a solution to starvation. Basically it means that the longer a process is waiting on the ready queue the higher its priority becomes (it ages) until eventually it becomes the current process.
A simple implementation is
This is a simple form of aging. The longer a process remains on the ready queue the greater its priority will become. Eventually it will become the highest priority process and get its turn on the CPU. Once it has executed it will return to its normal priority and being the climb up the priority hill again.
The steps to implementation are
In this case we want to
This step identifies the files that need to be modified. The low coupling used in the design of RCOS means that you can be confident that modifying one file will not effect another file.
By referring back to chapter 1 it can be seen that all the process management data structures and algorithms are contained in the EXEC.CPP and EXEC.HPP files.
The file EXEC.HPP declares the following array
PCB arrPCB[MAX_PROC];
that is used to contain the process control blocks of all the processes that are currently in the system. The information that RCOS stores in a process control block is also defined in the EXEC.HPP file with the structure PCB. The structure is below with the value of interest in bold.
typedef struct pcb {
char *pszName; // user name for process, if any
INT16 nPriority, // process priority
nQuantum; // max permissable ticks per scheduling
UINT16 uPid, // unique ID for process (PID)
uPidp, // parent PID of process
uIP, uSP, uBP, // Instruction, Stack and Base pointers
uStatus, // current status
uDevCnt; // count of devices open by process
PMSG pReply; // message associated with wake-up
UINT32 lStarted, // time process started/created (mS).
luTicks, // amount of processor time in user
// mode
leTicks, // time consumed in executive mode
lCode; // 32 bit instruction at IP for
// animator
LnDrv *pDev; // pointer line protocol driver
UINT16 arrDev[MAX_DEV]; // Devices needed before process can
//start
UINT16 uTos; // fetched values at top of stack
UINT16 uSemOpen, // Bit map of semaphore ID's opened by
// PID
uSemSet, // map of semaphores set by this
// process
uSemWait; // map of semaphores we are waiting on
DblList Share; // List of open shared memory block
// ID's
FsIface *pFile; // File sysem Interface package
} PCB, *PPCB;
The ready queue (and all the other process queues used by RCOS) are all object of class Pque. This class is declared in EXEC.HPP and is partially shown below.
class Pque : private DblList {
typedef struct qmbr { // structure used for double link list
INT16 nKey; // Key for ordering (normally priority)
UINT16 uPid; // index into array (which is the PID #)
} QMBR, *PQMBR;
BOOL bOrdered; // FIFO or priority ordering
public:
The class Pque is basically a list of QMBR structures. Each element of the queue contains
A key for ordering the list. In the case of the Ready Queue this represents the current priority of the process.
The process' unique process identifier. This number can be used to access the process' PCB structure from the arrPCB array.
Every time a process is added to the Ready Queue the function Pque::PqAdd is executed. A part of this function automatically assigns nKey to be the process' priority. From this point in time nKey and nPriority are completely unrelated (changes to one do not change the other).
Diagram 6.2 provides an overview of the major functions in the EXEC class and how they relate to RCOS' process management. From Diagram 6.2 we can see that the function Exec::Sked is executed everytime a new process is placed onto the CPU
When a process is added to the ready queue a new Queue element is created and the PID and priority of the process are copied from the processes PCB into the new Queue element. Any modifications made to the Queue element after this time is not reflected in the PCB.
Here's the plan.
. Define the macro AGING in EXEC.HPP
. Add a new function Exex::CalcPriority that increments the nKey variable for every element of the Ready Queue.
. Everytime a new process is placed on the CPU (the function Exec::Sked) call the CalcPriority function.
There is no need to reset the priority of a process as this is done automatically in Pque::PqAdd when a process is added back onto the ready queue. The ready queue holds only the PID and the process's priority. The PqAdd function copies the priority that is in the PCB into the ready queue structure. From then on my solution only modifies the priority on the ready queue.
Only the modifications to EXEC.CPP are listed below. #define AGING was also added to EXEC.HPP.
#ifdef AGING
//*****************************************************
// CalcPriority
// - execute every quantum expiration
// - increment nKey of every process on the ready queue
void Exec::CalcPriority( void )
{
PQMBR pTemp = PqReady.PqGetHead();
while ( pTemp )
{
pTemp->nKey++;
pTemp = PqReady.PqGetNext();
}
}
#endif // AGING
.
void Exec::Sked (void)
{
INT16 i;
UINT16 arrProcs[MAX_PROC];
.
.
uCurProc = PqReady.PqGet();
if (uCurProc != NO_PROC) {
arrPCB[uCurProc].nQuantum = PCD_QUANTUM;
#ifdef AGING
CalcPriority();
#endif
}
.
.
}
RCOS uses Hungarian Notation as the naming scheme for identifiers. This approach provides a number of advantages including the ability to know the type of a variable simply by observation.
The design of RCOS was intended to result in low coupling between the different components of the system. This means that modifications can be made inside of sub-systems like process and memory management without fearing multiple unpredictable effects on the rest of the system.
Modifying RCOS consists of a number of steps