CS 452/652 Fall 2022 - Lecture 33

March 30, 2022 prev

Real-Time in General-Purpose (Operating) Systems

duration of operating system services
- hardware interrupt arbitration and servicing
synchronization, e.g., for memory allocation
time-slicing preemption → fairness & run-time
real-time: few tasks, no CPU bottleneck, latency << period
⇒ ensure high-priority and limit interrupt processing

Multi-Core Scheduling

optimal multiprocessor scheduling is NP-hard
optimality: minimalize overall task completion time

Multi-Core Programming

Parallelism

multiple independent execution streams
- unknown and non-deterministic execution
- somewhat similar to effects of asynchronous interrupt
- shared counter needs atomic operations

example: ticket lock

shared state
```
  int ticket = 0;
  int serving = 0;
```

critical section

  int myticket = ticket++;
  while (myticket != serving) { // wait }
  ... // critical section
  serving++;

ticket++ must be atomic operation

Memory Ordering

each core respects sequential data dependencies
- what about sequential execution without data dependencies?
- example, assume A and B initialized to 0, then:
```
  Thread 1    Thread 2
  A=1         B=1
  print(B)    print(A)
```
- possible outcomes? 00 is counter-intuitive...
memory hierarchy & pipeling → out-of-order execution
- write buffers, caching hierarchy
- amplifies parallelism challenge
think of the effects as operations that "float" around

example: Dekker's Algorithm (software locking)

shared state

  int wantIn[2] = {false, false};
  int turn = 0;

thread initialization (other thread: me = 1)
```
  int me = 0;
  int you = 1 - me;
```

critical section

  wantIn[me] = true;
  while (wantIn[you]) {
    if (turn != me) {
      wantIn[me] = false;
      while (turn != me) { // wait }
      wantIn[me] = true;
    }
  }
  ... // critical section
  turn = you;
  wantIn[me] = false;

need memory barriers after each wantIn[me] = true

example memory model: total-store-order (TSO)
- write can be delayed after read
- write/write not reordered
RISC (such as ARM) processors often implement more relaxed models (more reordering)
trade-off: programming semantics ↔ performance

Mechanisms

C 'volatile' avoids compiler reordering and register caching
atomic instructions: consistency/correctness of parallel operations
memory barrier/fence: execution ordering

Sequential Consistency

one of many consistency models
- formal description effects of parallel operations on mutable state
- formal reasoning about program correctness
- some model more restricted, some more relaxed
intuitive model: direct shared memory (no buffering)
- writes become globally visible in local per-processor order
- some global sequence of writes
- 'print' example above: sequential consistency prohibits 00 outcome
atomic operation guarantees SC for atomic variables
memory barrier guarantees SC for critical section data
- need memory barrier after critical section (and possibly before)

Additional Notes

Java 'volatile' essentially means SC
x86 atomic instructions include barrier semantics