47KB
Developing Your Own 32-Bit Operating System — Chapter-03: The Tasking Model
- Source: /library/Developing Your Own 32-Bit Operating System/source-file.pdf
- PDF pages: 45–62
- Pages without text: 45, 46, 47
- Note: Includes the Part II divider plate and its blank verso before the chapter.
The Tasking Model
26 I Part II ■ Architecture and General Theory This chapter discusses the tasking model and the things that have an effect on it. Most of the discussion centers on resource management and, more specifically, CPU utilization. After all, resource management is supposed to be what a computer operating system provides you. Terms We Should Agree On One thing the computer industry lacks is a common language, and I'm not talking about pro- gramming languages. One computer term may mean six different things to six different people. Much of the problem is caused by hype and deceptive advertising, but some of it also can be attributed to laziness. (Yes, I admit some guilt here too.) People use terms in everyday conver- sation without really knowing what they mean or at least without coming to agreement on them. Before I begin a general discussion or analyze your options for a tasking model, I have to define some terms just to make sure we're on common ground. You may not agree with the definitions, but I hope you will accept them while you're reading this book. The terms you already should be familiar with are as follows: ■ Task ■ Kernel ■ Preemptive multitasking Tasks A task'is an independently scheduled thread of execution. You can transform the same 50 pro- cessor instructions in memory into 20 independent tasks. When a task is suspended from ex- ecution, its hardware and software states 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 sys- tems call a task a “process,” whereas others call it a “thread.” In most instances, I call it a task. Some documentation, however, may use other words that mean the same thing, such as “interprocess communications,” which means communications between tasks. Generally, I have seen the term thread applied to additional tasks all belonging to one pro- gram. But this is not cast in stone either. It really depends on the documentation with the operating system you are using. If you write your own, be specific about it. Tell the program- mers what you mean. For task, I use the same definition as in 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 literally destroyed two copies of each or these books while writing MMURTL (pages falling out, coffee and soda spilled on them, more highlighter and chicken scratching than you can imagine). The Intel-based hardware is by far the most available and least expensive, so I imagine most of you will be working with it.
Chapter 3 ■ The Tasking Model The Kernel The term kernelis not disputed very much, but it is used a lot in the computer industry, so it is important to understand. Apparently a lot of people use the term and they don't even know what it is. The kernel of an operating system is the code that is directly responsible for the task- ing 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 its executable form, it probably isn't much more than two or three kilobytes of code. This makes it a very small kernel. This might incline me to use the techno-buzz-word “microkernel” if I were into buzzwords. The operating system functions that directly affect CPU tasking are called kernel primitives. This is not because they're from the days of Neanderthal computing, but because they are the lowest-level entry points into the kernel code of the operating system. Preemptive Multitasking Preemptive multitasking is a hotly disputed term (or phrase) in the industry. It shouldn't be, but it is. In computing, the word preempt simply means to interrupt something that is cur- rently running, but doesn't expect the interrupt. There are many ways to do this in a computer operating system. One type of preemption that occurs all the time is hardware interrupts. I'm not including them in this discussion because they generally return control of the processor back to the same interrupted task, and non-multitasking systems use them to steal time from programs and simulate true multitasking (for example, MS-DOS TSRs — terminate-and-stay- resident programs). The preemptive multitasking I'm talking about and that most people refer to is the capability for an operating system to equitably share CPU time between several well- defined tasks currently scheduled to run on the system (even tasks that may be a little greedy with the CPU). My definition of preemptive multitasking is as follows: If an operating system has the capabil- ity to stop a task while running before that task was ready to give up the processor, to save its state, and then start another task running, it's preemptive. How and when it does this is driven by its tasking model. An operating system that you use may be preemptive, but its tasking model may not be the correct one for the job you want to accomplish (or you may not be using it correctly) — hence, all the grumbling and heated discussions I see on the online services. When you determine exactly what you want for a tasking model, you will see the rest of your operating system fit around this decision. n Resource Management An operating system manages resources for applications and services. This is its only real pur- pose in life. Consider your resources when planning your operating system. The resources in- clude CPU time sharing (tasking model), memory management, and hardware (timers, DMA, interrupt controller units, and so on). These are the real resources. Everything else uses these
:s Part II ■ Architecture and General Theory resources to accomplish their missions. Input/output (I/O) devices, including video, keyboard, disk, and communications equipment, make use of these basic resources to do their jobs. These resources must be managed properly for all these things to work effectively in a multitasking environment. One of my major goals in designing the MMURTL operating system was simplicity. To para- phrase a famous scientist (yes, good old Albert), “Everything should be as simple as possible, but not simpler.” (Otherwise it wouldn't work!) I have attempted to live up to that motto while building my system as a resource manager. One of my friends suggested the motto “Simple software for simple minds,” but, needless to say, it didn't sit very well with me. Managing these resources in a simple yet effective fashion is paramount to building a system you can maintain and work with. Task Management Tasks begin. Tasks end. Tasks crash. All of these things must be taken into consideration when designing a task-management scheme. Obviously, keeping track of tasks is no simple “task.” In some operating systems, each task may be considered a completely independent entity. It may have memory assigned to it, and it may even run after the task that created it is long gone. On the other hand, it may be completely dependent on its parent task or program. How tasks are handled and how resources are assigned to these tasks was easy for me to decide, but it may not be so easy for you. If you decide that a single task may exist on its own two feet, then you must make sure that your task-management structures and any interprocess communications mechanisms take this into account. When you get to Part IV of this book (“The Operating System Source Code”), take a good look at the TSS (Task State Segment). This is where all of the resources for my tasks are managed. You may need to expand on this structure quite a bit if you decide that each and every task is an entity unto itself. Single User Versus Multiuser One of the determining factors on how your tasks are managed may be whether or not you have a true multiuser system. The operating system included with this book is not multiuser. It is not a UNIX clone by any stretch of the imagination. Nor did I want it to be. In a system that is designed for multiple terminals/users, tasks may be created to monitor serial ports or even network connections for logons, execute programs as new users’ desire, and then still be there after all the child processes are long gone (for the next user). Probably the best way to get this point across is to describe what I decided, and why. From this information you will be able to judge what's right for you. I have written many commercial applications that span a wide variety of applications. Some are communications programs (fax software, comms programs), some deal with equipment control (interaction with a variety of external hardware), and some are user-oriented software.
Chapter 3 H The Tasking Model In each case, when I look back at the various jobs this software had to handle, each of the func- tions dealt with a specific well-defined mission. In other words, each program had a set of things that it had to accomplish to be successful (satisfy the user). When I wrote these programs, the ability to spawn more tasks to handle requirements for simultaneous operations came in very handy. But in almost all of these systems, when the mission was accomplished, or the user was done, there seemed to be no purpose in having additional tasks that continued to run. The largest factor was that I had a CPU in front of me, and each of the places these programs ex- ecuted also had a CPU — in other words, single user, multitasking. My operating system is designed for microcomputers rather than a mini or mainframe envi- ronment (although this line is getting really blurry with the unbelievable power found in mi- cro CPUs these days). I deal with one user at a time. You may want to deal with many. Your decision in this matter will have a large effect on how you manage tasks or whole programs that are comprised of one or more tasks. The Hardware State When a task switch occurs, the task that is running must have its hardware context saved. The hardware context in its simplest form consists of the values in registers and processor flags at the time the task stopped executing. In the case of hardware interrupts, this is usually a no- brainer. The CPU takes care of it for you. If you must do it yourself, there are instructions on some processors to save all of the necessary registers onto the stack. Then all you have to do is switch stacks. When you restore a task, you switch to its stack and pop the registers off. The hardware state may also consist of memory context if you are using some form of hard- ware paging or memory management. This will depend on the processor you are using and possibly on external paging circuitry. You will have to determine this from the technical manuals you accumulate for your system. The Software State The software state can be a little more complicated than the hardware state and depends on how you implement your task management. The software state can consist of almost nothing, or it may be dozens of things that have to be saved and restored with each task switch. An example of an item that would be part of the software state is a simple variable in your operating system that you can check to see which task is running. When you change tasks, you change this variable to tell you which task is currently executing. The number of things you have to save may also depend on whether or not the processor assists you in saving and restor- ing the software state. Some processors (such as the Intel series) let you define software-state items in a memory structure that is partially managed by the operating system. This is where the hardware state is saved. It's actually easier than it sounds. You can define a structure to maintain the items you need for each task, then change a pointer to the current state structure for the task that is executing. H
30 Part II ■ Architecture and General Theory CPU Time CPU time is the single most important resource in a computer system. “It's 1 1:00 p.m. Do you know where your CPU is?” A funny question, but an important one. What instructions are executing? Where is it spending all its time? And why? When an application programmer writes a program, he or she generally assumes that it's the only thing running on the computer system. My first programs were written with that atti- tude. I didn't worry about how long the operating system took to do something, unless it seemed like it wasn't fast enough. Then I asked, “What is that thing doing?” When I used my first multiuser system, there were many times that I thought the system had died and gone to com- puter heaven. Yet, it would seem to return at its leisure. What was that thing doing? It was being shared with a few dozen other people staring at their terminals just like I was. We were each getting a piece of the pie, albeit not a very big piece. Microcomputers spoiled me. I had my very own processor, and I could pretty much figure out what it was doing most of the time. Many of the programs I wrote didn't require multitasking, and a single thread of instructions suited me just fine. It was in 1980 that I wrote my first time sheer, which was built into a small program on an 8-bit processor. It was crude, but effective. I knew exactly how long each of my two tasks were going to run. I also knew exactly how many microseconds it took to switch between them. There were so few factors to be concerned with on that early system, it was a breeze. In a multitasking operating system, ensuring that the CPU time is properly shared is the job of kernel and scheduling code. This will be the heart and brains of the system. Single Tasking What if you don't want a multitasking system? This is entirely possible, and in some cases a single-threaded system may be the best solution. In such a case, you basically have a hardware manager. 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 operating system is at its other jobs, such as file handling, interrupt servicing, and basic input/output. Many methods have been devised to allow single-tasking operating systems to share the CPU among pseudo-tasks. These have been in the form of special languages (Co-Pascal), and it can also be done with mini-multitasking kernels you include in your programs. These forms of CPU time sharing suffer from the disadvantage that they are not in complete control of all resources. They can, however, do an adequate job in many cases. You may also be aware that multitasking is simulated quite often in single-tasking systems by stealing time from hardware interrupts. This is done by tacking your code onto other code that is executed as a result of an interrupt.
Chapter 3 ■ The Tasking Model Multitasking I categorize forms of multitasking into two main groups: cooperative and. preemptive. An oper- ating system's tasking model can be one of these, or a combination of the two. In fact, many operating-system tasking models are a combination. There are other important factors that apply to these two types of multitasking, which I cover later in this chapter. The major point that you must understand here is that there are really only two ways a task switch will occur on any system: A task that has the processor gives it up, or it is preempted (that is, the processor is taken away from the task). H Cooperative Multitasking In a solely cooperative environment, each task runs until it decides to give up the processor. This can be for a number of reasons, but usually it is either to wait for a resource that is not immediately available or to pause when it has nothing to do, if the system allows this (a sleep or delay function). An important point here is that in a cooperative system, programs (or, more precisely, the programmer) may have to be aware of things that must be done to allow a task switch to happen. This implies that the programmer does part of the scheduling of task execu- tion. This is in the form of the task saying to the operating system, “Hey — I'm done with the CPU for now.” From there, the operating system decides which of the tasks will run next (if any are ready to run at all). It may not always be obvious when it happens, however. For in- stance, a program that is running makes an operating-system call to get the time of day. The operating system may be written in such a fashion that this (or any call into the operating- system code) will suspend that task and execute another one. I'm sure you've run across the need to delay the execution of your program for a short period of time, and you have used a library or system call with a name such as sleep ( ) or delay ( ). With these calls, you pass a parameter that indicates how long the program should pause be- fore resuming execution. This may be expressed in milliseconds, tenths of seconds, or even full seconds. If the operating system uses this period of time to suspend your task and execute an- other, you are cooperating with the operating system. It is then making wise use of your re- quest to delay or sleep. In many single-tasking systems, a call of this type may do nothing more than loop through a series of instructions or continually check a timer function until the de- sired time has passed. And yes, that's a waste of good CPU time if something else can be done with it. There is a major problem with a fully cooperative system. If a programmer writes code that doesn't give up the CPU (which means he doesn't make an operating-system call that some- how gets to the scheduler), he then monopolizes the CPU. If this isn't the task that the user is involved with, the screen and everything else looks frozen. Meanwhile, there's some task in there calculating pi to a zillion digits, and the computer looks dead for all practical purposes.
B Part II ■ Architecture and General Theory Because such “CPU hogs” are not only possible but inevitable, it is a good idea to have some form of a preemptive system, with the ability to cut a task off at the knees, if necessary. Preemptive Multitasking At the opposite end of the spectrum from a fully cooperative system is a preemptive system. This is an operating system that can stop a task dead in its tracks and start another one. I de- fined preemptive at the beginning of this chapter. To expand on that definition, when a task is preempted, it doesn't expect it. It does nothing to prepare for it. This can occur between any two CPU instructions that it is executing (with some exceptions discussed later). As I also mentioned earlier, this actually happens every time a hardware interrupt is activated. However, when a hardware interrupt occurs on most hardware platforms, the entire “state” of your task is not saved. Most of the time, it's only the hardware state, which includes registers, and maybe memory context, or a few other hardware-related things. Also, after the interrupt is finished, the CPU is returned to the task that was interrupted. Generally, hardware interrupts occur in order to pass information to a device driver, a program, or the operating system from an external device (hardware timer, disk drive, communications device, and so on). One of the most important hardware interrupts and one of the most useful to an operating system designer is a timer interrupt. On most platforms, there is hardware (programmable sup- port circuitry) that allows you to cause a hardware interrupt either at intervals or after a set period of time. The timer can help determine when to preempt. Task Scheduling Given the only two real ways a task switch can occur, you must now decide which task runs next. To refresh your memory, these two reasons are as follows: 1 . A task that has the processor decides to give it up. 2. The currently running task is preempted, which means the processor is taken away from the task without its knowledge. The next section is the tricky part. When do you switch tasks, to which task do you switch, and how long does that task get to run? Who, When, and How Long? The procedure or code that is responsible for determining which task is next is usually called the scheduler.
Chapter 3 ■ The Tasking Model In fully cooperative systems, the scheduler simply determines who's next. The programmer (or the task itself) determines how long a task will run. This is usually until it willingly surrenders the processor. In a preemptive system, the scheduler also determines how long a task gets to run. For the preemptive system, this adds the requirement of timing. How long does the current task run before you suspend it and start the next one? One thing that you can't lose sight of when considering scheduling is that computer programs are generally performing functions for a human (the user). They are also, quite often, connected to the outside world — communicating, controlling, or monitoring. This means there is often some desire or necessity to have certain jobs performed in a timely fashion so there is synchro- nization with outside events. This synchronization may be required for human interaction with the computer which is not that critical, or it may be for something extremely critical, such as ensuring your coffee is actually brewed when you walk out for a cup in a maniacal daze looking like Bill the Cat. This is where the scheduling fun really begins. H Scheduling Techniques In a multitasking system, only one task is running at a time (excluding the possibility of multi- processor systems). The rest of the tasks are waiting for their shot at the CPU, or waiting for outside resources such as I/O. As you can see, there is often a desire, or even a requirement, for some form of communication between several parties involved in the scheduling process. These parties include the program- mer, the task that's running, the scheduler, outside events, and maybe (if you're nice) the user. I'm going to present several techniques as if they were used alone. This way you can picture what each technique has to offer. Time Slicing Time slicing means you switch tasks based on set periods of execution time for each task — “a slice of time.” This implies the system is capable of preempting tasks without their permission or knowledge. In the simplest time-sliced systems, each task will get a fixed amount of time — all tasks will get the same slice — and they will be executed in the order they were created. A simple queueing system suffices. For example, each task gets 25 milliseconds. When a task's time is up, its com- plete hardware and software state is saved, and the next task in line is restored and executed. Many early multitasking operating systems were like this. They were perhaps not quite that simple, but they used a time-slicing scheduler based on a hardware timer to divide CPU time among the tasks that were ready to run.
Part II ■ Architecture and General Theory In some systems, a simple time-slicing scheme may be adequate or at least acceptable. For ex- ample, a multitasking system that is handling simple point-of-sale and ordering transactions at Ferdinand's Fast Food and Burger Emporium may be just fine as an equitably time-sliced sys- tem. The customer (and the greasy guy waiting on you behind the counter) would never see the slowdown as the CPU in the back room did a simple round-robin between all the tasks for the terminals. This would even take care of the situation where an employee falls asleep on the terminal and orders 8,000 HuMonGo Burgers by mistake. The others may see a slowdown, but it won't be on their terminals. (The others will be flipping 8,000 burgers.) Simple Cooperative Queueing The very simplest of cooperative operating-system schedulers could use a single queue system and execute the tasks on a first-come/first-served basis. When a task indicates it is done by making certain calls to the operating system, it is suspended and goes to the end of the queue. This is usually not very effective, and if a user interface is involved, it can make for some pretty choppy user interaction. But it may be just fine in some circumstances. Prioritized Cooperative Scheduling A logical step up from a simple first-in/first-out cooperative queue is to prioritize the tasks. Each task can be assigned a number (from highest to lowest priority) indicating its importance. This gives the scheduler something to work with. It can look at the priorities of those tasks that are ready-to-run and select the best based on what the programmer thinks is important. In a cooperative system, this means that of all the tasks that are ready to run, the one with the highest priority will be executed. This also implies that some may not be ready at all. They can be waiting for something such as I/O. Variable Time Slicing In a preemptive system, if you preempted a task without it first telling you it was OK to do so, you must assume that it is ready to run immediately. This also means you can't just assign simple priorities in a time-sliced system; otherwise, only the very highest would ever get to run. In a time-sliced preemptive system, it makes more sense to increase the time allocation for more important tasks than to execute the tasks in a sequence of equal time segments based solely on a priority assignment. The tasks that need more time can get it by asking for it or by the programmer (or user) telling the scheduler it needs it. Time allocation can even be increased by some form of signaling based on other outside events. Time slicing is a an old technique. When combined with an adequate form of interprocess communications or signaling (as discussed in Chapter 4, “Interprocess Communications”), it can serve admirably. But it has some major drawbacks. Who determines which task gets more
Chapter 3 ■ The Tasking Model time or which task will run more often? You generally can't ask the user if they need more time. (They will always say yes!) And the programmer can't even determine in advance how much time he or she will need, or how much time there is to go around en the system. Because it is still based on a preset period of time, there is always the possibility of being preempted before a certain important function is accomplished. It's pretty simple to calculate how much time you'll need for a communications program run- ning at full capacity at a known data rate. To know in advance if it will actually be used at that rate is, however, another story entirely. E Other Scheduling Factors You know as well as I do that things are rarely as simple as they seem. Users may not know how their computers operate, but they know what they want, including dependable, clean commu- nications and an interface that is responsive to their needs. To achieve maximum functional- ity, the machine must perform countless tasks about which the user may have no concept or interest. In case you haven't noticed, computers are everywhere. They do so many things for you that you simply accept them in your everyday life. Many of these things depend on real-time inter- action between the machine and the world to which it is connected. Some of the best examples of real-time computing are in robotics and equipment control. A computer in charge of climate control for a large building may be a good example, but it's not dramatic enough. Instead, let's look at one that controls a nuclear reactor and the various events at a nuclear power plant. The programs that run on this computer may have some snap deci- sions to make based on information from outside sensors or the user. If this computer has to wait 200 or more milliseconds before performing a critical safety task, it may spell disaster. Therefore, outside events must be able to force (or at least speed up) a task switch. This implies that some form of communication is required between the sensors (for example, hardware- interrupt service routines) and the scheduler. The programmer on this type of system must also be able to indicate to the operating system that certain programs or tasks are more impor- tant than others. (Should turning on the coffee pot for the midnight shift take priority over emergency cooling-water control?) Not many of us will ever write the software for nuclear power-plant control, but there are ev- eryday tasks that require real-time computing to operate smoothly. One of the most volatile reactions I can think of is when a user loses data from a communications program or an impor- tant fax is garbled because buffers went a little bit too long before being emptied or filled. If there's big money involved, this reaction can approximate meltdown conditions. This is criti- cal real-time stuff. Thus, when something that is out of the immediate control of the program- mer (and the CPU) must be handled within a specific period of time, it requires the ability to juggle tasks on the system in real-time.
H Part II ■ Architecture and General Theory In the case of the nuclear-reactor operating system, you definitely want to be able to preempt a task, and prioritization of these tasks will be critical. If I thought my operating system would be used in this fashion, I would have spent more time on the tasking model and also on inter- rupt service routines. But I opted to “get real” instead. If you have ever had the pleasure of writing communications-interrupt service routines on a system that has a purely time-sliced model, you know that it can lead to serious stress and maybe even hair loss. Operating systems that share the CPU among tasks by just dividing up a period of time and giving each task a share are the kind that respond poorly to outside events. This is not to say that time-sliced systems 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. The buffer will overflow. This is a simple example (actually a common problem), but it makes the point. In a message-based system, the ISR can send a message to the program ser- vicing it to tell it that the buffer is almost full. (“Hey, come do something with this data before I lose it!") I think you can see the advantages of a priority-based system, and maybe you can even see where it would be advantageous to combine a cooperative system (where the programmer can volun- tarily give up the CPU) with a preemptive time-sliced system. Mixed Scheduling Techniques As you can see, you have many options for scheduling techniques, as follows: ■ Cooperative task scheduling ■ Preemptive time slicing ■ Cooperative, prioritized task scheduling ■ Variable/prioritized time slicing ■ Any and all combinations of the above There are as many ways to mix the two basic types of task scheduling as there are copies of this book out there. No doubt, you have a few ideas of your own. I invite you to experiment with your own combinations. See what works for your applications. That's the only way you'll re- ally know for sure. In the next sections I'll present a few ways to mix them. All of these ways require some form of signaling or interprocess communications, and I discuss all of that in the next chapter. I didn't want to cloud the tasking issue with the required communications methods, even though these
Chapter 3 ■ The Tasking Model methods are very important and even help define the tasking model. In addition, all of the examples in the next sections have preemptive capabilities. To be honest, I can't picture a sys- tem without these capabilities, although such systems exist. Fully Time Sliced, Some Cooperation In this type of model, all tasks will be scheduled for execution and will execute for a predeter- mined amount of time. A task may, however, give up the CPU if it's no longer needed. This would put the task back into the queue to be executed when it surrendered the CPU. In this type of system, all tasks will get to run. You may opt to give certain tasks a larger execu- tion time based on external factors or the programmer's desires. But even when the task has nothing to do, it would still be scheduled to execute. If such were the case (having nothing to do) the task would simply surrender the CPU again. In a system that was designed for multiuser application sharing (such as UNIX originally was), time-slicing all the tasks is suitable (even desirable) in order to accomplish what was initially intended by the system builders. Users on a larger, solely time-sliced system will see the system slow down as the time is equitably divided between an increasing number of users or tasks. Writing communications tasks for these types of systems has always been a challenge (and that's being polite about it). Time Sliced, More Cooperative Building on the previous mix (some cooperation), additional signaling or messaging could be incorporated in the system to allow a task to indicate that it requires more time to execute. This could be in the form of a system call to indicate to the scheduler that this task should get a larger percentage of the available CPU time. You can probably picture in your head how this could get complicated as several tasks begin to tell the scheduler they need a larger chunk of time. There would have to be additional mecha- nisms to prevent poorly written tasks from simply gobbling up the CPU. This could be in the form of a maximum percentage of CPU time allowed, based on the number of tasks sched- uled. A very simple, rapid calculation would hold the reins on a CPU hog. Primarily Cooperative, Limited Time Slicing In this type of system, tasks are prioritized and generally run until they surrender the CPU. This means that the programmer sets the priority of the task and the scheduler abides by those wishes. Keep in mind that on a prioritized cooperative system, the task that is executing is al- ways the one with the highest priority found on the queue. Only in circumstances where multiple tasks of the same priority are queued to run would time slicing be invoked. These tasks would always be the highest priority tasks that are queued on the system. H
38 Part II ■ Architecture and General Theory This type of system would also have the capability to preempt a task in order to execute a higher priority task if one became queued (messaging from an Interrupt Service Routine). Primarily Cooperative, More Time Slicing This is similar to the previous model except you can slice a full range of priorities instead of just the highest priority that is running. For instance, if you have 256 priorities, 0 through 255 (the highest) may be sliced together, giving the lowest numbers (highest priorities) the greatest time slice. The Tasking Model I Chose I'll tell you what I wanted, then you can make your own choice based on my experiences. As I once read on a sugar packet, “Experience is a wonderful thing. It allows you to recognize a mistake when you make it again.” (No, it wasn't Ferdinand's Burger Emporium.) I wanted a priority-based, preemptive, multitasking, real-time operating system. My goal was not just to equitably share the processor among the tasks, but to use the programmer's desires as the primary factor. In such a system, prioritization of tasks is very important. I made MMURTL listen to the programmer. Remember the saying: “Be careful what you ask for — you may get it.” Let me repeat that my goal was a real-time system. I never wanted to miss outside events. To me, the outside events are even more important than placating the user, and in reality, the user is an outside event! This put my system in the category of “primarily coop- erative, limited time slicing.” As an illustration of my tasking model, MMURTL task switches occur for only two reasons:
- The currently running task can't continue because it needs more information from the outside world (outside its own data area), such as keystrokes, file access, timer services, or whatever. In such a case, it sends a “request” or non-specific message, goes into a “waiting” state, and the next task with the highest priority executes.
- An outside event (an interrupt) has sent a message to a task that has an equal or higher priority than the currently running task. This in itself does not immediately cause a task switch. The timer-interrupt routine, which provides a piece of the scheduling function, monitors the current task priority, as well as checking for the highest priority task that is queued to run. When it detects that a higher priority task is in a ready-to-run state, it will initiate a task switch as soon as it finds this. If it detects that one or more tasks with priorities equal to the current task are in the ready queue, it will initiate a task switch after a set period of time. This is the only “time slicing” that MMURTL does. This has the desired effect of ensuring that the high- est priority task is running when it needs to and also that all tasks of equal priority get a shot at the CPU. This is the preemptive nature of MMURTL.
Chapter 3 U The Tasking Model In Chapter 18, “Kernel Code,” and Chapter 20, “Timer Management Code,” I discuss in de- tail how I melded these two models. H Interrupt Handling Hardware interrupt service routines (ISRs) have always been interesting to me. I have learned two very valuable lessons concerning ISRs: Keep them short, and limit the functionality if at all possible. I bring them up in this chapter because how an operating system handles ISRs can affect the tasking model, and they will also be used for execution timing on some preemptive systems. Certain critical functions in the operating-system kernel and even some functions in device drivers will require you to suspend interrupts for brief periods of time. The less time the better. This will usually be during the allocation of critical shared operating-system resources and cer- tain hardware I/O functions. With the Intel processors, you even have a choice of whether the ISR executes as an indepen- dent task or executes in the context of a task that it interrupted. The task-based ISR is slower. A complete processor task change must occur for the ISR to execute, and another one must occur to return it to the task that was interrupted. Other processors may offer similar options. Go for the fastest option. Period. I decided that MMURTL ISRs would execute in the context of the task that they interrupted. This is a speed issue. It's faster — actually, much faster. This could have presented some protec- tion problems, and also the possibility of memory-management headaches, but because ISRs all execute code at the OS level of protection and all programs on the system share this com- mon OS-base addressing, the problems didn't surface. This was due to MMURTL's memory management methods. I discuss memory management in Chapter 5, “Memory Management,” and MMURTL's specific methods in Chapter 19, “Memory Management Code.” An important thing you should understand is that you don't have a big choice as to when an ISR executes. It is determined by hardware that may be completely out of your control, or even possibly the user's, and they are surely out of your control most of the time. For instance, who's to say when Mr. or Ms. User is going to press a key on the keyboard? That's right — only the user knows. Who will determine how long it actually takes to transfer several sectors from a disk device? There are too many factors involved to even prepare for it. This means that your operating system must be prepared at all times to be interrupted. Your only option (when you need one) is to suspend the interrupts either through the processor (which stops all of them except those of the non-maskable variety), or to suspend one or more through the Priority Interrupt Controller Unit.
/q Part II ■ Architecture and General Theory The real effect on the tasking model comes from the fact that some interrupts may convey information that should cause an eventual task switch. On systems that are primarily time sliced, the generic clock interrupt may be the basis of most task switches. After a period of time has elapsed, you switch tasks. In a cooperative environment, it may possibly be some form of intel- ligent message from an ISR that causes a task switch (if an ISR causes a task switch at all). When you get to Chapter 4, you'll see how messaging ties into and even helps to define your tasking model.