CSE 451

Operating Systems

L6 - Concurrency: Processes and Threads

​

​

Slides by: Tom Anderson

Baris Kasikci

Process Lifetime

C program -> process

• Compile .c files into .o files
• Link .o files into executable
• ELF: Executable and linkable format
• Header: an array of memory segments: code, data, bss (zero’ed data)
• File offset (start of segment in executable file)
• Virtual address start (where this segment goes in process address space)
• Size of segment in process address space
• Size of segment in file (for uninitialized data, can be different)
• Permission: execute only (code), read-only, read-write (data)
• Sequence of segments
• Code
• Data
• bss, heap, and stack initialized on process start, not from ELF file

To create a new process to run a program

• Create and initialize the process control block (PCB)
• Assign each process a unique ID (process ID)
• Create and initialize a new address space
• Load the program into the address space (using ELF file)
• Copy arguments into memory in the address space
• Eg, “To be or not” is an argument to grep
• Initialize the hardware context to start execution at ``start’’
• start.S – assembly code to set up stack frame and call to main procedure
• If main returns, start.S calls process exit
• Inform the scheduler that the new process is ready to run

Example process control block (proc.h)

Windows CreateProcess API (simplified)

if (!CreateProcess(

NULL,

argv[1], NULL, NULL, FALSE, 0, NULL, NULL,

&si,

&pi )

// No module name (use command line)

// Command line

// Process handle not inheritable

// Thread handle not inheritable

// Set handle inheritance to FALSE

// No creation flags

// Use parent's environment block

// Use parent's starting directory

// Pointer to STARTUPINFO structure

// Pointer to PROCESS_INFORMATION structure

)

UNIX Process API

• UNIX fork – create a copy of the current process, and start it running
• No arguments!
• UNIX exec – change the program being run by the current process
• Put the name of the program and its arguments on the stack before calling main
• UNIX wait – wait for a process to finish
• UNIX exit – program is complete (waiter can return)
• UNIX signal – send a notification to another process (eg, to kill a runaway process)

UNIX Process Management

Question: What does this code print?

int child_pid = fork();

if (child_pid == 0) { // I'm the child process printf("I am process #%d\n", getpid());

return 0;

} else { // I'm the parent process printf("I am parent of process #%d\n", child_pid); return 0;

}

UNIX shell

A shell is a user application that runs other programs

• Often with its own programming language

% grep “To be or not” Shakespeare.txt

% grep “To be or not” Shakespeare.txt > logfile

% grep “To be or not” Shakespeare.txt > logfile &

% grep “To be or not” Shakespeare.txt | wc

// run grep, output to stdout

// run grep, output to logfile

// same, but do it in the background

// run grep and wc, output of grep

// goes to input of wc

How can the shell use fork/exec to do these?

Grep has no knowledge of where its output is going

Base case: create a process with arguments

// grep “To be or not” Shakespeare.txt char *prog, **args;

int child_pid;

while (readAndParseCmdLine(&prog, &args)) {// Read and parse the input a line at a time

// create a child process

// I'm the child process. Run prog

if ((child_pid = fork()) == 0) { exec(prog, args);

} else {

wait(child_pid); return 0;

}

}

// I'm the parent, wait for child

Redirect to file “logfile”

// grep “To be or not” Shakespeare.txt > logfile

if ((child_pid = fork()) == 0) { int fd = open(“logfile”); dup2(fd, stdout);

exec(“grep”, args);

} else {

wait(child_pid); return 0;

}

}

// create a child process

// replace stdout with fd

// Then run grep

// I'm the parent, wait for child

Connect two processes with a pipe

// grep “To be or not” Shakespeare.txt | wc pipe(&fd[2]);

if ((child1 = fork()) == 0) {

dup2(fd[1], stdout);

exec(“grep”, grepargs);

} else if (child2 = fork()) == 0) { dup2(fd[0], stdin);

exec(“wc”, wcargs);

} else {

wait(child1); wait(child2);

}}

// create the pipe

// create one child process

// replace stdout with one end of the pipe

// Then run grep

// create the second child process

// replace stdin with other end of the pipe

// wait for both children to finish

Questions

• Can UNIX fork() return an error? Why?
• :(){ :|:& };:

​

• Can UNIX exec() return an error? Why?

​

• Can UNIX wait() ever return immediately? Why?

Implementing UNIX fork/exec

Steps to implement UNIX fork

• Create and initialize the process control block (PCB)
• Create a new address space
• Initialize the address space with a copy of the entire contents of the address

space of the parent

• Inherit the execution context of the parent (e.g., any open files)
• Inform the scheduler that the new process is ready to run

Steps to implement UNIX exec

• Load the program into the current address space
• Copy arguments into memory in the address space (where?)
• Initialize the hardware context to start execution at ``start''

Is UNIX fork too slow?

• Make copy of address space
• What if process is large?
• Instead: virtual copy of address space
• Make a copy of the page table
• Both parent and child point to the same physical pages
• Mark both parent and child pages as “read-only”
• What if parent or child modifies memory (eg, stack)?
• Hardware will page fault (write to read-only page)
• Kernel can copy-on-write – make a copy of each page that’s modified
• Resume execution with page table entry as “read-write”

Concurrency: Threads

• Can multiple executions share the same address space?
• Yes! The operating system kernel runs multiple processes on different cores
• Yes! The operating system kernel can multiplex processes on one core
• In each case, multiple system calls can be active at the same time
• Also: interrupts, background tasks, system maintenance
• Applications can also benefit from concurrency
• Thread to handle user input
• Thread to do operation user requested
• Humans are not very good at keeping track of multiple things happening simultaneously

Definitions

• A thread is a single execution sequence that represents a separately schedulable task
• Single execution sequence: familiar programming model
• Separately schedulable: OS can run or suspend a thread at any time
• Protection is an orthogonal concept
• Can have one or many threads per protection domain
• Kernel itself has many threads

Multithreaded OS Kernel

Multithreaded User Processes

Process Thread Lifetime

Thread Operations

• thread_create(thread, func, args)
• Create a new thread to run func(args)
• thread_yield()
• Relinquish processor voluntarily
• thread_join(thread)
• In parent, wait for child thread to exit, then return
• thread_exit
• Quit thread and clean up, wake up joiner if any

Déjà vu?

• Didn’t we learn all about concurrency in CSE 332/333?
• More practice
• Realistic examples, especially in the project
• Design patterns and pitfalls
• Methodology for writing correct concurrent code
• Implementation
• How do threads work at the machine level?
• CPU scheduling
• If multiple threads to run, which do we do first?

Thread Abstraction

• Infinite number of processors
• Threads execute with variable speed
• Programs must be designed to work with any schedule

Question

Why do threads execute at variable speed?

Programmer vs. Processor View

Possible Executions

Example: threadHello

#define NTHREADS 10 thread_t threads[NTHREADS]; main() {

for (i = 0; i < NTHREADS; i++) thread_create(&threads[i], &go, i); for (i = 0; i < NTHREADS; i++) {

exitValue = thread_join(threads[i]);

printf("Thread %d returned with %ld\n", i, exitValue);

}

printf("Main thread done.\n");

}

void go (int n) {

printf("Hello from thread %d\n", n); thread_exit(100 + n);

// REACHED?

}

Implementing threads

• thread_create(func, args)
• Allocate thread control block
• Allocate stack
• Build stack frame for base of stack (stub)
• Put func, args on stack
• Put thread on ready list
• Will run sometime later (maybe right away!)
• stub(func, args):
• Call (*func)(args)
• If func returns, call thread_exit()

Thread Stack

• What if a thread puts too many procedures on its stack?
• What happens in Java?
• What happens in the Linux kernel?
• What happens in xk?
• What should happen?

xk swtch (swtch.S)

swtch:

// callee save registers already saved

// ptr to old PCB is in rdi push %rbp

push %rbx

push %r11 push %r12 push %r13 push %r14 push %r15

mov %rsp, (%rdi)

// ptr to new PCB is in rsi mov %rsi, %rsp

pop %r15 pop %r14 pop %r13 pop %r12 pop %r11 pop %rbx pop %rbp ret

A Subtlety

• Thread_create puts new thread on ready list
• When it first runs, some thread calls swtch
• Saves old thread state to stack
• Restores new thread state from stack

=> Set up newly created thread so that swtch will ”resume” at start of

thread

Stack Progression

Timer Interrupt -> swtch

Two Threads Call Yield