CS 452/652 Winter 2023 - Lecture 6

Communication: Send-Receive-Reply (SRR)

• synchronous communication; no asynchronous buffering
• sender state: Ready, SendWait, ReplyWait
• receiver state: Ready, ReceiveWait
• sender first
  • receiver tid: look up receiver - not in ReceiveWait
  • sender blocks (Ready -> SendWait)
  • where to store information about senders? per receiver
• receiver arrives to waiting sender
  • finds sender - sanity check for SendWait
  • sender still blocked (SendWait → ReplyWait)
  • kernel copies data
• receiver first
  • no sender found
  • receiver blocks (Ready → ReceiveWait)
  • store receive-blocked tasks in kernel container? only for cleanup/housekeeping
• sender arrives to waiting receiver
  • receiver tid: look up receiver - in ReceiveWait
  • unblock receiver (ReceiveWait → Ready)
  • block sender (Ready → ReplyWait)
  • kernel copies data
• reply
  • non-blocking: sender must be waiting
  • sender tid: look up sender - sanity check for ReplyWait
  • unblock sender (ReplyWait → Ready)
  • kernel copies data
• receive and reply can be decoupled
  • in time: sender parked until later reply (reordering)
  • in space: different task replies than original receiver (delegation)
• kernel provides SRR functionality
  • provide mechanisms for blocking senders and/or receivers
  • message copying for safe asynchronous operation of sender & receiver
    • direct copy from sender to receiver and vice versa
    • no message buffering in kernel
  • kernel must also set return codes appropriately
• messages: structured data
  • no conversion (marshalling) needed as in heterogeneous distributed systems
  • copied as byte (char) array
  • type-checking: verify type of message for type of task?
    ⇒ need at least a global type field per message

Synchronization

• no shared memory; no memory synchronization
• no lock, semaphore, condition variable
• task synchronization via SRR
• resource synchronization via task patterns
  • example: track server mediates access to track
• device synchronization via AwaitEvent() system call

SRR for Producer/Consumer

• single producer, single consumer (SPSC)
  • producer sends, consumer responds with ack: "push" communication
  • consumer sends/requests, producer responds with element: "pull" communication
• multiple producers, single consumer (MPSC)
  • push communication works ⇒ producers are senders
  • pull communication: slow producer might block consumer (and thus other producers)
• single producer, multiple consumers (SPMC)
  • push communication: slow consumer might block produce (and thus other consumers)
  • pull communication works ⇒ consumers are senders
• multiple producers, multiple consumers (MPMC)
  • need intermediary: buffer ("distributor", "warehouse")
  • buffer: acts as single consumer to producers, single producer to consumers
  • buffer full or empty: block respective producer(s)/consumer(s)?
    • design decision: blocking vs. non-blocking (return error) operation
  • buffer receives requests, processes request, (delayed?) response
  • buffer never sends, only receives ⇒ server pattern

Server

• execution pattern:
  1. receive request
  2. process request
  3. (delayed) reply
• server always ready or working, never blocked!
• server never in SRR-"send" role

Name Resolution

• pervasive topic in computer science
• examples:
  • systems: memory address - name for circuit, name for device register
  • programming: variable - name for memory location or register
  • operating system: file - name for data on disk
  • Internet: DNS - name for IP address
  • Internet: URL - name for remote file/service and access protocol
• name resolution always starts in a default context with a default starting point!
  • file system: / (slash) & kernel
  • Internet domain names: . (dot) & local resolver
• this is called closure mechanism
• here: default name server
  • implicit/default starting point: tid of name server
  • use hack: global, hard-coded, other?
• tid-based communication facilitated by kernel (see 'Communication' earlier)

Name Server

• names are null-terminated character arrays
• maximum length? error? truncate?
• WhoIs()for non-existing name? error? block?
• RegisterAs() with previous registration for same name?
• design of name server (data structure and operation):
  • how many names?
  • how often is name server used? when?
  • latency-critical?