CS 452/652 Fall 2019 - Lecture 34

Real-Time in General-Purpose (Operating) Systems

• duration of operating system services
  • hardware interrupt arbitration and servicing
• synchronization, e.g., 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: minimum overall task completion time

Multi-Core Programming

Challenges

• parallelism: multiple independent execution streams
  • unknown and non-deterministic ordering
  • somewhat similar to effects of asynchronous interrupt
  • example: shared counter -> need atomic operations
• 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
  • also amplifies parallelism challenge
• think of the effects as "floating" operations
• example model: total-store-order (TSO)
  • writes can be delayed after reads
  • 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
• memory barrier: execution ordering
• atomic instructions: consistency/correctness of parallel operations

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 barrier after wantIn[me] = true

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 (including fetch)

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)
• Note: Java 'volatile' essentially means SC
• x86 atomic instructions include barrier semantics