COS 318: Operating Systems Processes and Threads

Jaswinder Pal Singh Computer Science Department Princeton University (http://www.cs.princeton.edu/courses/cos318/)

Todays Topics
! ! !

Concurrency Processes Threads Reminder:

Hope youre all busy implementing your assignment

Concurrency and Process

Concurrency
" " "

Hundreds of jobs going on in a system CPU is shared, so are I/O devices Each job would like to have its own computer Decompose complex problems into simple ones Make each simple one a process Deal with one at a time Each process feels like it has its own computer

Process concurrency
" " " "

Example: gcc (via gcc pipe v) launches

/usr/libexec/cpp | /usr/libexec/cc1 | /usr/libexec/as | /usr/libexec/elf/ld Each instance is a process

"

Process Parallelism
!

Virtualization
" " "

Each process runs for a while Each virtually has its own CPU Make one CPU seem like many CPU process overlaps with I/O Each runs almost as fast as if it had its own computer Reduce total completion time for all processes Multiple CPUs (such as SMP) Processes running in parallel Speedup

emacs gcc CPU 3s I/O 2s CPU 3s CPU 3s CPU 3s

emacs

I/O parallelism
" " "

CPU 3s I/O 2s

9s

CPU parallelism
" " "

3s

More on Process Parallelism

Process parallelism is common in real life

Each sales person sell $1M annually Hire 100 sales people to generate $100M revenue Ideal speedup is factor of N Reality: bottlenecks + coordination overhead Can you speed up by working with a partner? Can you speed up by working with 20 partners? Can you get super-linear (more than a factor of N) speedup?

Speedup
" "

Question
" " "

Simplest Process
!

Sequential execution
" " "

No concurrency inside a process Everything happens sequentially Some coordination may be required Registers Main memory I/O devices
File system Communication ports

Process state
" " "

"

Program and Process

main() { ... foo() ... } bar() { ... }

main() { ... foo() ... } bar() { ... }

heap

stack

Program

registers PC Process

Process vs. Program

Process > program

Program is just part of process state Example: many users can run the same program
Even though the program has a single set of variable names, the same variable in different instances may have different values The different processes running the program have different address spaces

Process < program

A program can invoke more than one process Example: Fork off processes

Process Control Block (PCB)

Process management info

" " "

State Ready: ready to run Running: currently running Blocked: waiting for resources Registers, EFLAGS, and other CPU state Stack, code and data segment Parents, etc Segments, page table, stats, etc Communication ports, directories, file descriptors, etc. Resource allocation and process state transition

! ! !

Memory management info

I/O and file management

How OS takes care of processes

Question: why is some information indirect?

Primitives of Processes
!

Creation and termination

Exec, Fork, Wait, Kill Action, Return, Handler Block, Yield We will talk about this later

Signals
"

Operations
"

Synchronization
"

10

Make A Process
!

Creation
" " " "

Load code and data into memory Create an empty call stack Initialize state to same as after a process switch Make the process ready to run Stop current process and save state Make copy of current code, data, stack and OS state Make the process ready to run

Clone
" " "

11

Example: Unix
!

How to make processes:

fork clones a process exec overlays the current process

If ((pid = fork()) == 0) { /* child process */ exec(foo); /* does not return */ else /* parent */ wait(pid); /* wait for child to die */

12

Process Context Switch

Save a context (everything that a process may damage)

All registers (general purpose and floating point) All co-processor state Save all memory to disk? What about cache and TLB stuff? Does the reverse OS code must save state without changing any state How to run without touching any registers?
CISC machines have a special instruction to save and restore all registers on stack RISC: reserve registers for kernel or have way to carefully save one and then continue
13

! !

Start a context
"

Challenge
" "

Process State Transition

Running

or it f e Wa ourc res

Create

Ready Resource becomes available

Blocked

14

Threads
!

Thread
" "

A sequential execution stream within a process (also called lightweight process) Threads in a process share the same address space Easier to program I/O overlapping with threads than signals Users often like to do several things at a time: Web browser A server (e.g. file server) serves multiple requests Multiple CPUs sharing the same memory

Thread concurrency
" " " "

15

Thread Control Block (TCB)

State
Ready: ready to run Running: currently running Blocked: waiting for resources

" " " " "

Registers Status (EFLAGS) Program counter (EIP) Stack Code

16

Typical Thread API

Creation
"

Fork, Join Acquire (lock), Release (unlock) Wait, Signal, Broadcast Alert, AlertWait, TestAlert

Mutual exclusion
"

Condition variables
"

Alert
"

17

Revisit Process
!

Process
" " "

Threads Address space Environment for the threads to run on OS (open files, etc)

Simplest process has 1 thread

Process

18

Thread Context Switch

Save a context (everything that a thread may damage)

All registers (general purpose and floating point) All co-processor state Need to save stack? What about cache and TLB stuff? Does the reverse

Start a context
"

May trigger a process context switch

19

Procedure Call
! !

Caller or callee save some context (same stack) Caller saved example:

save active caller registers call foo foo() { do stuff } restore caller regs

20

Threads vs. Procedures

Threads may resume out of order

Cannot use LIFO stack to save state Each thread has its own stack Do not partition registers Each thread has its own CPU Procedure call can use compiler to save state synchronously Threads can run asynchronously Multiple threads can run on multiple CPUs in parallel Procedure calls are sequential

Threads switch less often

Threads can be asynchronous

Multiple threads
" "

21

Process vs. Threads

Address space
" " "

Processes do not usually share memory Process context switch page table and other memory mechanisms Threads in a process share the entire address space Processes have their own privileges (file accesses, e.g.) Threads in a process share all privileges Do you really want to share the entire address space?

Privileges
" "

Question
"

22

Real Operating Systems

One or many address spaces One or many threads per address space

1 address space

Many address spaces

1 thread per address space Many threads per address spaces

MSDOS Macintosh

Traditional Unix

Embedded OS, Pilot

VMS, Mach (OS-X), OS/2, Windows NT/XP/Vista, Solaris, HP-UX, Linux

23

Summary
!

Concurrency
" " "

CPU and I/O Among applications Within an application Abstraction for application concurrency Abstraction for concurrency within an application

Processes
"

Threads
"

24