Processes

Before we start

Why this matters

Chapter 3 · Lectures 7–8

Outline

Select a topic to jump to the slide that explains it.

1. Process concept
2. Process scheduling
3. Operations on processes
4. fork( ) and exec( ) in practice
5. Process termination
6. Interprocess communication
7. IPC in shared-memory systems
8. IPC in message-passing systems
9. Examples of IPC systems

Process concept

Process concept

• An operating system executes a variety of programs that run as a process.
• Process – a program in execution;
• Multiple parts
  • The program code, also called text section
  • Current activity including program counter, processor registers
  • Stack containing temporary data
    • Function parameters, return addresses, local variables
  • Data section containing global variables
  • Heap containing memory dynamically allocated during run time

Process concept

Process concept (cont.)

Process concept

Process concept (cont.)

• Program is passive entity stored on disk (executable file); process is active
  • Program becomes process when an executable file is loaded into memory
• Execution of program started via GUI mouse clicks, command line entry of its name, etc.
• One program can be several processes
  • Consider multiple users executing the same program

Process concept

Process state

As a process executes, it changes state:

• New: the process is being created
• Running: instructions are being executed
• Waiting: the process is waiting for some event to occur
• Ready: the process is waiting to be assigned to a processor
• Terminated: the process has finished execution

Process concept

Process state (cont.)

Interactive

Diagram of process state

Process concept

Process control block (PCB)

Information associated with each process (also called task control block):

• Process state – running, waiting, etc.
• Program counter – location of instruction to next execute
• CPU registers – contents of all process-centric registers
• CPU scheduling information – priorities, scheduling queue pointers
• Memory-management information – memory allocated to the process
• Accounting information – CPU used, clock time elapsed since start, time limits
• I/O status information – I/O devices allocated to process, list of open files

Process concept

Process control block (PCB) (cont.)

Process concept

Threads

• So far, process has a single thread of execution
• Consider having multiple program counters per process
  • Multiple locations can execute at once
    • Multiple threads of control → threads
• Must then have storage for thread details, multiple program counters in PCB
• Explore in detail in Chapter 4

Process scheduling

Process scheduling

• Process scheduler selects among available processes for next execution on CPU core
• Goal – maximize CPU use, quickly switch processes onto CPU core
• Maintains scheduling queues of processes
  • Ready queue – set of all processes residing in main memory, ready and waiting to execute
  • Wait queues – set of processes waiting for an event (i.e., I/O)
  • Processes migrate among the various queues

Process scheduling

Process scheduling (cont.)

Process scheduling

CPU switch from process to process

A context switch occurs when the CPU switches from one process to another.

Process scheduling

CPU switch from process to process (cont.)

Process scheduling

Context switch

• When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch
• Context of a process represented in the PCB
• Context-switch time is pure overhead; the system does no useful work while switching
  • The more complex the OS and the PCB → the longer the context switch
• Time dependent on hardware support
  • Some hardware provides multiple sets of registers per CPU → multiple contexts loaded at once

Animated

A context switch, animated

Operations on processes

Operations on processes

System must provide mechanisms for:

• Process creation
• Process termination

Operations on processes

Process creation

• Parent process creates children processes, which, in turn create other processes, forming a tree of processes
• Generally, process identified and managed via a process identifier (pid)
• Resource sharing options
  • Parent and children share all resources
  • Children share subset of parent’s resources
  • Parent and child share no resources
• Execution options
  • Parent and children execute concurrently
  • Parent waits until children terminate

Operations on processes

Process creation (cont.)

• Address space
  • Child duplicate of parent
  • Child has a program loaded into it
• UNIX examples
  • fork() system call creates new process
  • exec() system call used after a fork() to replace the process’ memory space with a new program
  • Parent process calls wait() waiting for the child to terminate

Operations on processes

Process creation (cont.)

Operations on processes

A tree of processes in Linux

fork( ) and exec( ) in practice

C program forking separate process

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

int main()
{
    pid_t pid;

    /* fork a child process */
    pid = fork();

    if (pid < 0) { /* error occurred */
        fprintf(stderr, "Fork Failed");
        return 1;
    }

fork( ) and exec( ) in practice

C program forking separate process (cont.)

    else if (pid == 0) { /* child process */
        execlp("/bin/ls", "ls", NULL);
    }
    else { /* parent process */
        /* parent will wait for the child to complete */
        wait(NULL);
        printf("Child Complete");
    }

    return 0;
}

• fork() returns twice: 0 in the child, the child’s pid in the parent, and a negative value if it fails.
• The child replaces itself with the ls program using execlp().
• The parent blocks in wait(NULL) until the child terminates, then prints “Child Complete”.

Code and output

fork( ) and wait( ): run it

#include <stdio.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    int x = 10;
    pid_t pid = fork();

    if (pid == 0) {                       /* child */
        x = x + 5;
        printf("child : pid %d, parent %d, x = %d\n", getpid(), getppid(), x);
        return 7;                         /* exit status for the parent */
    }

Code and output

fork( ) and wait( ): run it (cont.)

    int status;
    wait(&status);                        /* parent waits for the child */
    printf("parent: pid %d, child %d, x = %d\n", getpid(), pid, x);
    printf("parent: child exited with status %d\n", WEXITSTATUS(status));
    return 0;
}

$ gcc forkpid.c -o forkpid -pthread && ./forkpid
child : pid 5742, parent 5741, x = 15
parent: pid 5741, child 5742, x = 10
parent: child exited with status 7

The child changes its own copy of x to 15; the parent still sees 10. fork() returned the child’s pid to the parent and 0 to the child. The pid numbers differ on every run.

Class handout · interactive

fork( ) and exec( ) step by step

Interactive

How many processes?

Process termination

Process termination

• Process executes last statement and then asks the operating system to delete it using the exit() system call
  • Returns status data from child to parent (via wait())
  • Process’ resources are deallocated by operating system
• Parent may terminate the execution of children processes using the abort() system call. Some reasons for doing so:
  • Child has exceeded allocated resources
  • Task assigned to child is no longer required
  • The parent is exiting, and the operating system does not allow a child to continue if its parent terminates

Process termination

Process termination (cont.)

• Some operating systems do not allow a child to exist if its parent has terminated. If a process terminates, then all its children must also be terminated.
  • cascading termination. All children, grandchildren, etc., are terminated.
  • The termination is initiated by the operating system.
• The parent process may wait for termination of a child process by using the wait() system call. The call returns status information and the pid of the terminated process

pid = wait(&status);

• If no parent waiting (did not invoke wait()) process is a zombie
• If parent terminated without invoking wait(), process is an orphan

Process termination

Multiprocess architecture – Chrome browser

• Many web browsers ran as single process (some still do)
  • If one web site causes trouble, entire browser can hang or crash
• Google Chrome browser is multiprocess with 3 different types of processes:
  • Browser process manages user interface, disk and network I/O
  • Renderer process renders web pages, deals with HTML, Javascript. A new renderer created for each website opened
    • Runs in sandbox restricting disk and network I/O, minimizing effect of security exploits
  • Plug-in process for each type of plug-in

Process termination

Multiprocess architecture – Chrome browser (cont.)

Interprocess communication

Interprocess communication

• Processes within a system may be independent or cooperating
• Cooperating process can affect or be affected by other processes, including sharing data
• Reasons for cooperating processes:
  • Information sharing
  • Computation speedup
  • Modularity
  • Convenience
• Cooperating processes need interprocess communication (IPC)
• Two models of IPC
  • Shared memory
  • Message passing

Interprocess communication

Interprocess communication (cont.)

Animated

Shared memory, step by step

Animated

Message passing, step by step

IPC in shared-memory systems

Producer–consumer problem

IPC in message-passing systems

IPC – message passing

• Processes communicate with each other without resorting to shared variables
• IPC facility provides two operations:
  • send(message)
  • receive(message)
• The message size is either fixed or variable

IPC in message-passing systems

Message passing (cont.)

• If processes P and Q wish to communicate, they need to:
  • Establish a communication link between them
  • Exchange messages via send/receive
• Implementation issues:
  • How are links established?
  • Can a link be associated with more than two processes?
  • How many links can there be between every pair of communicating processes?
  • What is the capacity of a link?
  • Is the size of a message that the link can accommodate fixed or variable?
  • Is a link unidirectional or bi-directional?

IPC in message-passing systems

Message passing (cont.)

Implementation of communication link

IPC in message-passing systems

Direct and indirect communication

IPC in message-passing systems

Indirect communication (cont.)

IPC in message-passing systems

Synchronization and buffering

• Message passing may be either blocking or non-blocking
• Blocking is considered synchronous
  • Blocking send – the sender is blocked until the message is received
  • Blocking receive – the receiver is blocked until a message is available
• Non-blocking is considered asynchronous
  • Non-blocking send – the sender sends the message and continues
  • Non-blocking receive – the receiver receives:
    • A valid message, or
    • Null message

IPC in message-passing systems

Synchronization and buffering (cont.)

• Different combinations possible
  • If both send and receive are blocking, we have a rendezvous

Buffering: a queue of messages attached to the link, implemented in one of three ways:

1. Zero capacity – no messages are queued on a link. Sender must wait for receiver (rendezvous)
2. Bounded capacity – finite length of n messages. Sender must wait if link full
3. Unbounded capacity – infinite length. Sender never waits

Interactive

Try blocking and buffering

Examples of IPC systems

Examples of IPC systems – POSIX

shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
ftruncate(shm_fd, 4096);
ptr = mmap(0, 4096, PROT_READ | PROT_WRITE,
           MAP_SHARED, shm_fd, 0);
sprintf(ptr, "%s", "Hello");

Code and output

POSIX shared memory: run it

#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/wait.h>
#include <unistd.h>

int main(void)
{
    const char *name = "/OS";
    const int SIZE = 4096;

    /* create the shared-memory object and set its size */
    int shm_fd = shm_open(name, O_CREAT | O_RDWR, 0666);
    ftruncate(shm_fd, SIZE);
    /* map it: the pointer is valid in this process and in its child */
    char *ptr = mmap(0, SIZE, PROT_READ | PROT_WRITE, MAP_SHARED, shm_fd, 0);

Code and output

POSIX shared memory: run it (cont.)

    if (fork() == 0) {                       /* producer */
        sprintf(ptr, "%s", "Studying Operating Systems Is Fun!");
        return 0;
    }
    wait(NULL);                              /* consumer, after the producer */
    printf("consumer read: %s\n", ptr);      /* no copy, no system call */
    shm_unlink(name);
    return 0;
}

$ gcc shm.c -o shm -pthread && ./shm
consumer read: Studying Operating Systems Is Fun!

The producer (child) writes with sprintf into the mapped region; the consumer (parent) reads the same bytes. Only shm_open, ftruncate and mmap are system calls.

Extra · code and output

Ordinary pipes

#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>

Extra · code and output

Ordinary pipes (cont.)

int main(void)
{
    int fd[2];                 /* fd[0]: read end, fd[1]: write end */
    char buf[32];
    pipe(fd);

    if (fork() == 0) {         /* child: the receiver */
        close(fd[1]);
        ssize_t n = read(fd[0], buf, sizeof buf - 1);
        buf[n] = '\0';
        printf("child read %zd bytes: %s\n", n, buf);
        return 0;
    }

Extra · code and output

Ordinary pipes (cont.)

    close(fd[0]);              /* parent: the sender */
    const char *msg = "Greetings";
    write(fd[1], msg, strlen(msg));
    printf("parent wrote: %s\n", msg);
    close(fd[1]);
    wait(NULL);
    return 0;
}

$ gcc pipe.c -o pipe -pthread && ./pipe
parent wrote: Greetings
child read 9 bytes: Greetings

Examples of IPC systems

Examples of IPC systems – Mach

• Mach communication is message based
  • Even system calls are messages
  • Each task gets two ports at creation – Kernel and Notify
  • Messages are sent and received using the mach_msg() function
  • Ports needed for communication, created via mach_port_allocate()
  • Send and receive are flexible; for example four options if mailbox full:
    • Wait indefinitely
    • Wait at most n milliseconds
    • Return immediately
    • Temporarily cache a message

Examples of IPC systems

Examples of IPC systems – Windows

• Message-passing centric via advanced local procedure call (LPC) facility
  • Only works between processes on the same system
  • Uses ports (like mailboxes) to establish and maintain communication channels
  • Communication works as follows:
    • The client opens a handle to the subsystem’s connection port object.
    • The client sends a connection request.
    • The server creates two private communication ports and returns the handle to one of them to the client.
    • The client and server use the corresponding port handle to send messages or callbacks and to listen for replies.

Examples of IPC systems

Examples of IPC systems – Windows (cont.)

Worked example 1 of 3

Worked example 1

int main() {
    fork();
    fork();
    printf("hello\n");
    return 0;
}

Worked example 2 of 3

Worked example 2

Worked example 3 of 3

Worked example 3

Practice

Practice (1 of 2)

Try each one on paper first, then check your answer.

Practice

Practice (2 of 2)

Try each one on paper first, then check your answer.

Check yourself

Quiz

Resources

Further learning

Free material to go deeper. Links open in a new tab.

Summary · End of Chapter 3

Summary

• A process is a program in execution: text, data, heap, stack, program counter and registers.
• It moves between new, ready, running, waiting and terminated; the OS keeps its information in a PCB.
• The scheduler picks from the ready queue; a context switch saves and restores PCBs and is pure overhead.
• fork() creates a child copy, exec() replaces its program, wait() lets the parent collect it; zombies and orphans result when wait() is missing.
• Cooperating processes use IPC: shared memory (e.g. the producer–consumer buffer) or message passing with send/receive.
• Message passing can be direct or indirect (mailboxes), blocking or non-blocking, with zero, bounded or unbounded buffering.