Operating System

Processes

3.1 Process Concept

• A process is an instance of a program in execution.
• Batch systems work in terms of "jobs". Many modern process concepts are still expressed in terms of jobs, ( e.g. job scheduling ), and the two terms are often used interchangeably.

3.1.1 The Process

• Process memory is divided into four sections as shown in Figure 3.1 below:
  • The text section comprises the compiled program code, read in from non-volatile storage when the program is launched.
  • The data section stores global and static variables, allocated and initialized prior to executing main.
  • The heap is used for dynamic memory allocation, and is managed via calls to new, delete, malloc, free, etc.
  • The stack is used for local variables. Space on the stack is reserved for local variables when they are declared ( at function entrance or elsewhere, depending on the language ), and the space is freed up when the variables go out of scope. Note that the stack is also used for function return values, and the exact mechanisms of stack management may be language specific.
  • Note that the stack and the heap start at opposite ends of the process's free space and grow towards each other. If they should ever meet, then either a stack overflow error will occur, or else a call to new or malloc will fail due to insufficient memory available.
• When processes are swapped out of memory and later restored, additional information must also be stored and restored. Key among them are the program counter and the value of all program registers.

Figure 3.1 - A process in memory

3.1.2 Process State

• Processes may be in one of 5 states, as shown in Figure 3.2 below.
  • New - The process is in the stage of being created.
  • Ready - The process has all the resources available that it needs to run, but the CPU is not currently working on this process's instructions.
  • Running - The CPU is working on this process's instructions.
  • Waiting - The process cannot run at the moment, because it is waiting for some resource to become available or for some event to occur. For example the process may be waiting for keyboard input, disk access request, inter-process messages, a timer to go off, or a child process to finish.
  • Terminated - The process has completed.
• The load average reported by the "w" command indicate the average number of processes in the "Ready" state over the last 1, 5, and 15 minutes, i.e. processes who have everything they need to run but cannot because the CPU is busy doing something else.
• Some systems may have other states besides the ones listed here.

Figure 3.2 - Diagram of process state

3.1.3 Process Control Block

For each process there is a Process Control Block, PCB, which stores the following ( types of ) process-specific information, as illustrated in Figure 3.1. ( Specific details may vary from system to system. )

• Process State - Running, waiting, etc., as discussed above.
• Process ID, and parent process ID.
• CPU registers and Program Counter - These need to be saved and restored when swapping processes in and out of the CPU.
• CPU-Scheduling information - Such as priority information and pointers to scheduling queues.
• Memory-Management information - E.g. page tables or segment tables.
• Accounting information - user and kernel CPU time consumed, account numbers, limits, etc.
• I/O Status information - Devices allocated, open file tables, etc.

Figure 3.3 - Process control block ( PCB )

Figure 3.4 - Diagram showing CPU switch from process to process

3.1.4 Threads

• Modern systems allow a single process to have multiple threads of execution, which execute concurrently. Threads are covered extensively in the next chapter.

3.2 Process Scheduling

• The two main objectives of the process scheduling system are to keep the CPU busy at all times and to deliver "acceptable" response times for all programs, particularly for interactive ones.
• The process scheduler must meet these objectives by implementing suitable policies for swapping processes in and out of the CPU.
• ( Note that these objectives can be conflicting. In particular, every time the system steps in to swap processes it takes up time on the CPU to do so, which is thereby "lost" from doing any useful productive work. )

3.2.1 Scheduling Queues

• All processes are stored in the job queue.
• Processes in the Ready state are placed in the ready queue.
• Processes waiting for a device to become available or to deliver data are placed in device queues. There is generally a separate device queue for each device.
• Other queues may also be created and used as needed.

Figure 3.5 - The ready queue and various I/O device queues

3.2.2 Schedulers

• A long-term scheduler is typical of a batch system or a very heavily loaded system. It runs infrequently, ( such as when one process ends selecting one more to be loaded in from disk in its place ), and can afford to take the time to implement intelligent and advanced scheduling algorithms.
• The short-term scheduler, or CPU Scheduler, runs very frequently, on the order of 100 milliseconds, and must very quickly swap one process out of the CPU and swap in another one.
• Some systems also employ a medium-term scheduler. When system loads get high, this scheduler will swap one or more processes out of the ready queue system for a few seconds, in order to allow smaller faster jobs to finish up quickly and clear the system. See the differences in Figures 3.7 and 3.8 below.
• An efficient scheduling system will select a good process mix of CPU-bound processes and I/O bound processes.

Figure 3.6 - Queueing-diagram representation of process scheduling

Figure 3.7 - Addition of a medium-term scheduling to the queueing diagram

3.2.3 Context Switch

• Whenever an interrupt arrives, the CPU must do a state-save of the currently running process, then switch into kernel mode to handle the interrupt, and then do a state-restore of the interrupted process.
• Similarly, a context switch occurs when the time slice for one process has expired and a new process is to be loaded from the ready queue. This will be instigated by a timer interrupt, which will then cause the current process's state to be saved and the new process's state to be restored.
• Saving and restoring states involves saving and restoring all of the registers and program counter(s), as well as the process control blocks described above.
• Context switching happens VERY VERY frequently, and the overhead of doing the switching is just lost CPU time, so context switches ( state saves & restores ) need to be as fast as possible. Some hardware has special provisions for speeding this up, such as a single machine instruction for saving or restoring all registers at once.
• Some Sun hardware actually has multiple sets of registers, so the context switching can be speeded up by merely switching which set of registers are currently in use. Obviously there is a limit as to how many processes can be switched between in this manner, making it attractive to implement the medium-term scheduler to swap some processes out as shown in Figure 3.8 above.

3.3 Operations on Processes

3.3.1 Process Creation

• Processes may create other processes through appropriate system calls, such as fork or spawn. The process which does the creating is termed the parent of the other process, which is termed its child.
• Each process is given an integer identifier, termed its process identifier, or PID. The parent PID ( PPID ) is also stored for each process.
• On typical UNIX systems the process scheduler is termed sched, and is given PID 0. The first thing it does at system startup time is to launch init, which gives that process PID 1. Init then launches all system daemons and user logins, and becomes the ultimate parent of all other processes. Figure 3.9 shows a typical process tree for a Linux system, and other systems will have similar though not identical trees:

Figure 3.8 - A tree of processes on a typical Linux system

• Depending on system implementation, a child process may receive some amount of shared resources with its parent. Child processes may or may not be limited to a subset of the resources originally allocated to the parent, preventing runaway children from consuming all of a certain system resource.
• There are two options for the parent process after creating the child:
  1. Wait for the child process to terminate before proceeding. The parent makes a wait( ) system call, for either a specific child or for any child, which causes the parent process to block until the wait( ) returns. UNIX shells normally wait for their children to complete before issuing a new prompt.
  2. Run concurrently with the child, continuing to process without waiting. This is the operation seen when a UNIX shell runs a process as a background task. It is also possible for the parent to run for a while, and then wait for the child later, which might occur in a sort of a parallel processing operation. ( E.g. the parent may fork off a number of children without waiting for any of them, then do a little work of its own, and then wait for the children. )
• Two possibilities for the address space of the child relative to the parent:
  1. The child may be an exact duplicate of the parent, sharing the same program and data segments in memory. Each will have their own PCB, including program counter, registers, and PID. This is the behavior of the fork system call in UNIX.
  2. The child process may have a new program loaded into its address space, with all new code and data segments. This is the behavior of the spawn system calls in Windows. UNIX systems implement this as a second step, using the exec system call.
• Figures 3.10 and 3.11 below shows the fork and exec process on a UNIX system. Note that the fork system call returns the PID of the processes child to each process - It returns a zero to the child process and a non-zero child PID to the parent, so the return value indicates which process is which. Process IDs can be looked up any time for the current process or its direct parent using the getpid( ) and getppid( ) system calls respectively.


Figure 3.9 Creating a separate process using the UNIX fork( ) system call.


Figure 3.10 - Process creation using the fork( ) system call

• Related man pages:
  • fork(2)
  • exec(3)
  • wait(2)

Figure 3.11

3.3.2 Process Termination

• Processes may request their own termination by making the exit( ) system call, typically returning an int. This int is passed along to the parent if it is doing a wait( ), and is typically zero on successful completion and some non-zero code in the event of problems.
  • child code:

                int exitCode;
                exit( exitCode );  // return exitCode; has the same effect when executed from main( )

  • parent code:

                pid_t pid;
                int status
                pid = wait( &status ); 
                // pid indicates which child exited. exitCode in low-order bits of status
                // macros can test the high-order bits of status for why it stopped

• Processes may also be terminated by the system for a variety of reasons, including:
  • The inability of the system to deliver necessary system resources.
  • In response to a KILL command, or other un handled process interrupt.
  • A parent may kill its children if the task assigned to them is no longer needed.
  • If the parent exits, the system may or may not allow the child to continue without a parent. ( On UNIX systems, orphaned processes are generally inherited by init, which then proceeds to kill them. The UNIX nohup command allows a child to continue executing after its parent has exited. )
• When a process terminates, all of its system resources are freed up, open files flushed and closed, etc. The process termination status and execution times are returned to the parent if the parent is waiting for the child to terminate, or eventually returned to init if the process becomes an orphan. ( Processes which are trying to terminate but which cannot because their parent is not waiting for them are termed zombies. These are eventually inherited by init as orphans and killed off. Note that modern UNIX shells do not produce as many orphans and zombies as older systems used to. )

3.4 Interprocess Communication

• Independent Processes operating concurrently on a systems are those that can neither affect other processes or be affected by other processes.
• Cooperating Processes are those that can affect or be affected by other processes. There are several reasons why cooperating processes are allowed:
  • Information Sharing - There may be several processes which need access to the same file for example. ( e.g. pipelines. )
  • Computation speedup - Often a solution to a problem can be solved faster if the problem can be broken down into sub-tasks to be solved simultaneously ( particularly when multiple processors are involved. )
  • Modularity - The most efficient architecture may be to break a system down into cooperating modules. ( E.g. databases with a client-server architecture. )
  • Convenience - Even a single user may be multi-tasking, such as editing, compiling, printing, and running the same code in different windows.
• Cooperating processes require some type of inter-process communication, which is most commonly one of two types: Shared Memory systems or Message Passing systems. Figure 3.12 illustrates the difference between the two systems:

Figure 3.12 - Communications models: (a) Message passing. (b) Shared memory.

• Shared Memory is faster once it is set up, because no system calls are required and access occurs at normal memory speeds. However it is more complicated to set up, and doesn't work as well across multiple computers. Shared memory is generally preferable when large amounts of information must be shared quickly on the same computer.
• Message Passing requires system calls for every message transfer, and is therefore slower, but it is simpler to set up and works well across multiple computers. Message passing is generally preferable when the amount and/or frequency of data transfers is small, or when multiple computers are involved.

3.4.1 Shared-Memory Systems

• In general the memory to be shared in a shared-memory system is initially within the address space of a particular process, which needs to make system calls in order to make that memory publicly available to one or more other processes.
• Other processes which wish to use the shared memory must then make their own system calls to attach the shared memory area onto their address space.
• Generally a few messages must be passed back and forth between the cooperating processes first in order to set up and coordinate the shared memory access.

Producer-Consumer Example Using Shared Memory

• This is a classic example, in which one process is producing data and another process is consuming the data. ( In this example in the order in which it is produced, although that could vary. )
• The data is passed via an intermediary buffer, which may be either unbounded or bounded. With a bounded buffer the producer may have to wait until there is space available in the buffer, but with an unbounded buffer the producer will never need to wait. The consumer may need to wait in either case until there is data available.
• This example uses shared memory and a circular queue. Note in the code below that only the producer changes "in", and only the consumer changes "out", and that they can never be accessing the same array location at the same time.
• First the following data is set up in the shared memory area:

  #define BUFFER_SIZE 10

  typedef struct {
       . . .
  } item;

  item buffer[ BUFFER_SIZE ];
  int in = 0;
  int out = 0;

• Then the producer process. Note that the buffer is full when "in" is one less than "out" in a circular sense:

  // Code from Figure 3.13

  item nextProduced;

  while( true ) {

/* Produce an item and store it in nextProduced */
nextProduced = makeNewItem( . . . );

/* Wait for space to become available */
while( ( ( in + 1 ) % BUFFER_SIZE ) == out )
      ; /* Do nothing */

/* And then store the item and repeat the loop. */
buffer[ in ] = nextProduced;
in = ( in + 1 ) % BUFFER_SIZE;

}

• Then the consumer process. Note that the buffer is empty when "in" is equal to "out":

// Code from Figure 3.14

item nextConsumed;

while( true ) {

/* Wait for an item to become available */
while( in == out )
      ; /* Do nothing */

/* Get the next available item */
nextConsumed = buffer[ out ];
out = ( out + 1 ) % BUFFER_SIZE;

/* Consume the item in nextConsumed
     ( Do something with it ) */

}

3.4.2 Message-Passing Systems

• Message passing systems must support at a minimum system calls for "send message" and "receive message".
• A communication link must be established between the cooperating processes before messages can be sent.
• There are three key issues to be resolved in message passing systems as further explored in the next three subsections:
  • Direct or indirect communication ( naming )
  • Synchronous or asynchronous communication
  • Automatic or explicit buffering.

3.4.2.1 Naming

• With direct communication the sender must know the name of the receiver to which it wishes to send a message.
  • There is a one-to-one link between every sender-receiver pair.
  • For symmetric communication, the receiver must also know the specific name of the sender from which it wishes to receive messages.
    For asymmetric communications, this is not necessary.
• Indirect communication uses shared mailboxes, or ports.
  • Multiple processes can share the same mailbox or boxes.
  • Only one process can read any given message in a mailbox. Initially the process that creates the mailbox is the owner, and is the only one allowed to read mail in the mailbox, although this privilege may be transferred.
    • ( Of course the process that reads the message can immediately turn around and place an identical message back in the box for someone else to read, but that may put it at the back end of a queue of messages. )
  • The OS must provide system calls to create and delete mailboxes, and to send and receive messages to/from mailboxes.

3.4.2.2 Synchronization

• Either the sending or receiving of messages ( or neither or both ) may be either blocking or non-blocking.
• Blocking send. The sending process is blocked until the message is received by the receiving process or by the mailbox.
• Nonblocking send. The sending process sends the message and resumes operation.
• Blocking receive. The receiver blocks until a message is available.
• Nonblocking receive. The receiver retrieves either a valid message or a null.

3.4.2.3 Buffering

• Messages are passed via queues, which may have one of three capacity configurations:
  1. Zero capacity - Messages cannot be stored in the queue, so senders must block until receivers accept the messages.
  2. Bounded capacity- There is a certain pre-determined finite capacity in the queue. Senders must block if the queue is full, until space becomes available in the queue, but may be either blocking or non-blocking otherwise.
  3. Unbounded capacity - The queue has a theoretical infinite capacity, so senders are never forced to block.

3.5 Examples of IPC Systems

3.5.1 An Example: POSIX Shared Memory

1. The ninth edition shows an alternate approach to shared memory in POSIX systems. Under this approach, the first step in using shared memory is to create a shared-memory object using shm_open( ),in a fashion similar to other file opening commands. The name provided will be the name of the memory-mapped file.

   shm_fd = shm_open( name,O_CREAT | O_RDRW,0666 );

2. The next step is to set the size of the file using ftruncate:

   ftruncate( shm_fd, 4096 );

3. Finally the mmap system call maps the file to a memory address in the user program space.and makes it shared. In this example the process that created the shared memory will be writing to it:

   ptr = mmap( 0, SIZE,PROT_WRITE, MAP_SHARED, shm_fd, 0 );

4. The "borrower" of the shared memory, ( not the one who created it ), calls shm_open( ) and mmap( ) with different arguments, skips the ftruncate( ) step and unlinks ( removes ) the file name when it is done with it. Note that the "borrower" must use the same file name as the "lender" who created it. ( This information could have been passed using messages. )

   shm_unlink( name );

5. Note that writing to and reading from the shared memory is done with pointers and memory addresses ( sprintf ) in both the 9th and 8th edition versions, even though the 9th edition is illustrating memory mapping of a file.
6. Figures 3.17 and 3.18 from the ninth edition illustrate a complete program implementing shared memory on a POSIX system: