CS 452/652 Fall 2022 - Lecture 14

Software Design

Basics

• each problem presents a complexity floor
  • how many inputs?
  • timing requirements?
  • computational complexity?
  • load & performance requirements?
• no software design/engineering in the world can produce a simpler solution
• but: it is possible to screw up and build an even more complex solution!

Objectives

• correctness → here: deadlock avoidance
• maintenance: multiple developers over time
• performance/control → maximize concurrency
• timeliness → here: watch your idle time
• ⇒ use simplest possible patterns!

Patterns

• scope of patterns
  • control flow
  • concurrency
  • communication
  • synchronization
• patterns must be restrictive to be useful
  • simplicity can only be attained by excluding functionality

Task Types

• client - application logic; typically blocks on send
• server - backend logic; typically blocks on receive
• worker - simple!

Worker Patterns

• notifier - blocks on events (interrupts)

  for (;;) {
    AwaitEvent()
    Send()
  }
  

• courier - transmits data between servers

  for (;;) {
    Send(server1, req, msg); // pull from server1
    Send(server2, msg);      // push to server2
  }
  

Server Patterns

• proprietor
  • controls access to backend server(s)
  • no internal buffering, serial execution
  • can reply before processing request
  • if exclusive client to back-end server: can use Send()

  for (;;) {
    Receive(msg)
    Process(msg) // interact with back-end server
    Reply()
  }
  

• administrator
  • generalization of proprietor
  • reorder requests, buffer requests, and/or park clients
  • interact with multiple clients and servers

Suggestions

• build small independent control loops
  • localized location estimate vs. route-based location estimate
• deadlock avoidance
  • avoid circular send
  • avoid circular receive
  • ⇒ do not mix Send() & Receive() in same task!
    • notwithstanding exception in proprietor pattern (see above)
• higher concurrency through more smaller tasks
• modularity → lower complexity through more smaller tasks?
• possible reference design: one design idea - not necessarily perfect!
  • early paper (accessible from UW IP addresses):
    Message passing between sequential processes: The reply primitive and the administrator concept