Processes - p. 1/66

Processes - p. 3/66

Linux Process States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 20 Linux Process States — 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 21

(see http://www.opencontent.org/openpub/)

Linux Process States — 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 22 Process States:

A process includes current values of: Program counter Registers Variables A process also has: The program code It’s own address space, independent of other processes A user that owns it A group owner An environment and a command line This information is stored in a process control block, or task descriptor or process descriptor a data structure in the OS, in the process table See slides starting at §34.

vmstat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 23

Tools for monitoring processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 24 Monitoring processes in Win 2000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 25 top Process Monitoring — top . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 27 load average. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 28

top: process states . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 29
top and memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 30 Virtual Memory: suspended processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 31 Suspended Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 32 Process Control Blocks OS Process Control Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 34 What is in a PCB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 35 Context Switch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 36 Execution Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 37 Program Counter in PCB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 38 PCB Example. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 39 PCB Example Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 40 PCB Example — Continued. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 41 Address of I/O instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 42 System Calls System Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 44

The code of a process occupies memory The Program counter (PC) is a CPU register PC holds a memory address. . . . . . of the next instruction to be fetched and executed

What are processes? How does the operating system manage them?

What is a process? — 2

Processes and Threads

Department of Information and Communications Technology

Copyright Conditions: Open Publication License

OSSI — ver. 1.5

OSSI — ver. 1.5

Program counter

Nick Urbanik

nicku@vtc.edu.hk

0-1

Processes - p. 2/66

What is a process? — 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 3 What is a thread? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 4 Program counter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 5 Environment of a process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 6 Permissions of a Process. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 7 Multitasking Multitasking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 8 Multitasking — 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 9 Multitasking — 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 10 Start of Process Birth of a Process. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 11 Process tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 12 Scheduler Scheduler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 13 When to Switch Processes? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 14 Scheduling statistics:

IPC — Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 49

Threads

What is a process?

Threads and Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 52 Threads have own. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 53 Threads share a lot . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 54 Problem with threads: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 55 Race Condition Race Conditions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 57 Critical Sections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 58 Race Condition — one possibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 59 Example — another possibility. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 60 Solution: Synchronisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 61 File Locking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 62 Summary and References Summary — Process States, Scheduling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 64 Summary — Processes and Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 65 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 66

A process is a program in execution Each process has a process ID In Linux, $ ps ax prints one line for each process. A program can be executed a number of times simultaneously. Each is a separate process.

Signals and the Shell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 50

vmstat. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 15

Interrupts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 16 Process States Process States . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 17 What is Most Common State? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 18 Most Processes are Blocked . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 19

order to avoid deadlock problems. Similarly, the use of threads in a

What is a process?. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 2

IPC — Shared Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 48

“Threads often prevent abstraction. In order to prevent deadlock. you

Introduction

Interprocess Communication (IPC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 47

often need to know how and if the library you are using uses threads in

library could be affected by the use of threads at the application layer.” –

Problem with Processes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Slide 46

A thread is a lightweight process Takes less CPU power to start, stop Part of a single process Shares address space with other threads in the same process Threads can share data more easily than processes Sharing data requires synchronisation, i.e., locking — see slide 61. This shared memory space can lead to complications in programming:

Contents

IPC

OSSI — ver. 1.5

What is a thread?

0-2

OSSI — ver. David Korn1.5

Processes - p. 4/66 See page 180, ESR in references, §66.

OSSI — ver. 1.5

Processes - p. 5/66

Environment of a process
The environment is a set of names and values Examples: PATH=/usr/bin:/bin:/usr/X11R6/bin HOME=/home/nicku SHELL=/bin/bash In Linux shell, can see environment by typing: $ set

Permissions of a Process
A process executes with the permissions of its owner The owner is the user that starts the process A Linux process can execute with permissions of another user or group If it executes as the owner of the program instead of the owner of the process, it is called set user ID Similarly for set group ID programs

OSSI — ver. 1.5

Processes - p. 6/66

OSSI — ver. 1.5

Processes - p. 7/66

Multitasking
Our lab PCs have one main CPU But multiprocessor machines are becoming increasingly common Linux 2.6.x kernel scales to 16 CPUs How execute many processes “at the same time”?

Multitasking — 2
CPU rapidly switches between processes that are “ready to run” Really: only one process runs at a time Change of process called a context switch See slide §36 With Linux: see how many context switches/second using vmstat under “system” in column “cs”

OSSI — ver. 1.5

Processes - p. 8/66

OSSI — ver. 1.5

Processes - p. 9/66

Multitasking — 3
This diagram shows how the scheduler gives a “turn” on the CPU to each of four processes that are ready to run

Birth of a Process
In Linux, a process is born from a fork() system call A system call is a function call to an operating system service provided by the kernel Each process has a parent The parent process calls fork() The child inherits (but cannot change) the parent environment, open files Child is identical to parent, except for return value of fork(). Parent gets child’s process ID (PID) Child gets 0

process D C B A

CPU executes process

time
OSSI — ver. 1.5 Processes - p. 10/66 OSSI — ver. 1.5 Processes - p. 11/66

context switches

Process tree

Scheduler
OS decides when to run each process that is ready to run (“runable”) The part of OS that decides this is the scheduler Scheduler aims to: Maximise CPU usage Maximise process completion Minimise process execution time Minimise waiting time for ready processes Minimise response time

Processes may have parents and children Gives a family tree In Linux, see this with commands: $ pstree or $ ps axf

OSSI — ver. 1.5

Processes - p. 12/66

OSSI — ver. 1.5

Processes - p. 13/66

When to Switch Processes?
The scheduler may change a process between executing (or running) and ready to run when any of these events happen: clock interrupt I/O interrupt Memory fault trap caused by error or exception system call See slide §17 showing the running and ready to run process states.

Scheduling statistics: vmstat
The “system” columns give statistics about scheduling: “cs” — number of context switches per second “in” — number of interrupts per second See slide §36, man vmstat

OSSI — ver. 1.5

Processes - p. 14/66

OSSI — ver. 1.5

Processes - p. 15/66

Interrupts
Will discuss interrupts in more detail when we cover I/O An interrupt is an event (usually) caused by hardware that causes: Saving some CPU registers Execution of interrupt handler Restoration of CPU registers An opportunity for scheduling

Process States
waiting for input Running scheduler chooses this process Blocked input available scheduler chooses another process Ready

OSSI — ver. 1.5

Processes - p. 16/66

OSSI — ver. 1.5

Processes - p. 17/66

What is Most Common State?
Now, my computer has 160 processes. How many are running, how many are ready to run, how many are blocked? What do you expect is most common state?

Most Processes are Blocked
9:41am up 44 days, 20:12, 1 user, load average: 2.02, 2.06, 2.13 160 processes: 145 sleeping, 2 running, 13 zombie, 0 stopped

Here you see that most are sleeping, waiting for input! Most processes are “I/O bound”; they spend most time waiting for input or waiting for output to complete With one CPU, only one process can actually be running at one time However, surprisingly few processes are ready to run The load average is the average number of processes that are in the ready to run state. In output from the top program above, see over last 60 seconds, there are 2.02 processes on average in RTR state
OSSI — ver. 1.5 Processes - p. 19/66

OSSI — ver. 1.5

Processes - p. 18/66

Linux Process States
stopped

Linux Process States — 2
Running — actually contains two states: executing, or ready to execute Interruptable — a blocked state waiting for event, such as: end of an I/O operation, availability of a resource, or a signal from another process Uninterruptable — another blocked state waiting directly on hardware conditions will not accept any signals (even SIGKILL)

running state

creation

ready to run

scheduling wait for event event

executing

zombie

signal or event
OSSI — ver. 1.5

uninterruptible

Processes - p. 20/66

OSSI — ver. 1.5

Processes - p. 21/66

interruptible

Linux Process States — 3
Stopped — process is halted can be restarted by another process e.g., a debugger can put a process into stopped state Zombie — a process has terminated but parent did not wait() for it

Process States: vmstat
The “procs” columns give info about process states: “r” — number of processes that are in the ready to run state “b” — number of processes that are in the uninterruptable blocked state

OSSI — ver. 1.5

Processes - p. 22/66

OSSI — ver. 1.5

Processes - p. 23/66

Tools for monitoring processes
Linux provides: vmstat Good to monitor over time: $ vmstat 5 procinfo Easier to understand than vmstat Monitor over time with $ procinfo -f View processes with top — see slides 27 to §30 The system monitor sar shows data collected over time: See man sar; investigate sar -c and sar -q See the utilities in the procps software package. You can list them with $ rpm -ql procps w Processes - p. 24/66 ps OSSI — ver. 1.5 pkill slabtop top watch free uptime snice pmap pgrep vmstat tload skill

Monitoring processes in Win 2000
Windows 2000 provides a tool: Start → Administrative Tools → Performance. Can use this to monitor various statistics

OSSI — ver. 1.5

Processes - p. 25/66

Process Monitoring — top
08:12:13 up 1 day, 13:34, 8 users, load average: 0.16, 0.24, 0.49 111 processes: 109 sleeping, 1 running, 1 zombie, 0 stopped CPU states: cpu user nice system irq softirq iowait idle total 0.0% 0.0% 3.8% 0.0% 0.0% 0.0% 96.1% Mem: 255608k av, 245064k used, 10544k free, 0k shrd, 17044k buff 152460k active, 63236k inactive Swap: 1024120k av, 144800k used, 879320k free 122560k cached PID 1253 1769 23548 1 2 3 4 6 5 USER root nicku nicku root root root root root root PRI 15 16 16 16 15 15 34 15 15 NI SIZE RSS SHARE STAT %CPU %MEM 0 73996 13M 11108 S 2.9 5.5 0 2352 1588 1488 S 1.9 0.6 0 1256 1256 916 R 1.9 0.4 0 496 468 440 S 0.0 0.1 0 0 0 0 SW 0.0 0.0 0 0 0 0 SW 0.0 0.0 19 0 0 0 SWN 0.0 0.0 0 0 0 0 SW 0.0 0.0 0 0 0 0 SW 0.0 0.0 TIME CPU COMMAND 19:09 0X 2:10 0 magicdev 0:00 0 top 0:05 0 init 0:00 0 keventd 0:00 0 kapmd 0:00 0 ksoftirqd/0 0:00 0 bdflush 0:11 0 kswapd

Process Monitoring with top

OSSI — ver. 1.5

Processes - p. 26/66

OSSI — ver. 1.5

Processes - p. 27/66

top: load average
08:12:13 up 1 day, 13:34, 8 users, load average: 0.16, 0.24, 0.49

top: process states
111 processes: 109 sleeping, 1 running, 1 zombie, 0 stopped

load average is measured over the last minute, five minutes, fifteen minutes Over that time is the average number of processes that are ready to run, but which are not executing A measure of how “busy” a computer is.

sleeping I/O running zombie

Most processes (109/111) are sleeping, waiting for

This is the number of processes that are both ready to run and are executing

There is one process here that has terminated, but its parent did not wait() for it. The wait() system calls are made by a parent process, to get the exit() status of its child(ren). This call removes the process control block from the process table, and the child process does not exist any more. (§34) When you press  Control-z © a shell, you will in OSSI — this Processes - p. 29/66 increasever. 1.5 number by 1
 ¨

stopped
OSSI — ver. 1.5 Processes - p. 28/66

top: Processes and Memory
PID USER 1253 root PRI 15 NI SIZE 0 73996 RSS SHARE STAT %CPU %MEM 13M 11108 S 2.9 5.5 TIME CPU COMMAND 19:09 0X

Virtual Memory: suspended processes
With memory fully occupied by processes, could have all in blocked state! CPU could be completely idle, but other processes waiting for RAM Solution: virtual memory will discuss details of VM in memory management lecture Part or all of process may be saved to swap partition or swap file

SIZE

This column is the total size of the process, including the part which is swapped (paged out) out to the swap partition or swap file Here we see that the process X uses a total of 73,996 Kb, i.e., 73,996 × 1024 bytes ≈ 72MB, where here 1MB = 220 bytes.

RSS

The resident set size is the total amount of RAM that a process uses, including memory shared with other processes. Here X uses a total of 13MB RAM, including RAM shared with other processes.

SHARE The amount of shared memory is the amount of RAM that this process shares with other processes. Here

X shares 11,108 KB with other processes.
OSSI — ver. 1.5

Processes - p. 30/66

OSSI — ver. 1.5

Processes - p. 31/66

We can see that the total amount of RAM used exclusively by one process is rss − share. Here we see that X uses about 13 × 220 − 11,108 × 210 ≈ 2 MB

Suspended Processes

Could add more states to process state table: ready and suspended blocked and suspended

Process Control Blocks The Process Table Data structure in OS to hold information about a process

OSSI — ver. 1.5

Processes - p. 32/66

OSSI — ver. 1.5

Processes - p. 33/66

OS Process Control Structures
Every OS provides process tables to manage processes In this table, the entries are called process control blocks (PCBs), process descriptors or task descriptors. We will use the abbreviation PCB. There is one PCB for each process in Linux, PCB is called task_struct, defined in include/linux/sched.h In a Fedora Core or Red Hat system, you will find it in the file /usr/src/linux-2.*/include/linux/sched.h if you have installed the kernel-source software package

What is in a PCB
In slide §3, we saw that a PCB contains: a process ID (PID) process state (i.e., executing, ready to run, sleeping waiting for input, stopped, zombie) program counter, the CPU register that holds the address of the next instruction to be fetched and executed The value of other CPU registers the last time the program was switched out of executing by a context switch — see slide §36 scheduling priority the user that owns the process the group that owns the process pointers to the parent process, and child processes Location of process’s data and program code in memory1.5 OSSI — ver. Processes - p. 35/66 List of allocated resources (including open files) PCB holds the values as they were when process was last switched out of executing by a context switch — see slide §36 Also called state of the process (but since this term has two meanings, we avoid that term here), process context or just context The execution context is all the data that the OS must save to stop one process from executing on a CPU, and load to start the next process running on a CPU This includes the content of all the CPU registers, the location of the code, . . . Includes most of the contents of the process’s PCB.

OSSI — ver. 1.5

Processes - p. 34/66

Context Switch
does a context switch when: stop current process from executing, and start the next ready to run process executing on CPU OS saves the execution context (see §37) to its PCB OS loads the ready process’s execution context from its
OS PCB

Execution Context

When does a context switch occur? When a process blocks, i.e., goes to sleep, waiting for input or output (I / O), or When the scheduler decides the process has had its turn of the CPU, and it’s time to schedule another ready-to-run process A context switch must be as fast as possible, or multitasking will be too slow Very — ver. 1.5 in Linux OS fast OSSI Processes - p. 36/66

OSSI — ver. 1.5

Processes - p. 37/66

Program Counter in PCB
What value is in the program counter in the PCB? If it is not executing on the CPU, The address of the next CPU instruction that will be fetched and executed the next time the program starts executing If it is executing on the CPU, The address of the first CPU instruction that was fetched and executed when the process began executing at the last context switch (§36)

Process Control Blocks—Example
The diagram in slide §40 shows three processes and their process control blocks. There are seven snapshots t0 , t1 , t2 , t3 , t4 , t5 and t6 at which the scheduler has changed process (there has been a context switch—§36) On this particular example CPU, all I / O instructions are 2 bytes long The diagram also shows the queue of processes in the: Ready queue (processes that are ready to run, but do not have a CPU to execute on yet) Blocked, or Wait queue, where the processes have been blocked because they are waiting for I / O to finish.

OSSI — ver. 1.5

Processes - p. 38/66

OSSI — ver. 1.5

Processes - p. 39/66

PCB Example: Diagram
CPU idle

PCB Example — Continued
t6
time

t0

t1

t2

t3

t4

t5

Ready Queue: Blocked Queue:

P3 P2

P3 P1

P1 P2

P2 P3

P3

PCB for P1

0xCAFE Running

0xC0DE Blocked

0xC0DE Ready

0xC0DE Running

Process 1 has terminated; It’s PCB has been freed

Sfrag replacements

PCB for P2

0xFACE Ready

0xFACE Running

0xFEED Blocked

0xFEED Ready

0xFEED Running

Process 2 has terminated PCB is freed

In slide §40, The times t0 , t1 , t2 , t3 , t4 , t5 and t6 are when the scheduler has selected another process to run. Note that these time intervals are not equal, they are just the points at which a scheduling change has occurred. Each process has stopped at one stage to perform I / O That is why each one is put on the wait queue once during its execution. Each process has performed I / O once

PCB for P3

0xDEAF Ready

0xDEAF Ready

0xDEAF Running

0xD1CE Blocked

0xD1CE Ready

0xD1CE Running

P3 has exited; PCB freed

OSSI — ver. 1.5

Processes - p. 40/66

OSSI — ver. 1.5

Processes - p. 41/66

What is the address of I/O instructions?
We are given that all I / O instructions in this particular example are two bytes long (slide §39) We can see that when the process is sleeping (i.e., blocked), then the program counter points to the instruction after the I / O instruction So for process P1, which blocks with program counter PC = C0DE16 , the I / O instruction is at address C0DE16 − 2 = C0DC16 for process P2, which blocks with program counter PC = FEED16 , the I / O instruction is at address FEED16 − 2 = FEEB16 for process P3, which blocks with program counter PC = D1CE16 , the I / O instruction is at address D1CE16 − 2 = D1CC16
OSSI — ver. 1.5 Processes - p. 42/66

Process System Calls How the OS controls processes How you use the OS to control processe

OSSI — ver. 1.5

Processes - p. 43/66

Major process Control System Calls
fork() — start a new process execve() — replace calling process with machine code from another program file wait(), waitpid() — parent process gets status of its’ child after the child has terminated, and cleans up the process table entry for the child (stops it being a zombie) exit() — terminate the current process

IPC Inter Process Communication How Processes can Talk to Each Other

OSSI — ver. 1.5

Processes - p. 44/66

OSSI — ver. 1.5

Processes - p. 45/66

Problem with Processes
Communication! Processes cannot see the same variables Must use Inter Process Communication (IPC) IPC Techniques include: pipes, and named pipes (FIFOs) sockets messages and message queues shared memory regions All have some overhead

Interprocess Communication (IPC)
Pipe — circular buffer, can be written by one process, read by another related processes can use unnamed pipes used in shell programming, e.g., the vertical bar ‘|’ in $ find /etc | xargs file unrelated processes can use named pipes — sometimes called FIFOs Messages — POSIX provides system calls msgsnd() and msgrcv() message is block of text with a type each process has a message queue, like a mailbox processes are suspended when attempt to read from empty queue, or write to full queue.

OSSI — ver. 1.5

Processes - p. 46/66

OSSI — ver. 1.5

Processes - p. 47/66

IPC — Shared Memory
Shared Memory — a Common block of memory shared by many processes Fastest way of communicating Requires synchronisation (See slide 61)
 

IPC — Signals
(SIGQUIT),  Control-Z © stop (SIGSTOP) — A process sends a signal to another process using the kill() system call signals are implemented as single bits in a field in the PCB, so cannot be queued A process may respond to a signal with: a default action (usually process terminates) a signal handler function (see trap in shell programming notes), or ignore the signal (unless it is SIGKILL or SIGSTOP) A process cannot ignore, or handle a SIGSTOP or a SIGKILL signal. A KILL 1.5 signal will always terminate a process (unless - p. 49/66 OSSI — ver. Processes it is in interruptible sleep) A SIGSTOP signal will always send a process into the stopped state. Some signals can be generated from the keyboard, i.e.,  ¨ ¨ Control-C © interrupt (SIGINT);  — Control-\ © quit — 
¨

OSSI — ver. 1.5

Processes - p. 48/66

Signals and the Shell
We can use the kill built in command to make the kill() system call to send a signal A shell script uses the trap built in command to handle a signal Ignoring the signals SIGINT, SIGQUIT and SIGTERM: trap "" INT QUIT TERM Handling the same signals by printing a message then exiting:
trap "echo ’Got a signal; exiting.’;exit 1" INT QUIT TERM

Threads Lightweight processes that can talk to each other easily

Handling the same signals with a function call: signal_handler() { echo "Received a signal; terminating." rm -f $temp_file exit 1 } OSSI — ver. 1.5 Processes - p. 50/66 trap signal_handler INT QUIT TERM Sending a SIGKILL signal to process with PID 3233: $ kill -KILL 3233

OSSI — ver. 1.5

Processes - p. 51/66

Threads and Processes

Threads have own. . .
stack pointer register values scheduling properties, such as policy or priority set of signals they can each block or receive own stack data (local variables are local to thread)

Threads in a process all share the same address space Communication easier Overhead less Problems of locking and deadlock a major issue

Processes have separate address spaces Communication more indirect: IPC (Inter Process Communication) Overhead higher Less problem with shared resources (since fewer resources to share!)

OSSI — ver. 1.5

Processes - p. 52/66

OSSI — ver. 1.5

Processes - p. 53/66

Threads share a lot
Changes made by one thread to shared system resources (such as closing a file) will be seen by all other threads. Two pointers having the same value point to the same data. A number of threads can read and write to the same memory locations, and so you need to explicitly synchronise access

Problem with threads:
Avoid 2 or more threads writing or reading and writing same data at the same time Avoid data corruption Need to control access to data, devices, files Need locking Provide three methods of locking: mutex (mutual exclusion) semaphores condition variables

OSSI — ver. 1.5

Processes - p. 54/66

OSSI — ver. 1.5

Processes - p. 55/66

Race Conditions
race condition — where outcome of computation depends on sheduling an error in coding Example: two threads both access same list with code like this: if ( list.numitems > 0 ) { // Oh, dear, better not change to // other thread here! remove_item( list ); // not here! // ...and not here either: --list.numitems; }

Race Condition

OSSI — ver. 1.5

Processes - p. 56/66

OSSI — ver. 1.5

Processes - p. 57/66

Critical Sections
critical resource — a device, file or piece of data that cannot be shared critical section — part of program only one thread or process should access contains a critical resource i.e., you lock data, not code All the code in the previous slide is a critical section Consider the code: very_important_count++; executed by two threads on a multiprocessor machine (SMP = symmetric multiprocessor)

Race Condition — one possibility
thread 1 read very_important_count (5) add 1 (6) write very_important_count (6) read very_important_count (6) add 1 (7) write very_important_count (7) thread 2

OSSI — ver. 1.5

Processes - p. 58/66

OSSI — ver. 1.5

Processes - p. 59/66

Example — another possibility
thread 1 read very_important_count (5) read very_important_count (5) add 1 (6) add 1 (6) write very_important_count (6) write very_important_count (6) thread 2

Solution: Synchronisation
Solution is to recognise critical sections use synchronisation, i.e., locking, to make sure only one thread or process can enter critical region at one time. Methods of synchronisation include: file locking semaphores monitors spinlocks mutexes

OSSI — ver. 1.5

Processes - p. 60/66

OSSI — ver. 1.5

Processes - p. 61/66

File Locking
For example, an flock() system call can be used to provide exclusive access to an open file The call is atomic It either: completely succeeds in locking access to the file, or it fails to lock access to the file, because another thread or process holds the lock No “half-locked” state No race condition Alternatives can result in race conditions; for example: thread/process 1 checks lockfile thread/process 2 checks lockfile a very short time later both processes think they have exclusive write access to the file file is corrupted by two threads/processes writing to it OSSI — Processes - p. 62/66 at the ver. 1.5 time same

Summary and References

OSSI — ver. 1.5

Processes - p. 63/66

Summary — Process States, Scheduling
Scheduler changes processes between ready to run and running states context switch: when scheduler changes process or thread Most processes are blocked, i.e., sleeping: waiting for I / O understand the process states why a process moves from one state to another Communication between processes is not trivial; IPC methods include pipes shared memory messages signals semaphores

Summary — Processes and Threads
With Linux and Unix, main process system calls are fork(), exec() and wait() Threads are lightweight processes part of one process share address space can share data easily sharing data requires synchronisation, i.e., locking

OSSI — ver. 1.5

Processes - p. 64/66

OSSI — ver. 1.5

Processes - p. 65/66

References
There are many good sources of information in the library and on the Web about processes and threads. Here are some I recommend: Operating Systems: A Modern Perspective: Lab Update, 2nd Edition, Gary Nutt, Addison-Wesley, 2002. A nice text book that emphasises the practical (like I do!) William Stallings, Operating Systems, Fourth Edition, Prentice Hall, 2001, chapters 3, 4 and 5 Deitel, Deitel and Choffnes, Operating Systems, Third Edition, Prentice Hall, 2004, ISBN 0-13-1182827-4, chapters 3, 4 and 5 Paul Rusty Russell, Unreliable Guide To Locking http://kernelnewbies. org/documents/kdoc/kernel-locking/lklockingguide.html Eric S. Raymond, The Art of UNIX Programming, Addison-Wesley, 2004, ISBN 0-13-142901-9.

OSSI — ver. 1.5

Processes - p. 66/66