Department of Computer Science Course: CS 3725

Processes

We have already used the term ``process'' as an entity to which the operating system allocates resources. At this point, it is worth while to define the term process more clearly.

A process is a particular instance of a program which is executing. It includes the code for the program, the current value of the program counter, all internal registers, and the current value of all variables associated with the program (i.e, the memory state.) Different (executing) instances of the same program are different processes.

In some (most) systems, the output of one process can be used as an input to another process (such as a pipe, in UNIX); e.g.,

          cat   file1   file2   |   sort

Here there are two processes, cat and sort, with their data specified. When this command is executed, the processes cat and sort are particular instances of the programs cat and sort.

Note that these two processes can exist in at least 3 states: active, or running; ready to run, but temporarily stopped because the other process is running; or blocked -- waiting for data from another process. Figure  shows such a minimal process state diagram.

  
Figure: A simple process state diagram

The transitions have the following meanings:

(1) blocked, waiting for data (2), (3) another process becomes active (4) data has become available.

Transition (2) happens as a result of the process scheduling algorithm. ``Real'' operating systems have somewhat more complex process state diagrams. Figure  shows a simplified process state diagram for the UNIX operating system.

  
Figure: A simplified state diagram for the UNIX operating system.

Note that, in the UNIX system, a process executes in either user or kernel mode.

One of the most fundamental resources to be allocated among processes (in a single CPU system) is the main memory. A number of allocation strategies are possible:

(1) single storage allocation -- here all of main memory (except for space for the operating system nucleus, or ``kernel'') is given to the current process.

Two problems can arise here:

1. the process may require less memory than is available (wasteful of memory)
2. the process may require more memory than is available.

The second is a serious problem, which can be addressed in several ways. The simplest of these is by ``static overlay'', where a block of data or code not currently required is overwritten in memory by the required code or data. This was originally done by the programmer, who embedded commands to load the appropriate blocks of code or data directly in the source code. Later, loaders were available which analyzed the code and data blocks and loaded the appropriate blocks when required.

This type of memory management is still used in primitive operating systems (e.g., DOS).

Early memory management -- ``static overlay'' -- done under user program control:

Figure  shows the functional dependence of ``code segments''.

  
Figure: The functional dependence of code segments - analysis for static overlay

Clearly, ``segments'' at the same level in the tree need not be memory resident at the same time. e.g., in the above example, it would be appropriate to have segments (1,3,9) and (5,7) in memory simultaneously, but not, say, (2,3).

(2) Contiguous Allocation

In the late 1960's, operating systems began to control, or ``manage'' more resources, including memory. The first attempts used very simple memory management strategies. One very early system was Fixed-Partition Allocation, as shown in Figure .

  
Figure: Fixed partition allocation

This system did not offer a very efficient use of memory; the systems manager had to determine an appropriate memory partition, which was then fixed. This limited the number of processes, and the mix of processes which could be run at any given time. Also, in this type of system, dynamic data structures pose difficulties.

An obvious improvement over fixed-partition allocation was Movable-Partition Allocation, shown in Figure .

  
Figure: Movable partition allocation

Here, dynamic data structures are still a problem -- jobs are placed in areas where they fit at the time of loading. A ``new'' problem here is memory fragmentation -- it is usually much easier to find a block of memory for a small job than for a large job. Eventually, memory may contain many small jobs, separated by ``holes'' too small for any of the queued processes. This effect may seriously reduce the chances of running a large job.

One solution to this problem is to allow dynamic reallocation of processes running in memory. Figure . shows the result of dynamic reallocation of Job 5 after Job 1 terminates.

  
Figure: dynamic reallocation of partitions

In this system, the whole program must be moved, which may have a penalty in execution time. This is a tradeoff -- how frequently memory should be ``compacted'' against the performance lost to memory fragmentation. Again, dynamic memory allocation is still difficult, but less so than for the other systems.

With the possibility of dynamic data structures, a new problem arises. The problem is garbage collection -- the safe removal of dynamic data elements.

Modern processors generally manage memory using a scheme called virtual memory -- here all processes appear to have access to all of the memory available to the system. A combination of special hardware and the operating system maintains some parts of each process in main memory, but the process is actually stored on disk memory. (Main memory acts somewhat like a cache for processes -- only the active portion of the process is stored there. The remainder is loaded as needed, by the operating system.) We will look in some detail at how processes are ``mapped'' from virtual memory into physical memory.

The idea of virtual memory can be applied to the whole processor, so we can think of it as a virtual system, where every process has access to all system resources, and where separate (non-communicating) processes cannot interfere with each other. In fact, we are already used to thinking of computers in this way. We are familiar with the sharing of physical resources like printers (through the use of a print queue) as well as sharing access to the processor itself in a multitasking environment.