SCSJ 4423 – Real-Time Software Engineering

Consolidated Study Notes (Chapters 5–9)

Exam-prep summary covering Concurrency, Mechanisms to Support Concurrency, RTOS, and Real-Time Scheduling & Schedulability Analysis.

---

Table of Contents

1. Chapter 5 – Introduction to Concurrency
2. Chapter 6 – Mechanisms to Support Concurrency
3. Chapter 7 – Concurrent Programming in Practice (BACI/jBACI)
4. Chapter 8 – Real-Time Operating Systems (RTOS)
5. Chapter 9 – Real-Time Scheduling & Schedulability Analysis
6. Quick Formula Sheet

---

Chapter 5 – Introduction to Concurrency

What is Concurrency?

• Concurrency = the ability of a system to handle multiple tasks that are in progress at the same time (their lifetimes overlap), whether or not they physically execute simultaneously.
• It is about dealing with many things at once (structure); parallelism is about doing many things at once (execution).

Concurrency vs. Parallelism

Aspect	Concurrency	Parallelism
Definition	Tasks make progress in overlapping time periods	Tasks execute literally at the same instant
Hardware	Possible on a single processor (interleaving)	Requires multiple processors/cores
Mechanism	Interleaving (time-sharing one CPU)	Overlapping (true simultaneous execution)
Goal	Structure / responsiveness	Speed-up / throughput

• Interleaving – one processor rapidly switches among tasks → appears simultaneous (semi/pseudo concurrency).
• Overlapping – multiple processors run tasks at the same real time (true concurrency).

Types of Concurrency

• Semi (pseudo) concurrency – single processor, achieved by interleaving/time-slicing.
• True concurrency – multiple processors executing simultaneously (parallelism).

Process vs. Thread

	Process	Thread
Definition	Program in execution with its own address space	Lightweight unit of execution within a process
Memory	Separate (isolated) memory space	Shares the process's memory/resources
Overhead	Heavy (context switch expensive)	Light (fast to create/switch)
Communication	IPC (message passing, pipes)	Shared variables (needs synchronization)
Terms	Multiprogramming = many processes	Multithreading = many threads in one process

Sequential vs. Concurrent

• Sequential program – single thread of control; statements execute one after another in a defined order.
• Concurrent program – multiple threads of control that may execute in parallel or be interleaved.
• Concurrent system – the executing environment (hardware + OS + RTSS) that supports concurrent programs.
• Concurrent program – the software describing the cooperating tasks.

Nature of Concurrent Systems

• Tasks are (largely) independent but may need to cooperate and compete for shared resources.
• Execution order between independent tasks is non-deterministic (not fixed).

The 6 Problems in Concurrent Programming

1. Violating mutual exclusion – two tasks in their critical section simultaneously → corrupted shared data.
2. Deadlock – tasks each hold a resource and wait for another's → all blocked forever.
3. Starvation / Lockout – a task is perpetually denied a needed resource.
4. Transient error – timing-dependent intermittent fault (hard to reproduce).
5. Busy waiting – a task wastes CPU cycles continuously polling instead of blocking.
6. Unfairness – resource allocation is not equitable among tasks.

---

Chapter 6 – Mechanisms to Support Concurrency

Two Forms of Concurrency

1. Hardware concurrency – true parallelism on multiprocessor/multi-core hardware.
2. Software concurrency – logical concurrency created by the OS/RTSS via interleaving on (possibly) one CPU.

Non-Determinism – the echo() Example

When two tasks call a shared echo() (read char → store → write) without protection, interleaved execution can lose or duplicate characters. This illustrates why unsynchronized access to shared data produces unpredictable (non-deterministic) results — the motivation for mutual exclusion.

Mutual Exclusion (MUTEX)

Ensures only one task accesses a shared resource / critical section at a time.

Critical Section (CS) structure:

entry section      // request permission to enter
    CRITICAL SECTION   // access shared resource
exit section       // release
remainder section  // non-critical work

MUTEX requirements (a correct solution must satisfy):

1. Mutual exclusion – at most one task in the CS at any time.
2. Progress – if no task is in the CS, a waiting task must be allowed in (no needless blocking).
3. Bounded waiting – a task waits only a finite time (no starvation).
4. No assumptions about relative speed or number of processors.

3 Approaches to Satisfy Mutual Exclusion

1. Semaphore – integer variable with atomic wait()/P() and signal()/V() operations. - Binary semaphore (0/1) → mutex lock. - Counting semaphore → manages N instances of a resource.
2. Monitor – high-level construct encapsulating shared data + procedures; only one task may be active in the monitor at a time (mutual exclusion is automatic). Uses condition variables (wait/signal).
3. Message Passing – tasks synchronize/communicate by send/receive messages (no shared memory needed). Can be synchronous (blocking) or asynchronous (non-blocking).

Concurrent Programming (CP) Constructs

• Fork/Join, cobegin/coend (or PAR), and explicit task/thread declarations mark statements to run concurrently.

Concurrent Programming Languages

Language	Concurrency Construct	Notes
Ada	task, PAR	Rendezvous model for task communication; designed for embedded/real-time.
OCCAM	SEQ, PAR, ALT	Based on CSP; designed for the transputer; channels for message passing.
Java	Thread class / Runnable interface	synchronized, wait(), notify(); monitors built in.
Concurrent C-- / BACI	cobegin … coend	Used in labs (BACI = Ben-Ari Concurrent Interpreter); semaphores.

Run-Time Support System (RTSS)

• The layer beneath a concurrent program that manages tasks: creation, scheduling, context switching, synchronization.
• Implements time-slicing – divides CPU time into small slices allocated to tasks in turn.
• Context switch – saving one task's state (registers, PC, stack) and restoring another's.

Two Ways to Achieve Concurrency in Real-Time Systems

1. Concurrent language (Ada/OCCAM/Java) – concurrency is built into the language; RTSS provided by the language runtime.
2. Sequential language + RTOS – e.g., C + µC/OS-II; the RTOS kernel provides tasking. Tasks created via calls like: c OSTaskCreate(TaskFunc, &data, &TaskStk[STKSIZE], priority);

---

Chapter 7 – Concurrent Programming in Practice (BACI/jBACI)

• jBACI – Java-based IDE/simulator for the BACI (Ben-Ari Concurrent Interpreter) system, used to write, compile, and visualize concurrent programs.
• Supports Concurrent C-- and Concurrent Pascal dialects.
• Key constructs practiced in labs:
• cobegin p1(); p2(); coend; – run procedures concurrently.
• Semaphores: semaphore s;, initialsem(s, val), p(s) (wait), v(s) (signal).
• mutex for binary locks.
• Purpose: observe non-determinism, demonstrate race conditions, and verify that semaphores/monitors enforce mutual exclusion. Different runs of the same program can give different interleavings/outputs.

---

Chapter 8 – Real-Time Operating Systems (RTOS)

Definition

An RTOS is an OS that guarantees tasks complete within deterministic, predictable time bounds — correctness depends on both logical result and timing. It is an abstraction layer between application software and hardware.

RTOS vs. Generic (General-Purpose) OS

Feature	RTOS	Generic OS
Design goal	Predictability / determinism	Throughput & fairness (average performance)
Scheduling	Priority-based, preemptive	Time-sharing / fair-share
Latency	Bounded, guaranteed	Variable, best-effort
Kernel	Small, deterministic	Large, feature-rich
Timing	Deadlines are critical	Deadlines not guaranteed
Example	µC/OS-II, VxWorks, FreeRTOS	Windows, Linux, macOS

RTOS Structure

• Executive + Kernel model:
• Kernel – the core: task scheduling, dispatch, context switching, inter-task synchronization/communication.
• Executive – kernel + additional services (memory management, I/O, timers, device drivers).

RTOS Services

• Task management (create/delete/suspend/resume)
• Scheduling & dispatching (priority-based preemptive)
• Inter-task communication & synchronization (semaphores, mailboxes, message queues)
• Time management (delays, timeouts, system tick)
• Memory management
• Interrupt handling

µC/OS-II (Micrium)

• Portable, ROMable, scalable, preemptive, multitasking real-time kernel for microprocessors/microcontrollers.
• Priority-based preemptive scheduling; each task has a unique priority.
• Deterministic (execution times are known/bounded).
• Written mostly in C (small portion in assembly for portability).
• Supports up to a fixed number of tasks, each with its own stack.
• Common API: OSInit(), OSStart(), OSTaskCreate(), OSTimeDly(), OSSemPend(), OSSemPost().

---

Chapter 9 – Real-Time Scheduling & Schedulability Analysis

Part 1 – Scheduling Fundamentals

Scheduling = deciding the order and timing in which tasks use the processor so that timing constraints (deadlines) are met.

Goals of Real-Time (ERT) scheduling: meet all deadlines, maximize processor utilization, ensure predictability, minimize response time.

Task Model Parameters

Symbol	Meaning
T	Period (time between successive releases of a periodic task)
D	(Relative) Deadline — often D = T
C	WCET — Worst-Case Execution Time (compute time)
R	Response time (release → completion)
a / S	Arrival / start time
U	Utilization = C / T

Task Types

• Periodic – released at fixed regular intervals (period T).
• Aperiodic – released irregularly; soft deadlines; random arrival.
• Sporadic – irregular arrival but with a minimum inter-arrival time; typically hard deadlines.

Scheduling Classification

• Pre-run-time (offline / static) – schedule computed before execution (e.g., cyclic executive). Predictable, inflexible.
• Run-time (online / dynamic) – decisions made during execution based on priorities.
• Fixed priority – priority set once and never changes (e.g., RM).
• Dynamic priority – priority changes at run time (e.g., EDF).

Basic Scheduling Policies

1. Cyclic (cyclic executive) – fixed repeating timeline of task slots.
2. Time-slicing (round-robin) – equal CPU quanta rotated among tasks.
3. Priority-based (preemptive) – highest-priority ready task runs; can preempt lower priority.

Rate Monotonic (RM) vs. Earliest Deadline First (EDF)

	Rate Monotonic (RM)	Earliest Deadline First (EDF)
Priority type	Fixed (static)	Dynamic
Priority rule	Shorter period T → higher priority	Earliest absolute deadline → higher priority
Assignment time	Offline (once)	At run time (recomputed)
Utilization bound	≤ n(2^(1/n) − 1) (≈0.693 as n→∞)	≤ 1 (100%)
Optimality	Optimal among fixed-priority schemes	Optimal among all schemes
Overhead	Low	Higher (deadline tracking)
Implementation	Simple, common in RTOS	More complex

---

Part 2 – Schedulability Analysis (SA)

Schedulability Analysis determines whether a given set of tasks can be successfully scheduled (every task completes by its deadline) under a specific algorithm. A Schedulability Test (ST) validates that deadlines are met. (Scheduling with resource dependencies is NP-hard.)

3 Basic Approaches

1. Processor Utilization Analysis
2. Processor Workload Analysis
3. Response Time Analysis

---

1) Processor Utilization Analysis

ST 1 — EDF (Di ≥ Ti, periods integer multiples). Necessary & sufficient:

ST 2 — RM. Necessary & sufficient (sufficient bound, Liu & Layland):

Utilization bound U(n) values:

n	U(n) bound
1	1.000
2	0.828
3	0.779
4	0.756
5	0.743
∞	0.693

Worked example — Mobile Robot (RM):

Task	Tᵢ	Cᵢ	Cumulative U	U(n) bound	Schedulable?
MotorControlKanan	50	12	0.24	1.00	✅
MotorControlKiri	50	12	0.48	0.828	✅
AvoidBehavior	250	20	0.56	0.779	✅
MobileRobot	300	10	0.59	0.756	✅
HRI	500	125	0.84	0.743	❌ (0.84 > 0.743)

• First 4 tasks → U = 0.59 ≤ 0.756 → schedulable.
• Adding HRI (5th) → U = 0.84 > 0.743 → NOT schedulable by the utilization test.
• ⚠️ The utilization test is sufficient but not necessary for RM: failing it doesn't prove infeasibility — use Response Time Analysis for an exact answer.

---

2) Processor Workload Analysis

ST 3 — RM. Task Jᵢ is schedulable iff there exists a time instant t where the cumulative workload fits:

The inequality Wᵢ(t) ≤ t must hold for some t chosen from:

• If Di ≠ Ti, replace Tᵢ with min(Di, Tᵢ).

---

3) Response Time Analysis (RTA)

ST 4 — RM. Task i is schedulable if Rᵢ ≤ Dᵢ, where R is found by the recurrence:

• hp(i) = set of tasks with higher priority than i (shorter periods under RM).
• ⌈ ⌉ = ceiling. The second term = interference from higher-priority tasks.

Iteration algorithm:

• Step 1: first approximation a₀ = Σ Cⱼ (sum of C of task i and all higher-priority tasks).
• Step 2: compute next aₙ₊₁ from the recurrence.
• Step 3: check:
• Cond. 1: aₙ₊₁ ≤ Dᵢ AND aₙ₊₁ ≠ aₙ → repeat Step 2.
• Cond. 2: aₙ₊₁ > Dᵢ → misses deadline (not schedulable).
• Cond. 3: aₙ₊₁ = aₙ → converged; aₙ = response time (WCRT). Schedulable if ≤ D.

Worked example — Mobile Robot task "Subsumption" (T=200, D=200, C=1; higher-priority: MobileRobot C=1/T=50, Motorctrl_left C=20/T=50, Motorctrl_right C=20/T=50):

• Step 1: a₀ = 1 + 20 + 20 + 1 = 42
• Step 2: a₁ = 1 + ⌈42/50⌉·1 + ⌈42/50⌉·20 + ⌈42/50⌉·20 = 1 + 1 + 20 + 20 = 42
• Step 3: a₁ = a₀ = 42 (Cond. 3) → WCRT = 42 ms ≤ D = 200 ms → schedulable ✅

Full mobile-robot timing results (Di = Ti):

Task	Period T	WCET C	Rᵢ	Schedulable (R ≤ D)?
MobileRobot	50	1	1	✅
Motorctrl_left	50	20	21	✅
Motorctrl_right	50	20	41	✅
Subsumption	200	1	42	✅
Avoid	300	17	100	✅
Cruise	300	1	143	✅
Manrobotintf	500	16	200	✅

➡️ Even though the utilization test failed for the full set, RTA proves every task meets its deadline — RTA is exact (necessary & sufficient) while the utilization bound is only sufficient.

Worked example 2 — RTA convergence (task e₃: T=350, C=100, D=350; hp = e₁ T=100/C=40, e₂ T=150/C=40):

• a₀ = 100 + 40 + 40 = 180
• a₁ = 100 + ⌈180/100⌉·40 + ⌈180/150⌉·40 = 100 + 2·40 + 2·40 = 260
• a₂ = 100 + ⌈260/100⌉·40 + ⌈260/150⌉·40 = 100 + 3·40 + 2·40 = 300
• a₃ = 100 + ⌈300/100⌉·40 + ⌈300/150⌉·40 = 100 + 3·40 + 2·40 = 300
• a₃ = a₂ = 300 → WCRT = 300 ms ≤ 350 ms → schedulable ✅

---

Quick Formula Sheet

Concept	Formula
Utilization of one task	Uᵢ = Cᵢ / Tᵢ
Total utilization	U = Σ (Cᵢ / Tᵢ)
EDF bound (nec. & suff.)	U ≤ 1
RM utilization bound (suff.)	U ≤ n(2^(1/n) − 1)
RM bound as n→∞	≈ 0.693
Workload (RM)	Wᵢ(t) = Σₖ Cₖ⌈t/Tₖ⌉, test Wᵢ(t) ≤ t
Response time (RM)	Rᵢˣ⁺¹ = Cᵢ + Σ_{j∈hp(i)} ⌈Rᵢˣ/Tⱼ⌉ Cⱼ
Schedulable (RTA)	Rᵢ ≤ Dᵢ
First approx.	a₀ = Σ Cⱼ (task i + all hp)

Key exam reminders

• RM → shorter period = higher priority; EDF → nearest deadline = higher priority.
• Utilization test is sufficient only for RM (a pass guarantees schedulable; a fail is inconclusive).
• Response Time Analysis is exact (necessary & sufficient) for fixed-priority preemptive scheduling.
• Ceiling ⌈ ⌉ in RTA/workload; floor ⌊ ⌋ in the workload's time-instant set.
• hp(i) = higher-priority tasks only (they interfere with i; lower-priority tasks do not).

---

Notes compiled from Chapters 5–9 lecture slides (Topic 5 Concurrency, Topic 5 Mechanisms, Topic 7 RTOS, Topic 8 RT Scheduling Parts 1 & 2, Processor Utilization & Response Time Analysis). Source folders left unmodified.