Multitasking

During this posting from some time ago, I wrote at length about the subject of interrupt prioritization. I wanted to demonstrate that I really did study System Software, and that therefore, I know something which I can pass along, about the subject of multitasking, which is a different subject.

The perspective from which I appreciate multitasking, is the perspective of the device-driver. According to what I was taught – and it is a bit dated – a device-driver had a top half and a bottom half. The top half was invoked by user-space processes, in a way that required a system-call, while the bottom half was invoked by interrupt requests, from the hardware. This latter detail did not changed if instead of using purely interrupt-driven I/O, the hardware and driver used DMA.

A system-call is also known as a software-interrupt.

The assumption which is made is that a user-space process can request a resource, thus invoking the top half of the device driver, but that the resource is recognized by the device driver as being busy, and that processes on the CPU run much faster than the I/O device. What the device-driver will do is change the state of the process which invoked it from ‘running’ to ‘blocked’, and it will make an entry in a table it holds, which identifies which process had requested the resource, as well as device-specific information, regarding what exactly the process asked for. Then, the top half of the device-driver will send whatever requests to the device that are needed, to initiate the I/O operation, and to ensure that at some future point in time, the resource and piece of data which were asked for, will become available. The top half of the device-driver then exits, and the process which invoked it will typically not be in a ‘running’ state anymore, unless for some reason the exact item being requested was immediately available. So as far as the top half is concerned, what usually needs to happen next is that some other process, which is in the ‘ready’ state, needs to be made ‘running’ by the kernel.

The bottom half of the device driver responds to the interrupt request from the device, which has signaled that something has become available, and looks up in the table belonging to the device driver, which process asked for that item, out of several possible processes which may be waiting on the same device. The bottom half then changes the state of the process in question from ‘blocked’ to ‘ready’, so that whenever a ‘ready’ process is about to be made ‘running’, the previously-blocked process will have become a contender.

The O/S kernel is then free to schedule the ‘ready’ process in question, making it ‘running’.

Now, aside from the fact that processes can be ‘running’, ‘ready’, or ‘blocked’, a modern O/S has a differentiation, between ‘active’ and ‘suspended’, that applies to ‘ready’ and ‘blocked’ processes. My System Software course did not go into great detail about this, because in order to understand why this is needed, one also needs to understand that there exists virtual memory, and that processes can be swapped out. The System Software course I took, did not cover virtual memory, but I have read about this subject privately, after taking the course.

The kernel could have several reasons to suspend a process, and the programmer should expect that his process can be suspended at any time. But one main reason why it would be suspended in practice, would be so that it can be swapped out. Only the kernel can make a ‘suspended’ process ‘active’ again.

In order to appreciate this detail, of ‘active’ as opposed to ‘suspended’, I suppose that the reader should also consider the Sleep() command, with which a currently ‘running’ process surrenders the CPU. In the distant past, we used a Yield() command, which was nonspecific about for how long the process was going to yield the CPU, but on any modern computer, the use of Yield() is deprecated (not only when we are programming in Java).

The Sleep() command takes two arguments, which become parameters in its implementation. The first states for how many seconds the process wishes to yield the CPU, while the second states a much shorter time unit – typically milliseconds. A sensible question to ask would be, ‘Why would the System Software specialists not use a single parameter?’

The reason for this is, that for shorter time-intervals, it makes no sense to swap out the process, while for longer time-intervals, it is feasible to do so. Thus, if the Sleep() command has a non-zero value as its first, slower parameter, the process will be ‘suspended’ in practice, while otherwise, in order to become inactive for only some number of milliseconds, it will remain a ‘ready-active’ process, in cue to be scheduled to ‘running’, but allowing other processes to run for the moment.

The way in which ‘ready-active’ processes are scheduled to ‘running’ on modern computers, has something to do with the fact that modern computers receive timing pulses as one of their hardware-interrupts. The interrupt service routine for a timing interrupt performs a miscellany of tasks, one of which is to look at ‘ready-active’ processes, and to analyze what their priority is, as well as whether their sleep milliseconds have elapsed.

This priority is not an interrupt priority level, nor an interrupt vector, with which kernel-space processes run, but a software-priority level, with which a computer is multitasking.

What this means is that in reality, the amount of time for which a process sleeps is not exact, and will in fact exceed the value it specified, because it will not get scheduled, until according to a timing interrupt, the elapsed milliseconds exceed the specified Sleep() parameter milliseconds. Programmers who need to write code that runs more-or-less in real-time need to take this into consideration. If there is more than one ‘ready-active’ process that fits this description, the process with the higher priority will be scheduled. But there could be two or more of them, that all have the same priority as well. And in this last case, there is an arbitrary order in which they form a cue. This order should at least allow all the processes to run eventually.

The use of Real-Time Operating Systems, has largely been replaced with this sort of logic, especially in cases where real-time scheduling is considered ‘preferable but not critical’. This includes cases in which users are just watching a video stream, and where the player-process can simply be made higher-priority, than processes which may run in the background, and do not run live. In fact, the terminology “Real-Time” has become distorted in consumer-grade operating systems, to refer to a single process, which will have a higher priority than all other processes, and which will be scheduled to ‘running’ within its requested time-interval, on that basis – delayed maximally by the frequency of the timing pulses.

The competition between ‘ready-active’ processes to become scheduled to ‘running’, is not a rescheduling event. Rescheduling involves possible ‘TLB Shootdowns’, as well as involving to swap processes out of physical RAM, and back in. The competition between ‘ready-active’ and ‘ready-suspended’ processes, does involve rescheduling, and therefore involves remapping virtual memory, and therefore also presents the most-efficient time at which they may be swapped in or out.

Technically, the remapping of virtual memory is called a ‘context-switch’, while actually to swap pages of memory in or out, is distinct. They may not go together, if what is being swapped are pages of data instead of code.

And data or code which has been swapped out, also represents a resource which is temporarily unavailable, when other code asks for it. All virtual data must at some point get swapped back into real, physical RAM, before it can be used. But the request for virtual memory additionally involves the ‘Translation Lookaside Buffer’, the ‘TLB’, and the way that works does not belong to the subject of this posting.

Dirk

 

Print Friendly, PDF & Email

Leave a Reply

Your email address will not be published. Required fields are marked *

Please Prove You Are Not A Robot *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>