Copyright 1991-1993, R.A. Burgess

MMURTL Architecture

Terms We Should Agree On

One thing the computer industry lacks is a common language, and I'm not talking about programming languages.  One computer term may mean 6 different things to 6 different people.  Most of the problem is caused by hype and poor advertising, but some is also attributed to laziness (yes, I admit guilt here too).  People use terms in everyday conversation without really trying to find out what they mean.  Before we go into the MMURTL architecture, I have to define some terms just to make sure we're on common ground.  You may not agree with the definitions, but please accept them, at least temporarily.

TASK - I use the same definition as the Intel 80386 System Software Writer's Guide and the 80386 and 80486 Programmer's Reference Manuals.  This is convenient if you want to refer to these documents while reading this book.  I destroyed two copies of each of these books while writing MMURTL (pages falling out, coffee and soda spilled on them, more highlighter and chicken scratching than you can imagine).  A task is an independently scheduled thread of execution.  You can make the same 50 instructions in memory into 20 independent tasks.  When a task is suspended from execution, it's hardware and software state are saved, while the next task's state is restored and then executed.  A single computer program can have one or more tasks.  Some operating systems call a task a process, while others call it a thread.  I call it a TASK.

KERNEL - This term is not disputed very much, but it is used a lot in the computer industry.  It also seems that a lot of people use the term and they don't even know what it is. It is pretty much accepted that the kernel of an operating system is the code that is directly responsible for the tasking model. In other words, it is responsible for the way the CPU's time is allocated.  MMURTL has a very small amount of code that is responsible for the tasking model.  In it's executable form, it probably isn't much more than two kilobyte of code.  This makes it a very small kernel.  This would allow me to use the latest techno-buzz-word "micro-kernel" if I were into buzzwords.  It's always nice to be in vogue with your buzz words and hype.  The operating system functions that directly affect CPU tasking are called kernel primitives.  It's not because they're from Neanderthal Computing, but because they are the lowest level entry points into the kernel code of the operating system.

Resource Management

MMURTL is an operating system that manages resources for applications.  This is it's only purpose in life.  One of the major goals of MMURTL is simplicity.  To paraphrase a famous scientist (yes, good old Albert), "Everything should be as simple as possible, but not simpler."  I have attempted to live up to that motto while building MMURTL.  A friend of mind suggested the motto, "Simple Software for Simple Minds," but needless to say it didn't sit too well with me.

This chapter discusses the architecture and theory of operation of MMURTL from the standpoint of a resource manager. After all, isn't that what a computer operating system should be doing?

The resources discussed include CPU time (which deals with messaging and task management), memory management, and hardware (Timers, DMA, Interrupt Controller Units, etc.).  These are the real resources.  Everything else uses these resources to accomplish their missions.  Input/Output (I/O) including video, keyboard, disk and communications use these resources to do their jobs and these resources must be managed properly for all these things to work effectively in a true multitasking environment.

CPU Time

In a single tasking operating system, management of CPU time is easy.  The only thing for the programmer to worry about is how efficient the OS is at its other jobs (file handling, interrupt servicing, etc.).

With a true multitasking operating system that provides a program the ability to create more than one thread of execution, management of CPU time becomes critical.  This management is often called the Tasking Model.

MMURTL has a real-time message-based, prioritized tasking model.  "Message based" means you can send messages between tasks in both synchronous and asynchronous fashions. "Prioritized" means that certain tasks will get to run more often than others, but only if they need to.  Real-time means it was designed to respond to outside events in a timely fashion.  Many operating system have problems responding to outside events.  Operating systems that share the CPU among tasks by just dividing up a period of time and giving each task a share, respond poorly to outside events.  This method is commonly referred to as Time Slicing.  This is not to say they have poor interrupt latency, but they have problems with unbalanced jobs being performed by the tasks.  For instance, take two communications programs that handle two identical ports with two independent Interrupt Service Routines (ISRs).  If the programs have an equal time slice and equal buffer sizes, but one channel is handling five times the data, the program servicing the busier port may lose data if it can't get back to the buffer in time to empty it. It will overflow.  This is a very simple example, but it makes the point.  In a message based system, the ISR can send a message to the program servicing it to tell it the buffer is almost full ("Hey, come do something with this data before I lose it").
-----------------------------------------------

Messaging And Tasks

A TASK is a single thread of instructions that can be independently scheduled for execution (as described earlier).

A MMURTL JOB is one or more tasks that make up a program. The initial task in a program may create additional tasks as needed. These new tasks inherit certain attributes from the initial task.

Before we discuss task scheduling we should look at how tasks communicate with each other in MMURTL because this is the key to the scheduler.

MMURTL is message based.  Tasks exchange information with each other by sending messages.  The messages come in two basic forms.  A "request" for services which should receive a response, and a non-specific "message" that doesn't expect a response.  The Request/Respond concept is the key to the MMURTL client-server architecture.

Sending and receiving messages in MMURTL is not unlike messaging of any kind (even phone messages).  You can send one way messages to a person such as "Tell Mr. Zork to forget it, his offer is the pits."  This is an example of a one way message that you expect no response from.  One key element in a message system is WHERE you leave your messages. In Bob's case he will get the message from his secretary.  In MMURTL's case, we call it an Exchange.  In order to send a message you must have an exchange.  MMURTL provides a call to allocate exchanges for jobs.  It is called AllocExch.  AllocExch is defined like this in C:

	unsigned long AllocExch(long *pdExchRet);

pdExchRet points to a DWord where the exchange number is returned.  The return value is the error if there is one.  It returns zero if all went well.

You also need a way to send the message.  OS calls to send a message come in several varieties.  The most common is SendMsg.  It does just what it says, it sends a message.  You tell it what exchange, give it the message and away it goes.  If you're lucky, the task that you want to get the message is "waiting" at the exchange by calling WaitMsg.  If not, the message will wait there until a task waits at the exchange or checks the exchange with CheckMsg.  The C definitions for these calls are:

unsigned long SendMsg(long dExch, 
                      long dMsgPart1, 
                      long dMsgPart2);
  
dExch -  the Exchange to send to
dMsgPart1 - First DWord in message
dMsgPart2 - Second DWord in message

unsigned long WaitMsg(long dExch,
                      char *pMsgRet);

unsigned long CheckMsg(long dExch,
                       char *pMsgRet);

dExch is the Exchange to send to.

pMsgRet points to an 8 byte (2 DWords) structure where the message will placed.


Did you notice (from the text above) that not only messages wait at exchanges, but tasks can wait there too.  This is an extremely important concept.  Consider the phone again.  The task is the human, the answering machine is the exchange.  You can leave a message on the machine (at the exchange) if no one (no task) is waiting there.  If a human is there waiting (a task is at the exchange waiting), the message is received right away.

Now, consider this. In a single processor system (one CPU) that is executing a multitasking operating system, only one task is actually executing instructions.  All the other tasks are WAITING somewhere.

There are only two places for a task to wait in MMURTL.  At an Exchange or on the Ready Queue.  The Ready Queue is the line-up of tasks that are in a ready-to-run state, but are not running because there's a higher priority task currently executing.  

One more quick introduction to round off what we've already covered.  Tasks are started with the kernel primitives SpawnTask or NewTask.  You point to a piece of code, provide some other pieces of information, and VOILA, a task is born.  Yes, it's a little more complicated than that, but we have enough to finish the basic theory.

Now we have some very important terms and functions defined.  Not in detail yet, but enough that we can talk about them.  SendMsg, CheckMsg, WaitMsg, SpawnTask, and NewTask are five very important kernel primitives.  AllocExch is an important auxiliary  function.  The only reason it's discussed with the rest of the kernel primitives is because of its importance.  I don't consider it part of the kernel because it has no effect on the tasking model (CPU time allocation). We also know about Exchanges and the Ready Queue.

I apologize that none of the items I've introduced have names that are confusing or buzzwordish.  I'll try to liven it up some later on.

We now have enough information under our belt to provide a scenario of message passing that will help enlighten you to MMURTL's methods.  

We'll start with a single task executing (what it's doing isn't important).  Lets also define time.  As we move down the page in our example, time is passing.  That was easy.

In our example, whenever you call a kernel primitive you enter the KERNEL ZONE.  Just kidding, it's not called the kernel zone, just the kernel (a small tribute to Rod Serling, very small...).

Task1 is Running
Task1 allocates Exch1
Task1 calls SpawnTask (to start Task2)
Kernel checks priority of new task. Task2 is higher.
Kernel places Task1 on the Ready Queue. 
Kernel makes Task2 run

Task2 is running.
Task2 allocates Exch2.
Task2 sends a message to Exch1.
Kernel checks for a task waiting at Exch1. None are.
Kernel attaches message to Exch1.

Task2 is still running.
Task2 calls WaitMsg at Exch2.
Kernel places Task2 on Exch2.
Kernel evaluates Ready Queue. Task1 is ready to run.
Kernel makes Task1 run.

Task1 is running.
Task1 calls WaitMsg at Exch1. 
Kernel gives msg at Exch1 to Task1.
Kernel evaluates Ready Queue. Only Task1 is ready to run.

Task1 is running
Task1 sends a message to Exch2
Kernel attaches message to Exch2.
Kernel places task1 on Ready Queue
Kernel makes Task2 run (Higher priority) 

Task2 is running
etc. 
etc.

From this simple explanation you can see that the kernel has it's job cut out for it.  You can also see that it is the messaging and the priority of the tasks that determines the sharing of CPU time. 

From the example you can also see that when you send a message, the kernel attaches the message to an exchange. If there is a task at the exchange, the message is associated with that task and it is placed on the Ready Queue.  The Ready Queue is immediately reevaluated, and if the Task that just received the message is a higher priority than the task that sent it, the receiving task is made to run.

What would happen if both Task1 and Task2 waited at their exchanges and no one sent a message?  You guessed it... the processor suddenly finds itself with nothing to do.  Actually it really does absolutely nothing.  MMURTL HALTs the processor with interrupts enabled. If everyone is waiting at an exchange, they must be waiting for something.  More than likely it is something from the outside world.  For instance a keystroke.  Each time an interrupt occurs, the processor is activated and it checks the Ready Queue.  If the interrupt that caused it to wake up sent a message, there will probably be a task sitting on the ready queue.

Request and Respond

Two more messaging calls exist. They are dedicated types.  Request and Respond provide the basis for a client server system that provides for identification of the destination exchange, and also allows you to send and receive much more than the 8 byte message used with the SendMsg primitive.  

The Request and Respond messaging primitives are designed so  you can install a program called a System Service that provides shared processing for all applications on the system.  The processing is carried out by the service, and a response (with the results and possibly data) is returned to the requestor.

Message based services are used to provide shared processing functions that are not time critical (where a few hundred microsecond delay would not make a difference), and need to be shared with multiple applications.  They are ideal for things like file systems, keyboard input, printing services, queued file management, E-mail services, BBS systems, FAX services, the list could go on and on and on.

Each service installed is given a name.  The name must be unique on the machine.  When the service is first installed it registers its name with the OS Name Registry and tells the OS what exchange it will be serving.  This way, the user of the system service doesn't need to know the exchange number, only the service name.  The exchange number may be different every time it's installed, but the name will always be the same.  A fully loaded system may have 10, 20 or even 30 system services. 

Each service can provide up to 65533 different functions as identified by the Service Code.  The functions and what they do are defined by the service.  The OS knows nothing about the service codes (except for one discussed later).  It doesn't need to because the Request interface is identical for all services.

The interface to the Request primitive is procedural, but has quite a few more parameters than SendMsg.  Look at it prototyped in C:

unsigned long Request(char *pSvcName,
                      unsigned int wSvcCode,