CS 452/652 Fall 2022 - Lecture 3

Polling Patterns

• generic polling loop

  for (;;) {
    if( c1 ) a1();
    if( c2 ) a2();
    ...
  }
  

  ⇒ worst-case latency: sum of all actions

• higher-frequency input/condition 'c1':

  for (;;) {
    if( c1 ) a1();
    if( c2 ) a2();
    if( c1 ) a1();
    if( c3 ) a3();
    ...
  }
  

  ⇒ worst-case latency: maximum of all actions

• latency still too high? break up action into parts

  for (;;) {
    if( c1 ) a1();
    if( c2 ) { a2.1(); a2half = true; }
    if( c1 ) a1();
    if( a2half ) { a2.2(); a2half = false; }
    ...
  }
  

• quickly gets complicated and is not flexible

Concurrency

• manage independent activities or concerns
• conceptual reasons: software structure, runtime management
• practical reasons: parallel hardware
• multi-tasking: abstraction for concurreny

Multi-Tasking

• asynchronous system implemented via synchronous control flow
• kernel: creates and manages tasks
• each with synchronous control flow
• key concern: stack

Kernel Overview

• uninterruptible (thus predictable) system manager
• hardware typically supports at least "user" and "system" modes
• "system" mode: with all privileges → "dangerous" operations possible
• microkernel → device drivers outside kernel
• normal scope: memory, threading, communication
• here: tasks and message passing
  • do not use shared memory between tasks
  • hardware protection optional
• entry/exit between kernel and user-level tasks
  • software interrupt - system call
  • hardware interrupt - device activity

Generic Kernel Loop

void kmain() {
  initialize();  // includes starting the first user task
  for (;;) {
    currtask = schedule();
    request = activate(currtask);
    handle(request);
  }
}

Task State

• management state: Ready, Active, Blocked, etc.
• meta information: parent task
• execution state
  • high-level language: line of code, variables
  • machine-level: program counter, stack (content, pointer), status register, other registers
  • type / shared: code, readonly data, write-once?
  • instance / private: state - read/write data
  • primarily on stack
  • ok to use static global for singleton tasks with subroutines

Task Descriptor

• in-kernel data structure holding task state → need queues for management
• no heap → use intrusive linkage, i.e., embed 'next' pointer

Memory Management

• C/C++ provide very good control over memory layout of structured data
  • use pointer casting to switch between unstructured and structured view
  • alternative: union declaration
  • if necessary, GCC extensions could be used to increase control over memory layout
• techniques for dynamic data structures without heap
  • intrusive linkage, i.e., embed next (and/or other) pointers in data strucure
  • slab allocation: dedicated memory region for each relevant data type
    • stored freed objects in free list, use intrusive overlay (cast/union, see above) to manage
    • allocate first from free list, then from slab
  • use stack or static (file-)local memory for private / slab
  • when using static memory: do not share between tasks!

Programming

• important principle: KISS
  • related: "premature optimization is the root of all evil" (Donald Knuth)
• availability of resources: track < ARM < developer < PC
• think strategically about
  • functionality: start simple, add functionality in small steps
    • test (and commit) at each step
  • data structures: encapsulate, start simple, exchange later
  • bugs: not every bug is a show-stopper
• use unit testing where possible
• use assertions generously!
• hardware emulation, such as QEMU → unclear cost/benefit