Preemption (computing)
Encyclopedia
In computing
, preemption (sometimes pre-emption) is the act of temporarily interrupting a task
being carried out by a computer system
, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch
. It is normally carried out by a privileged
task or part of the system known as a preemptive scheduler
, which has the power to preempt, or interrupt, and later resume, other tasks in the system.
s which, if not permitted to run to completion, would tend to produce race condition
s resulting in deadlock
. Barring the scheduler from preempting tasks while they are processing kernel functions simplifies the kernel design at the expense of system responsiveness. The distinction between user mode
and kernel mode, which determines privilege level within the system, may also be used to distinguish whether a task is currently preemptible.
Some modern systems have preemptive kernels, designed to permit tasks to be preempted even when in kernel mode. Examples of such systems are Solaris 2.0/SunOS 5.0, Windows NT
, the Linux kernel
2.6 and 3.x, AIX and some BSD systems (NetBSD
, since version 5).
Other systems improve responsiveness by a microkernel
design. This moves most of the system logic out of the kernel and into user mode processes, which are preemptible.
In simple terms: Preemptive multitasking involves the use of an interrupt mechanism which suspends the currently executing process and invokes a scheduler to determine which process should execute next. Therefore all processes will get some amount of CPU time at any given time.
In preemptive multitasking, the operating system kernel can also initiate a context switch
to satisfy the scheduling policy's priority constraint, thus preempting the active task. In general, preemption means "prior seizure of". When the high priority task at that instance seizes the currently running task, it is known as preemptive scheduling.
The term "preemptive multitasking" is sometimes mistakenly used when the intended meaning is more specific, referring instead to the class of scheduling policies known as time-shared scheduling, or time-sharing
.
Preemptive multitasking allows the computer system to more reliably guarantee each process a regular "slice" of operating time. It also allows the system to rapidly deal with important external events like incoming data, which might require the immediate attention of one or another process.
At any specific time, processes can be grouped into two categories: those that are waiting for input or output (called "I/O bound
"), and those that are fully utilizing the CPU ("CPU bound
"). In early systems, processes would often "poll", or "busywait
" while waiting for requested input (such as disk, keyboard or network input). During this time, the process was not performing useful work, but still maintained complete control of the CPU. With the advent of interrupts and preemptive multitasking, these I/O bound processes could be "blocked", or put on hold, pending the arrival of the necessary data, allowing other processes to utilize the CPU. As the arrival of the requested data would generate an interrupt, blocked processes could be guaranteed a timely return to execution.
Although multitasking techniques were originally developed to allow multiple users to share a single machine, it soon became apparent that multitasking was useful regardless of the number of users. Many operating systems, from mainframes down to single-user personal computers and no-user control systems (like those in robotic spacecraft
), have recognized the usefulness of multitasking support for a variety of reasons. Multitasking makes it possible for a single user to run multiple applications at the same time, or to run "background" processes while retaining control of the computer.
An interrupt
is scheduled to allow the operating system
kernel to switch between processes when their time slices expire, effectively allowing the processor’s time to be shared between a number of tasks, giving the illusion that it is dealing with these tasks simultaneously, or concurrently. The operating system which controls such a design is called a multi-tasking system.
, Linux
, iOS and Android.
Some of the earliest operating systems available to home users featuring preemptive multitasking were Sinclair QDOS
(1984) and Amiga OS (1985). These both ran on Motorola 68000
-family microprocessors without memory management. Amiga OS used dynamic loading
of relocatable code blocks ("hunks
" in Amiga jargon) to multitask preemptively all processes in the same flat address space.
Early PC operating systems such as MS-DOS
and PC DOS, did not support multitasking at all, however alternative operating systems such as MP/M-86 (1981) and Concurrent CP/M-86 did support preemptive multitasking. Other Unix-like
systems including MINIX
and Coherent
provided preemptive multitasking on 1980s-era personal computers.
Later DOS versions natively supporting preemptive multitasking/multithreading include Concurrent DOS, Multiuser DOS
, Novell DOS, Caldera OpenDOS and DR-DOS
7.02 and higher. Since Concurrent DOS 386, they could also run multiple DOS programs concurrently in virtual DOS machines. Novell NetWare
, Microsoft Windows
and OS/2
systems introduced cooperative multitasking to the PC, but did not support preemptive multitasking.
The earliest version of Windows to support a limited form of preemptive multitasking was Windows 2.1x
, which used the Intel 80386
's Virtual 8086 mode
to run DOS applications in virtual 8086 machine
s--commonly known as "DOS boxes"--which could be preempted. In Windows 95, 98, and Me
, 32-bit applications were made preemptive by running each one in a separate address space, but 16 bit applications remained cooperative. The Windows NT
family (including 2000
, XP
, Vista
, and 7) has always supported preemptive multitasking.
OS/2
version 2.0 onwards supported preemptive multitasking of native applications and OS/2 Warp, IBM's rewrite of OS/2 targeted at 386 systems, also permitted several different Windows sessions to be multitasked preemptively.
Unix
and Unix-like
systems (such as Linux
, BSD and Mac OS X
), VMS
, and other systems used in the academic and medium-to-large business markets, have always supported preemptive multitasking.
Although there were plans to upgrade the cooperative multitasking Mac OS to a preemptive model (and a preemptive API did exist in Mac OS 9
, although in a very limited sense and rarely exploited), these were abandoned in favor of Mac OS X
, a hybrid of MacOS and the NextStep
operating system, which is based on the Mach kernel
and provides Unix-like preemptive multitasking.
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, preemption (sometimes pre-emption) is the act of temporarily interrupting a task
Task (computers)
A task is an execution path through address space. In other words, a set of program instructions that are loaded in memory. The address registers have been loaded with the initial address of the program. At the next clock cycle, the CPU will start execution, in accord with the program. The sense is...
being carried out by a computer system
Computer
A computer is a programmable machine designed to sequentially and automatically carry out a sequence of arithmetic or logical operations. The particular sequence of operations can be changed readily, allowing the computer to solve more than one kind of problem...
, without requiring its cooperation, and with the intention of resuming the task at a later time. Such a change is known as a context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
. It is normally carried out by a privileged
Ring (computer security)
In computer science, hierarchical protection domains, often called protection rings, are a mechanism to protect data and functionality from faults and malicious behaviour . This approach is diametrically opposite to that of capability-based security.Computer operating systems provide different...
task or part of the system known as a preemptive scheduler
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
, which has the power to preempt, or interrupt, and later resume, other tasks in the system.
User mode and kernel mode
In any given system design, some operations performed by the system may not be preemptible. This usually applies to kernel functions and service interruptInterrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
s which, if not permitted to run to completion, would tend to produce race condition
Race condition
A race condition or race hazard is a flaw in an electronic system or process whereby the output or result of the process is unexpectedly and critically dependent on the sequence or timing of other events...
s resulting in deadlock
Deadlock
A deadlock is a situation where in two or more competing actions are each waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg"...
. Barring the scheduler from preempting tasks while they are processing kernel functions simplifies the kernel design at the expense of system responsiveness. The distinction between user mode
User space
A conventional computer operating system usually segregates virtual memory into kernel space and user space. Kernel space is strictly reserved for running the kernel, kernel extensions, and most device drivers...
and kernel mode, which determines privilege level within the system, may also be used to distinguish whether a task is currently preemptible.
Some modern systems have preemptive kernels, designed to permit tasks to be preempted even when in kernel mode. Examples of such systems are Solaris 2.0/SunOS 5.0, Windows NT
Windows NT
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...
, the Linux kernel
Linux kernel
The Linux kernel is an operating system kernel used by the Linux family of Unix-like operating systems. It is one of the most prominent examples of free and open source software....
2.6 and 3.x, AIX and some BSD systems (NetBSD
NetBSD
NetBSD is a freely available open source version of the Berkeley Software Distribution Unix operating system. It was the second open source BSD descendant to be formally released, after 386BSD, and continues to be actively developed. The NetBSD project is primarily focused on high quality design,...
, since version 5).
Other systems improve responsiveness by a microkernel
Microkernel
In computer science, a microkernel is the near-minimum amount of software that can provide the mechanisms needed to implement an operating system . These mechanisms include low-level address space management, thread management, and inter-process communication...
design. This moves most of the system logic out of the kernel and into user mode processes, which are preemptible.
Preemptive multitasking
The term preemptive multitasking is used to distinguish a multitasking operating system, which permits preemption of tasks, from a cooperative multitasking system wherein processes or tasks must be explicitly programmed to yield when they do not need system resources.In simple terms: Preemptive multitasking involves the use of an interrupt mechanism which suspends the currently executing process and invokes a scheduler to determine which process should execute next. Therefore all processes will get some amount of CPU time at any given time.
In preemptive multitasking, the operating system kernel can also initiate a context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
to satisfy the scheduling policy's priority constraint, thus preempting the active task. In general, preemption means "prior seizure of". When the high priority task at that instance seizes the currently running task, it is known as preemptive scheduling.
The term "preemptive multitasking" is sometimes mistakenly used when the intended meaning is more specific, referring instead to the class of scheduling policies known as time-shared scheduling, or time-sharing
Time-sharing
Time-sharing is the sharing of a computing resource among many users by means of multiprogramming and multi-tasking. Its introduction in the 1960s, and emergence as the prominent model of computing in the 1970s, represents a major technological shift in the history of computing.By allowing a large...
.
Preemptive multitasking allows the computer system to more reliably guarantee each process a regular "slice" of operating time. It also allows the system to rapidly deal with important external events like incoming data, which might require the immediate attention of one or another process.
At any specific time, processes can be grouped into two categories: those that are waiting for input or output (called "I/O bound
IO bound
In computer science, I/O bound refers to a condition in which the time it takes to complete a computation is determined principally by the period of time spent waiting for input/output operations to be completed. This is the opposite of a task being CPU bound...
"), and those that are fully utilizing the CPU ("CPU bound
CPU bound
In computer science, CPU bound is when the time for a computer to complete a task is determined principally by the speed of the central processor: processor utilization is high, perhaps at 100% usage for many seconds or minutes...
"). In early systems, processes would often "poll", or "busywait
Busy waiting
In software engineering, busy-waiting or spinning is a technique in which a process repeatedly checks to see if a condition is true, such as whether keyboard input is available, or if a lock is available. Spinning can also be used to generate an arbitrary time delay, a technique that was necessary...
" while waiting for requested input (such as disk, keyboard or network input). During this time, the process was not performing useful work, but still maintained complete control of the CPU. With the advent of interrupts and preemptive multitasking, these I/O bound processes could be "blocked", or put on hold, pending the arrival of the necessary data, allowing other processes to utilize the CPU. As the arrival of the requested data would generate an interrupt, blocked processes could be guaranteed a timely return to execution.
Although multitasking techniques were originally developed to allow multiple users to share a single machine, it soon became apparent that multitasking was useful regardless of the number of users. Many operating systems, from mainframes down to single-user personal computers and no-user control systems (like those in robotic spacecraft
Robotic spacecraft
A robotic spacecraft is a spacecraft with no humans on board, that is usually under telerobotic control. A robotic spacecraft designed to make scientific research measurements is often called a space probe. Many space missions are more suited to telerobotic rather than crewed operation, due to...
), have recognized the usefulness of multitasking support for a variety of reasons. Multitasking makes it possible for a single user to run multiple applications at the same time, or to run "background" processes while retaining control of the computer.
Time slice
The period of time for which a process is allowed to run in a preemptive multitasking system is generally called the time slice, or quantum. The scheduler is run once every time slice to choose the next process to run. If the time slice is too short then the scheduler will consume too much processing time.An interrupt
Interrupt
In computing, an interrupt is an asynchronous signal indicating the need for attention or a synchronous event in software indicating the need for a change in execution....
is scheduled to allow the operating system
Operating system
An operating system is a set of programs that manage computer hardware resources and provide common services for application software. The operating system is the most important type of system software in a computer system...
kernel to switch between processes when their time slices expire, effectively allowing the processor’s time to be shared between a number of tasks, giving the illusion that it is dealing with these tasks simultaneously, or concurrently. The operating system which controls such a design is called a multi-tasking system.
Systems supporting preemptive multitasking
Today, nearly all operating systems support preemptive multitasking, including the current versions of Windows, Mac OSMac OS
Mac OS is a series of graphical user interface-based operating systems developed by Apple Inc. for their Macintosh line of computer systems. The Macintosh user experience is credited with popularizing the graphical user interface...
, Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, iOS and Android.
Some of the earliest operating systems available to home users featuring preemptive multitasking were Sinclair QDOS
Sinclair QDOS
QDOS is the multitasking operating system found on the Sinclair QL personal computer and its clones...
(1984) and Amiga OS (1985). These both ran on Motorola 68000
Motorola 68000
The Motorola 68000 is a 16/32-bit CISC microprocessor core designed and marketed by Freescale Semiconductor...
-family microprocessors without memory management. Amiga OS used dynamic loading
Dynamic loading
Dynamic loading is a mechanism by which a computer program can, at run time, load a library into memory, retrieve the addresses of functions and variables contained in the library, execute those functions or access those variables, and unload the library from memory...
of relocatable code blocks ("hunks
Amiga Hunk
Hunk is the executable file format of tools and programs of the Amiga Operating System based on Motorola 68000 CPU and other processors of the same family....
" in Amiga jargon) to multitask preemptively all processes in the same flat address space.
Early PC operating systems such as MS-DOS
MS-DOS
MS-DOS is an operating system for x86-based personal computers. It was the most commonly used member of the DOS family of operating systems, and was the main operating system for IBM PC compatible personal computers during the 1980s to the mid 1990s, until it was gradually superseded by operating...
and PC DOS, did not support multitasking at all, however alternative operating systems such as MP/M-86 (1981) and Concurrent CP/M-86 did support preemptive multitasking. Other Unix-like
Unix-like
A Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification....
systems including MINIX
Minix
MINIX is a Unix-like computer operating system based on a microkernel architecture created by Andrew S. Tanenbaum for educational purposes; MINIX also inspired the creation of the Linux kernel....
and Coherent
Coherent (operating system)
The Coherent operating system was a Version 7 Unix clone by the now-defunct Mark Williams Company, originally produced for the PDP-11 in 1980. A port was introduced in 1983 as the first Unix-like system for IBM PC compatible computers....
provided preemptive multitasking on 1980s-era personal computers.
Later DOS versions natively supporting preemptive multitasking/multithreading include Concurrent DOS, Multiuser DOS
Multiuser DOS
Multiuser DOS is a soft real-time multi-user multi-tasking operating system for IBM PC-compatible microcomputers.An evolution of the older Concurrent CP/M-86 and Concurrent DOS operating systems, it was originally developed by Digital Research and later further developed by Novell...
, Novell DOS, Caldera OpenDOS and DR-DOS
DR-DOS
DR-DOS is an MS-DOS-compatible operating system for IBM PC-compatible personal computers, originally developed by Gary Kildall's Digital Research and derived from Concurrent PC DOS 6.0, which was an advanced successor of CP/M-86...
7.02 and higher. Since Concurrent DOS 386, they could also run multiple DOS programs concurrently in virtual DOS machines. Novell NetWare
Novell NetWare
NetWare is a network operating system developed by Novell, Inc. It initially used cooperative multitasking to run various services on a personal computer, with network protocols based on the archetypal Xerox Network Systems stack....
, Microsoft Windows
Microsoft Windows
Microsoft Windows is a series of operating systems produced by Microsoft.Microsoft introduced an operating environment named Windows on November 20, 1985 as an add-on to MS-DOS in response to the growing interest in graphical user interfaces . Microsoft Windows came to dominate the world's personal...
and OS/2
OS/2
OS/2 is a computer operating system, initially created by Microsoft and IBM, then later developed by IBM exclusively. The name stands for "Operating System/2," because it was introduced as part of the same generation change release as IBM's "Personal System/2 " line of second-generation personal...
systems introduced cooperative multitasking to the PC, but did not support preemptive multitasking.
The earliest version of Windows to support a limited form of preemptive multitasking was Windows 2.1x
Windows 2.1x
Windows 2.1x is a family of Microsoft Windows graphical user interface-based operating environments.Windows/286 2.10 and Windows/386 2.10 were released on May 27, 1988, less than a year after the release of Windows 2.0...
, which used the Intel 80386
Intel 80386
The Intel 80386, also known as the i386, or just 386, was a 32-bit microprocessor introduced by Intel in 1985. The first versions had 275,000 transistors and were used as the central processing unit of many workstations and high-end personal computers of the time...
's Virtual 8086 mode
Virtual 8086 mode
In the 80386 microprocessor and later, virtual 8086 mode allows the execution of real mode applications that are incapable of running directly in protected mode while the processor is running a protected mode operating system.VM86 mode uses a segmentation scheme identical to that of real mode In...
to run DOS applications in virtual 8086 machine
Virtual machine
A virtual machine is a "completely isolated guest operating system installation within a normal host operating system". Modern virtual machines are implemented with either software emulation or hardware virtualization or both together.-VM Definitions:A virtual machine is a software...
s--commonly known as "DOS boxes"--which could be preempted. In Windows 95, 98, and Me
Windows 9x
Windows 9x is a generic term referring to a series of Microsoft Windows computer operating systems produced since 1995, which were based on the original and later modified Windows 95 kernel...
, 32-bit applications were made preemptive by running each one in a separate address space, but 16 bit applications remained cooperative. The Windows NT
Windows NT
Windows NT is a family of operating systems produced by Microsoft, the first version of which was released in July 1993. It was a powerful high-level-language-based, processor-independent, multiprocessing, multiuser operating system with features comparable to Unix. It was intended to complement...
family (including 2000
Windows 2000
Windows 2000 is a line of operating systems produced by Microsoft for use on personal computers, business desktops, laptops, and servers. Windows 2000 was released to manufacturing on 15 December 1999 and launched to retail on 17 February 2000. It is the successor to Windows NT 4.0, and is the...
, XP
Windows XP
Windows XP is an operating system produced by Microsoft for use on personal computers, including home and business desktops, laptops and media centers. First released to computer manufacturers on August 24, 2001, it is the second most popular version of Windows, based on installed user base...
, Vista
Windows Vista
Windows Vista is an operating system released in several variations developed by Microsoft for use on personal computers, including home and business desktops, laptops, tablet PCs, and media center PCs...
, and 7) has always supported preemptive multitasking.
OS/2
OS/2
OS/2 is a computer operating system, initially created by Microsoft and IBM, then later developed by IBM exclusively. The name stands for "Operating System/2," because it was introduced as part of the same generation change release as IBM's "Personal System/2 " line of second-generation personal...
version 2.0 onwards supported preemptive multitasking of native applications and OS/2 Warp, IBM's rewrite of OS/2 targeted at 386 systems, also permitted several different Windows sessions to be multitasked preemptively.
Unix
Unix
Unix is a multitasking, multi-user computer operating system originally developed in 1969 by a group of AT&T employees at Bell Labs, including Ken Thompson, Dennis Ritchie, Brian Kernighan, Douglas McIlroy, and Joe Ossanna...
and Unix-like
Unix-like
A Unix-like operating system is one that behaves in a manner similar to a Unix system, while not necessarily conforming to or being certified to any version of the Single UNIX Specification....
systems (such as Linux
Linux
Linux is a Unix-like computer operating system assembled under the model of free and open source software development and distribution. The defining component of any Linux system is the Linux kernel, an operating system kernel first released October 5, 1991 by Linus Torvalds...
, BSD and Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
), VMS
OpenVMS
OpenVMS , previously known as VAX-11/VMS, VAX/VMS or VMS, is a computer server operating system that runs on VAX, Alpha and Itanium-based families of computers. Contrary to what its name suggests, OpenVMS is not open source software; however, the source listings are available for purchase...
, and other systems used in the academic and medium-to-large business markets, have always supported preemptive multitasking.
Although there were plans to upgrade the cooperative multitasking Mac OS to a preemptive model (and a preemptive API did exist in Mac OS 9
Mac OS 9
Mac OS 9 is the final major release of Apple's Mac OS before the launch of Mac OS X. Introduced on October 23, 1999, Apple positioned it as "The Best Internet Operating System Ever," highlighting Sherlock 2's Internet search capabilities, integration with Apple's free online services known as...
, although in a very limited sense and rarely exploited), these were abandoned in favor of Mac OS X
Mac OS X
Mac OS X is a series of Unix-based operating systems and graphical user interfaces developed, marketed, and sold by Apple Inc. Since 2002, has been included with all new Macintosh computer systems...
, a hybrid of MacOS and the NextStep
NEXTSTEP
NeXTSTEP was the object-oriented, multitasking operating system developed by NeXT Computer to run on its range of proprietary workstation computers, such as the NeXTcube...
operating system, which is based on the Mach kernel
Mach (kernel)
Mach is an operating system kernel developed at Carnegie Mellon University to support operating system research, primarily distributed and parallel computation. Although Mach is often mentioned as one of the earliest examples of a microkernel, not all versions of Mach are microkernels...
and provides Unix-like preemptive multitasking.