This state diagram is perhaps the most important in the entire study of Operating Systems, so it is important to understand what is happening in each state and how a process transitions from one state to another.

Here is what is happening at each transition.

1. Ready to Running This event is triggered by a kernel operation called the process scheduler or dispatcher, which selects a process in the Ready state and starts running it.
2. Running to Blocked This event would be triggered when a running process attempts to execute an IO operation such as a read or write or otherwise needs a resource which is not currently available. Accessing data from a disk takes several orders of magnitude longer than executing statements in the CPU, and so it makes sense for a process which is waiting for data from a disk to give up the CPU to another process while it is waiting.
3. Blocked to Ready A process is in the waiting state when it is waiting for an event to occur, so when this event occurs, it moves from Waiting to Ready. For example, a process which was waiting for an IO operation would be unblocked when the IO operation was completed and the data had been copied to or from user space.
4. Running to Ready A process moves from Running to Ready when the Process Scheduler determines that there is a process with a higher priority in the Ready queue. In many operating systems, if there are several runnable processes, each process is allocated a time slice or time quantum, and when this time slice ends, the running process is replaced by another process which is also ready to run, and the formerly running process is returned to the ready queue.
5. New to Ready When a new process is created, it is moved to the ready state.
6. Running to terminated There are two ways that a process can terminate. A normal termination occurs when the process reaches the end of main or calls the exit routine. An abnormal termination occurs when a process encounters an abnormal condition from which it cannot recover, such as a segmentation fault (memory access error) or when the user manually terminates the process.

The process of switching from one process to another is called Context Switching. If there are several runnable processes, all of them are loaded into memory. To execute a context switch, the kernel has to store the contents of all of the registers for the process which was formerly running, copy the register values for the new process into the registers, and start executing the next instruction of the new process. Thus, context switching can be done quickly.

This scenario is an oversimplification. The process scheduler is itself a process and so has to be swapped into the running state, although it is in the kernel, and is always in memory. Also, other kinds of interrupts may occur. In particular, clock interrupts happen many times a second, and so the running process has to be preempted to handle the new interrupt.

Here is a table from the text showing everything that happens when an interrupt occurs.

It should be obvious that multiprogramming can improve CUP utilization. Here is a graph showing theoretical CPU utilization as a function of the number of processes available to run (degree of multiprogramming), and the amount of time that each process spends performing I/O operations (20%, 50%, or 80%).

If processes are I/O bound, that is, spend most of their time performing I/O operations, many processes can be in memory at the same time.

The layout of a process in memory

Historically, a C program consists of the following pieces.

text segment also known as the code segment

the machine instructions executed by the CPU

initialized data segment

global variables which are initialized automatically

uninitialized data segment

(call the bss) global variables which are not initialized (e.g. long sum[1000])

stack

storage for automatic variables along with other info about a function call (i.e. return address, register values)

heap

memory for dynamic memory allocation. When a running program asks for more memory by calling malloc in a C program or new in a C++ program, the memory is found in the heap.

user area

maintains housekeeping info about the process (running time, open file descriptors, how it responds to signals)

page tables

used by the memory management system

The Run Time Stack

The concept of the run time stack is important. The normal state of affairs when a process is running is for a function to run for a while, then this function calls another function. Execution stops in the calling function and starts running in the called function. The called function may in turn call another function. Each time a new function is called, a new entity, called a stack frame is created and placed on the run time stack. A stack frame contains the following:

• memory for arguments which are passed to the function
• memory for any automatic variables (variables which are local to that function)
• the return address (the address of the first statement to be executed after the function terminates. This will be in the calling function, which will be the stack frame directly below the current stack frame).
• the register values to be restored to the old function when the current function terminates

Notice that both the stack and the heap vary in size during the execution of a program. As the run time stack increases, it grows upward, and as the heap increases, it grows downward.

File formats

The image of an executable which is stored on a disk usually contains header information which tells the operating system how to load and start the process. This is needed because when the executable image is created, the exact memory address where it will be loaded is not known. When the process is actually loaded, the system has to perform some address relocation. This usually involves setting values in various registers. To facilitate this, the header will contain information on the various segments. It may also have a symbol table.

There are a number of different formats for this. Many Unix systems use the coff (Common Object File Format), but most implementations of Linux use ELF(Executable and Linkable Format).

Windows also supports several file formats. The usual is the .exe format. You may have noticed that even a very simple program, which could not be more than a few lines of executable code, results in a executable file of tens of thousands of bytes. This is because of the extensive header information.

In the very early days of DOS (and CP/M), executables were often in the .com format. This was very small, with essentially no header information, but the size of the file was restricted to one segment (64K).

Device drivers and other kernel code are often in the .sys format. This is raw binary code with no relocation information.

The Process Control Blocks in the Kernel

The kernel needs a way to store housekeeping information about each current process. This information is stored in a structure which is often called a process control block. Typically when a new process is created, a new process control block is created and the appropriate values are filled in. A typical process control block might contain such fields as the following:

• Data for restarting the process
  • Register values, including stack pointers, program status word, program counter etc.
  • Pointer to the page table or tables
• Process identification information
  • Process Id
  • Owner
  • Parent process id
  • command string
  • Process group
• Housekeeping information
  • start time
  • total cpu time to date
  • open file descriptors or handles
  • current working directory
  • root directory
  • scheduling priority
• List of unhandled signals
• Thread information

Process creation and termination

All operating systems need a mechanism for creating new processes and terminating processes. We will discuss system calls to do this in the next section. When a new process is created, the system must allocate a new process control block, fill in the initial values for it, allocate memory for the new process, and copy at least some of the code for the new process into memory.

A newly created process is put in the ready queue. The process scheduler may decided that the newly created process has a higher priority and thus it will preempt the currently running process, running the new process immediately and placing the formerly running process on the ready queue.

We can distinguish two types of process termination, normal and abnormal. A normal termination of a process occurs either when the program reaches the end of main or when it executes the exit system call. Normal termination can only occur when the program is in the running state. An abnormal termination occurs when the program encounters an error condition from which it cannot recover, such as a memory exception fault (a segmentation fault in Unix jargon), or it is killed by another process. (You can generally kill a currently running process by hitting Control-c).

Regardless of how a process is terminated, the operating system will free up the memory used by the process, destroy the process control block for that process, and, in some systems, notify the parent process.

Unix Process System Calls

Now that you know what a process is, we can look at the system calls which create new processes. This module will discuss the Unix system calls related to processes, the next module will discuss the Win32 APIs related to processes.

The fork system call

On classical Unix systems , all processes are created with the fork() system call. This system call creates a new process which is an exact duplicate of the calling process. The process which called fork() is referred to as the parent and the new process which fork creates is called the child. Both processes, the parent and the child, are runnable and when run, start immediately after the fork system call.

Here is the function prototype

     #include <sys/types.h>
     #include <unistd.h>

     pid_t fork(void);

The data type pid_t refers to the type of a process id, which is an unsigned int on all systems that I am aware of. The return value of fork() is important. In the parent, the value returned from fork() is the process id of the child. In the child, the value returned from fork() is zero. In the case of an error, fork() will return a negative value.

Here is a simple program which demonstrates this.

#include <unistd.h>
#include <sys/types.h>
#include <stdio.h>
extern int errno;
int main()
{
    pid_t pid;
    pid = fork();
    if (pid == 0) 
       printf("I'm the child\n");
    else if (pid > 0) {
       printf("I'm the parent, ");
       printf("child pid is %d\n",pid);
   }
    else { /* pid < 0 */
       perror("Error forking");
       fprintf(stderr,"errno is %d\n",errno);
    }
   return 0;
}

This picture shows the layout of processes in memory before and after process 1234 calls fork to create a child process with process id 1235.

A call to fork is unlikely to fail under ordinary circumstances. However, all Unix systems have a limit on the total number of processes which can be run by a single user and the total number of processes which are in the process table at one time, and so if the creation of a new process would cause either of these limits to be exceeded, it will fail, returning a negative value and the child process will not be created.

The following are the same for the parent process and the child process

• The text segments (code segments)
• The values of all variables (except the value returned from fork())
• The environment
• The process priority
• The controlling terminal
• The current working directory
• Open file descriptors

Note that although the values of all variables are the same, all of the various data segments, including the run time stack are copied, so that there are two instances of each variable, allowing each process to update data independently.

The following are different for the parent process and the child process

• The process id
• The parent process id
• Data on resource allocation. For example, total run time is set to zero in the child, and process start time for the child is set to the current time

Note that every process except the init process (init has pid 0 and is the first process created at boot time. It runs until the system shuts down.) has a parent process so there is a tree of processes with init as the root.

Here is what fork does

• Reserve swap space for the child's data and stack
• allocate a new pid and kernel proc structure
• initialize the kernel proc structure. Some fields (i.e. user id, group id, signal masks) are copied from the parent, some set to zero (i.e. cpu usage), others such as ppid point to child specific values
• allocate address translation maps for the child
• add the child to the set of processes sharing the text region of the program that the parent is executing
• duplicate the parent's data and stack regions
• acquire references to shared resources inherited by the child such as open files
• initialize the hardware context by copying the parent's registers
• make the child runnable and place it on the scheduler queue
• arrange for the child to return from fork with a value of zero
• return the pid of the child to the parent

The wait system call

Whether the parent or the child will be run first is undermined; the term for this is a race condition. Thus there are two possible outputs for this program.

I'm the child
I'm the parent, child pid is 22970

I'm the parent, child pid is 22970
I'm the child

It is possible for the parent to control this by executing a wait() system call. This call causes the parent process to be blocked until a child dies. If the process has no children, a call to wait returns immediately.

Here is the function prototype

     #include <sys/types.h>
     #include <sys/wait.h>

     pid_t wait(int *stat_loc);

The return value from wait is the process id of the child that died.

Here is a short program which demonstrates this.

#include <unistd.h>
#include <sys/types.h>
#include <sys/wait.h>
#include <stdio.h>
extern int errno;
int main()
{
    pid_t pid, retval;
    int status;
    
    pid = fork();
    if (pid == 0) 
       printf("I'm the child\n");
    else if (pid > 0) {
       retval = wait(&status);
       printf("I'm the parent, ");
       printf("the child %d has died\n",retval);
   }
    else { /* pid < 0 */
       perror("Error forking");
       fprintf(stderr,"errno is %d\n",errno);
    }
   return 0;
}

If the parent happens to run first, it executes the wait system call, which causes the process to block (remember the process state diagram from the previous module). It remains blocked until the child terminates, at which time a signal is sent to the parent which awakens it and it is returned to runnable status. If the child happens to run first and terminate before the parent runs, then the call to wait returns immediately. In either case, the return value is the process id of the child.

A parent of a dying child might want to know how the child died, and the dying child might want to send a message to the parent. Both of these are accomplished using the argument which is passed to wait. Because this is a reference argument, its value is set by the system call. The least significant byte indicates how the child process died. If the child terminated normally (i.e. the process reached the end of main() or it called the exit() system call), the lowest byte of status will be zero. If the child terminated abnormally, (e.g. was terminated by a memory exception error (segmentation fault) or by the user sending a kill signal (cntl-c)), the lowest byte will be set to the numeric value of the signal that killed it.

If the child terminated normally by calling exit(), the child can pass an argument to exit() and this value will be in the second byte of status. For example, if the child called exit(5), the value of status in binary would be
00000000 00000000 00000101 00000000
It would be 00 00 05 00 in hexadecimal.

The C language has some bitwise operations which you may not know. >> is the right shift operator, << is the left shift operator, & is the bitwise and operator, and | is the bitwise or operator. You can use these to check the value of each byte of status. For example, to check whether the lowest order byte is zero, use the bitwise and operator with 0xFF (0x preceding a numeric constant in C indicates that the value is in hexadecimal).

  if (status & 0xFF != 0)  
     printf("The child died abnormally");

   int temp;
   ....
   temp = status >> 8; /* right shift */
   temp = temp & 0xFF; 
   printf("exit status was %d\n",temp);

If a process dies before all of its children have terminated, the children become orphans. Since all processes except init have a parent, orphans are adopted by the init process.

Zombies

If a child dies before its parent calls wait(), it is possible that the parent might call wait at some later time, and would want information about the status of the dead child. In this case, the process is not really terminated, but some information is retained. A process which has terminated but whose parent has not called wait() is called a zombie. Zombies occupy a slot in the process table of the operating system although they do not consume other resources. When you examine the processes on the computer with the ps command, the status of zombies is defunct. A zombie is terminated either when the parent calls wait and gets the information about that child or when the parent dies, because zombies whose parent is init will be killed.