Prev Next

fork() and Synchronization

Pipes

Chains of communicating processes can be created by exploiting the pipe() system call.

pipe() creates an anonymous pipe object and returns a two file descriptors: one for the read-only end, and the other for the write-only end.
Anything written to the write-only end of the pipe is immediately available at the read-only end of the pipe.
Pipe contents are buffered in memory.
Why is this useful?

IPC Using `fork()` and `pipe()`

Before calling fork() the parent creates a pipe object by calling pipe().
Next, it calls fork().
After fork() the parent closes its copy of the read-only end and the child closes its copy of the write-only end.
Now the parent can pass information to the child.

# pipeEnds[0] gets the read end; pipeEnds[1] gets the write end.
int pipeEnds[2];

pipe(pipeEnds);

int returnCode = fork();

if (returnCode == 0) {

  # Don't need a loopback.
  close(pipeEnds[1]);

  # Read some data from the pipe.
  char data[14];
  read(pipeEnds[0], data, 14);
} else {

  # Don't need a loopback.
  close(pipeEnds[0]);

  # Write some data to the pipe.
  write(pipeEnds[1], "Hello, sweet child!\n", 14);
}

Issues with `fork()`

Copying all that state is expensive!

Especially when the next thing that a process frequently does is start load a new binary which destroys most of the state fork() has carefully copied!

Several solutions to this problem:

Optimize existing semantics: through copy-on-write, a clever memory-management optimization we will discuss in several weeks.
Change the semantics: vfork(), which will fail if the child does anything other than immediately load a new executable.
- Does not copy the address space!

What if I don’t want to copy all of my process state?

fork() is now replaced by clone(), a more flexible primitive that enables more control:
- over sharing, including sharing memory, and signal handlers,
- and over child execution, which begins at a function pointer passed to the system call instead of resuming at the point where fork() was called.
Try man clone in your CSE421 VM.

The Tree of Life

fork() establishes a parent-child relationship between two process at the point when each one is created.
The pstree utility allows you to visualize these relationships.

Fast Forward: Synchronization

What you need to know

The OS creates the illusion of concurrency by quickly switching the processor(s) between multiple threads
- We will back up and discuss how this happens after discussion synchronization
Threads are used to abstract and multiplex the CPU

Pandora’s Concurrency Box

The illusion of concurrency is both powerful and useful:

It helps us think about how to structure our applications.
It hides latencies caused by slow hardware devices.

Unfortunately, concurrency also creates problems:

Coordination: how do we enable efficient communication between the multiple threads involved in performing a single task?
Correctness: how do we ensure that shared state remains consistent when being accessed by multiple threads concurrently? How do we enforce time-based semantics?
We will focus on correctness today but return to coordination later.

Patient 0

The operating system itself is one of the most difficult concurrent programs to write. Why?

It is multiplexing access to hardware resources and therefore sharing a great deal of state between multiple processes!
It frequently uses many threads to hide hardware delays while servicing devices and application requests.
Lots of shared state plus lots of threads equals a difficult synchronization problem.
Also, if the operating system gets synchronization wrong bad things happen.

Concurrency v. Parallelism

The Go developers have a great description of this distinction. According to them:

…when people hear the word concurrency they often think of parallelism, a related but quite distinct concept. In programming, concurrency is the composition of independently executing processes, while parallelism is the simultaneous execution of (possibly related) computations. Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once.

Watch the video to find out more.

Unless Shown Otherwise…

Concurrency forces us to relax any assumptions that we may want to make about how any particular thread executes.

Unless explicitly synchronized, threads may:

Be run in any order,
Be stopped and restarted at any time,
Remain stopped for arbitrary lengths of time.

Generally these are good things—the operating system is making choices about how to allocate resources.
When accessing shared data these are challenges that force us to program more carefully.

The Bank Example

Consider the following code snippet.

void giveGWATheMoolah(account_t account, int largeAmount) {
  int gwaHas = get_balance(account);
  gwaHas = gwaHas + largeAmount;
  put_balance(account, gwaHas);
  notifyGWAThatHeIsRich(gwaHas);
  return;
}

Assume I have $1,000 and that two of you are trying to make deposits concurrently:

One of you is depositing $1,000 (this person gets a B).
One of you is depositing $2,000 (A- material).

Things Go Well

A- Student	B Student	Balance
		$1000
`int gwaHas = get_balance(account); gwaHas = gwaHas + $2000; put_balance(account, gwaHas);`		$3000
	`int gwaHas = get_balance(account); gwaHas = gwaHas + $1000; put_balance(account, gwaHas);`	$4000

Things Go Less Well

A- Student B Student Balance

$1000

int gwaHas = get_balance(account);
gwaHas = gwaHas + $2000;

int gwaHas = get_balance(account);
gwaHas = gwaHas + $1000;

put_balance(account, gwaHas);

$2000

put_balance(account, gwaHas);

$3000

Things Go Very Badly

A- Student B Student Balance

$1000

int gwaHas = get_balance(account);
gwaHas = gwaHas + $2000;

int gwaHas = get_balance(account);
gwaHas = gwaHas + $1000;

put_balance(account, gwaHas);

$3000

put_balance(account, gwaHas);

$2000

Race Conditions

A race condition is "when the output of a process is unexpectedly dependent on timing or other events."

Note that the definition of a race depends on what we expected to happen:

We expected me to have $4,000 after both deposits. (Otherwise we are not observing the Law of the Conversation of Money, probably important to banks except during bailouts.)