Processes

Tom Kelliher, CS42

Sept. 16, 1996

The Process

1. Program in execution.
2. Serial, ordered execution within a single process. (Contrast task with multiple threads.)
3. ``Parallel'' unordered execution between processes.

Three issues to address

1. Specification and implementation of processes --- the issue of concurrency (raises the issue of the primitive operations).

2. Resolution of competition for resources: CPU, memory, I/O devices, etc.

3. Provision for communication between processes.

Example: Producer/Consumer

How can the communication be optimized?

Process States

Three possible states for a process:

• Running --- currently being executed by the processor

• Ready --- waiting to get the processor

• Blocked (waiting) --- waiting for an event to occur: I/O completion, signal, etc. (Suspended --- ready to run but not eligible.)

How many in each state?

A Process' Resources

Kept in a process control block (PCB) for each process:

1. Code (possibly shared among processes).
2. Execution stack --- stack frames.
3. CPU state --- general purpose registers, PC, status register, etc.
4. Heap --- dynamically allocated storage.
5. State --- running, ready, blocked, zombie, etc.
6. Scheduling information --- priority, total CPU time, wall time, last burst, etc.
7. Memory management --- page, segment tables.
8. I/O status --- devices allocated, open files, pending I/O requests, postponed resource requests (deadlock avoidance).
9. Accounting --- owner, CPU time, disk usage, parent, child processes, etc.

PCB updated during context switches (kernel in control).

Should a process be able to manipulate its PCB?

Process Scheduling

Determination of which process to run next (CPU scheduling).

Multiple queues for holding processes:

1. Ready queue --- priority order.
2. I/O queues --- request order.

   Consider a disk write:

   1. Syscall.
   2. Schedule the write.
   3. Modify PCB state, move to I/O queue.
   4. Call short term scheduler to perform context switch.
   Is it necessary to wait on a disk write?

3. Event queues --- waiting on child completion, sleeping on timer, waiting for request ( inetd).

Three types of schedulers:

• Long term scheduler.
• Medium term scheduler.
• Short term (CPU) scheduler.

Long Term Scheduler

Determines overall job mix:

1. Balance of I/O, CPU bound jobs.
2. Attempts to maximize CPU utilization, throughput, or some other measure.
3. Runs infrequently.

Medium Term Scheduler

Cleans up after poor long term scheduler decisions:

1. Over-committed memory --- thrashing.
2. Determines candidate processes for suspending and paging out.
3. Decreases degree of multiprogramming.
4. Runs only when needed.

CPU Scheduler

Decides which process to run next:

1. Picks among processes in ready queue.
2. Priority function.
3. Runs frequently --- must be efficient.

Context Switching

Time line schematic:

Example: Context Switch Routines for Xinu

The following is from the Xinu system, designed by Douglas Comer.

/* declarations */

#define QUANTUM         10             /* clock ticks until preemption */
#define SP              6              /* reg. 6 is stack pointer */
#define PC              7              /* reg. 7 is program counter */
#define PS              8              /* proc. status stored in 8th loc. */

#define NPROC           10             /* max number of processes */

#define PRCURR          '\bksl01'      /* process is running */
#define PRFREE          '\bksl02'      /* table entry is free */
#define PRREADY         '\bksl03'      /* process is on ready queue */
#define PRRECV          '\bksl04'      /* process is waiting for message */
#define PRSLEEP         '\bksl05'      /* process is sleeping */
#define PRSUSP          '\bksl06'      /* process is suspended */
#define PRWAIT          '\bksl07'      /* process is on semaphore queue */

#define PNREGS          9              /* number of CPU registers */
#define PNMLEN          8              /* process name length */


/* process table entry */

struct   pentry \{
         char  pstate;                 /* state of process */
         short pprio;                  /* process priority */
         short pregs[PNREGS];          /* saved registers: R0-R5, SP, PC, PS */
         short psem;                   /* semaphore process waiting on */
         short pmsg;                   /* message sent to process */
         short phasmsg;                /* nonzero iff pmsg is valid */
         short pbase;                  /* base of runtime stack */
         short pstklen;                /* stack length */
         short plimit;                 /* lowest extent of stack */
         char name[PNMLEN];            /* process name */
         short pargs;                  /* number of arguments */
         short paddr;                  /* initial code address */
\};


extern struct pentry    proctab[NPROC];
extern int              currpid;       /* currently executing process */
extern int              rdyhead, rdytail;
extern int              preempt;


/*-----------------------------------------------------------------------------
 *  resched -- reschedule processor to highest priority ready process
 *
 *  Notes:     Upon entry, currpid gives current process id.
 *             Proctab[currpid].pstate gives correct NEXT state for current
 *             process if other than PRCURR.
 *-----------------------------------------------------------------------------
 */
int resched() \{
   register struct pentry        *optr;   /* pointer to old process entry */
   register struct pentry        *nptr;   /* pointer to new process entry */

   /* no switch needed if current process priority HIGHER than next */

   if ( ( (optr = &proctab[currpid])->pstate == PRCURR) &&
        (lastkey(rdytail) < optr->pprio) )
      return(OK);

   /* force context switch */

   if (optr->pstate == PRCURR) \{
      optr->pstate = PREADY;
      insert(currpid, rdyhead, optr->pprio);
   \}

   /* remove highest priority process at end of ready list */

   nptr = &proctab[ (currpid = getlast(rdytail) ) ];
   nptr->pstate = PRCURR;
   preempt = QUANTUM;                     /* reset preemption counter */
   ctxsw(optr->pregs, nptr->pregs);       /* do context switch */

   /* the OLD process returns here when resumed */

   return(OK);
\}


/*-----------------------------------------------------------------------------
 *  ctxsw -- assembler routine for performing context switch,
 *  saving/loading registers
 *
 *  The stack contains three items upon entry to this routine:
 *
 *  SP+4 => address of 9 word save area with new registers + PS
 *  SP+2 => address of 9 word save area for old registers + PS
 *  SP   => return address
 *
 *  The saved state consists of: the values of R0-R5 upon entry, SP+2, PC
 *  equal to the return address, and the PS (i.e., the PC and SP are saved
 *  as if the calling process had returned to its caller.
 *-----------------------------------------------------------------------------
 */
         .globl _ctxsw        /* declare name global */
_ctxsw:                       /* entry point to proc. */
         mov   r0,*2(sp)      /* save old R0 in old register area */
         mov   2(sp),r0       /* get address of old register area in R0 */
         add   $2,r0          /* increment to saved pos. of R1 */
         mov   r1,(r0)+       /* save R1-R5 in successive locations of old
         mov   r2,(r0)+       /*  process register save are */
         mov   r3,(r0)+
         mov   r4,(r0)+
         mov   r5,(r0)+
         add   $2,sp          /* move SP beyond the return address, as if a */
                              /*  return had occurred */
         mov   sp,(r0)+       /* save stack pointer */
         mov   -(sp),(r0)+    /* save caller's return address as PC */
         mfps  (r0)           /* save processor status beyond registers */
         mov   4(sp),r0       /* get address of start of new register area */
                              /* ready to load registers for the new process */
                              /*  and abandon the old stack */
         mov   2(r0),r1       /* load R1-R5 and SP from the new area */
         mov   4(r0),r2
         mov   6(r0),r3
         mov   8.(r0),r4      /* dot following a number makes it decimal; */
         mov   10.(r0),r5     /*  otherwise it is octal */
         mov   12.(r0),sp     /* have switched stacks now */
         mov   16.(r0),-(sp)  /* push new process PS on new process stack */
         mov   14.(r0),-(sp)  /* push new process PC on new process stack */
         mov   (r0),r0        /* load R0 from new area */
         rtt                  /* load PC, PS, and reset SP all at once */

Operations on Processes

Process Creation

Parent, child.

Where does the child's resources come from? By ``resources'' we mean:

1. Stack.
2. Heap.
3. Code.
4. Environment --- environment variables, open files, devices, etc.

Design questions:

• New text, same text?
• Make a copy of the memory areas? (Expensive.)
• Copy the environment?
• How are open files handled?

Solutions to the ``copy the parent's address space'' problem:

1. Copy on write --- Mark all parent's pages read only and shared by parent & child. On any attempted write to such a page, make a copy and assign it to child. Fix page tables.
2. vfork --- No copying at all. It is assumed that child will perform an exec, which provides a private address space.

Unix Example

For additional information see (on reserve in Mack):

W. R. Stevens, Advanced Programming in the Unix Environment, Addison Wesley, 1992. Chapter 8.

The fork() call:

1. Creates a new process.
2. Child is Copy of parent.
3. Same environment.
4. Returns twice:
   1. Parent's return value --- pid of child, -1 (error).
   2. Child's return value --- 0 (otherwise illegal)

Sample code:

if ((pid = fork() < 0)
   Error();
else if (pid == 0)
   Child();
else
   Parent();

Example uses:

• Shell starting programs for user.
• Concurrent server in client/server computing. I.e., telnetd.

Process Termination

exit()

Parent Synchronization

Parent may progress in parallel, or wait until child exits.

Example of parent waiting for child:

if ((pid = fork()) < 0)
   Error();
else if (pid == 0)
   Child();
else
   wait();   /* parent waiting on child */