Resource Sharing, Deadlocks & Access Control in Real-Time Systems

TAKEAWAYS:

• Shared resources (e.g., printers, sensors, memory) in real-time systems must be accessed without violating timing deadlines, using protocols like Priority Inheritance (PI) or Priority Ceiling (PC).
• Deadlocks occur when tasks hold resources while waiting for others; four necessary conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) must all be present for a deadlock to form.
• Resource access control uses locks (mutexes, semaphores) and protocols (e.g., Stack Resource Policy) to prioritize critical tasks and avoid priority inversion.
• Real-world systems (e.g., Ncell’s network slicing, Khalti’s payment processing, Pathao’s ride dispatch) rely on these mechanisms to guarantee response times under load.
• Performance trade-offs: Strict protocols (e.g., PCP) reduce deadlock risk but may increase blocking time; dynamic priority adjustment (e.g., EDF with resource reservations) balances responsiveness and fairness.
• Exam focus: Be able to identify deadlock scenarios, design protocols for a given system, and compare PI vs. PCP in terms of blocking time and schedulability.

1. Shared Resources in Real-Time Systems

Real-time systems often share hardware resources (CPU cores, memory, I/O devices) and software resources (data structures, files, sensors). Unlike general-purpose OSes, real-time systems must ensure that resource access does not violate timing deadlines. For example:

• A medical infusion pump shares a serial communication port with a patient monitor. If the pump’s task is preempted while holding the port, the monitor’s task (with lower priority) may miss its deadline.
• Ncell’s 5G network slicing dynamically allocates CPU and memory to different slices (e.g., one for voice calls, another for IoT devices). If a slice’s tasks are starved, latency spikes occur.

Types of Shared Resources

Why Resource Sharing is Tricky

• Priority inversion: A low-priority task holds a resource needed by a high-priority task, causing the high-priority task to wait longer than its deadline. Example: In Pathao’s ride dispatch system, a low-priority "update driver location" task holds a lock on the driver_queue while a high-priority "assign ride" task waits. If the low-priority task runs for too long, the ride assignment misses its deadline.
• Unbounded blocking: Without proper protocols, a task can block others indefinitely (e.g., a bank’s loan processing system where a low-priority "audit" task holds a lock on the transaction_log, delaying critical "fraud detection" tasks).

2. Deadlocks: The Four Necessary Conditions

A deadlock occurs when two or more tasks are blocked forever, each waiting for a resource held by another. Coffman et al. identified four necessary conditions for deadlock:

graph LR
    A["Mutual Exclusion"] --> B["Hold-and-Wait"]
    C["No Preemption"] --> D["Circular Wait"]
    B --> D
    A --> C
    C --> A

1. Mutual Exclusion

Only one task can use the resource at a time. Example: A Khalti payment gateway can process one transaction at a time on a shared ledger lock.

2. Hold-and-Wait

A task holds a resource while waiting for another. Example: In Daraz’s order fulfillment system, Task A holds the inventory_lock while waiting for the shipping_lock.

3. No Preemption

Resources cannot be forcibly taken from a task. Example: A traffic light controller cannot preempt a task updating the sensor_data lock mid-execution.

4. Circular Wait

A circular chain of tasks exists where each waits for a resource held by the next. Example:

Task 1 (High Priority) → holds Resource X → waits for Resource Y
Task 2 (Low Priority) → holds Resource Y → waits for Resource X

3. Deadlock Prevention vs. Avoidance vs. Detection

4. Resource Access Protocols

To prevent deadlocks and priority inversion, real-time systems use protocols to control resource access. The two most common are:

A. Priority Inheritance (PI) Protocol

• If a high-priority task (H) is blocked by a low-priority task (L) holding a resource, L inherits H’s priority temporarily.
• Prevents unbounded priority inversion (where L runs for an arbitrarily long time).
• Example: In Ncell’s core network, if a high-priority "emergency call" task is blocked by a low-priority "background update" task holding a router_lock, the update task’s priority is boosted to match the emergency call.

sequenceDiagram
    participant H as High-Priority Task
    participant L as Low-Priority Task
    participant R as Resource
    H->>R: Request (blocked)
    L->>R: Holds Resource
    Note right of L: L inherits H's priority
    L-->>R: Releases Resource
    H->>R: Acquires Resource

Advantages:

• Simple to implement.
• Reduces blocking time compared to no protocol.

Disadvantages:

• Indefinite blocking: If a third task (M) preempts L, L may never release the resource.
• Priority inversion can still occur if M has higher priority than H.

B. Priority Ceiling Protocol (PCP)

• Each resource has a ceiling priority = the highest priority of any task that may use it.
• A task can only run if its priority is ≥ the ceiling of all resources it holds.
• Example: In Khalti’s payment processing, the ledger resource has a ceiling priority of 5 (highest priority task that uses it). A task with priority 3 cannot run while holding the ledger if a priority 5 task requests it.

stateDiagram-v2
    [*] --> Idle
    Idle --> Running: Task priority ≥ ceiling of all held resources
    Running --> Blocked: Task requests resource with higher ceiling
    Blocked --> Running: Higher-priority task releases resource

Advantages:

• Bounds blocking time: A task can block others for at most the execution time of the highest-priority task that might use its resources.
• Prevents circular wait: By enforcing a strict priority order.

Disadvantages:

• Lower CPU utilization: Tasks may be blocked even if resources are free but their ceilings are too high.
• Complexity: Requires static analysis to assign ceilings correctly.

5. Stack Resource Policy (SRP)

• A strict ordering of resources is enforced: tasks must request resources in increasing order of priority.
• Example: In NTC’s fiber optic network management, tasks must request locks in this order:
  1. low_priority_config_lock (priority 1)
  2. medium_priority_route_lock (priority 3)
  3. high_priority_bandwidth_lock (priority 5)

How it works:

• If a task requests resources out of order, it is blocked until it releases all held resources.
• Prevents circular wait by design.

Advantages:

• Deadlock-free if followed strictly.
• Simple to implement.

Disadvantages:

• Reduces flexibility: Tasks must adhere to a fixed order.
• May increase blocking time if a task holds a low-priority resource while waiting for a high-priority one.

6. Real-World Applications

Case Study 1: Khalti’s Payment Processing

• Resource: Shared transaction_log (a critical section in the database).
• Problem: High-priority "fraud detection" tasks are blocked by low-priority "audit" tasks.
• Solution: Priority Ceiling Protocol (PCP) is used:
  • The transaction_log has a ceiling priority of 5 (highest priority task that uses it).
  • If an audit task (priority 2) holds the log, any task with priority ≤ 2 is blocked from running.
• Result: Fraud detection tasks meet their deadlines (≤ 100ms).

Case Study 2: Pathao’s Ride Dispatch System

• Resources: driver_queue, ride_queue, payment_lock.
• Problem: A low-priority "update driver location" task holds driver_queue, blocking high-priority "assign ride" tasks.
• Solution: Priority Inheritance (PI) is used:
  • When an "assign ride" task (priority 4) is blocked, the "update driver location" task (priority 2) inherits priority 4.
  • If another task (priority 3) preempts the update task, the system uses PCP to ensure the update task cannot be starved.

Case Study 3: Ncell’s 5G Network Slicing

• Resources: CPU cores, memory segments, network buffers.
• Problem: Different slices (e.g., IoT, voice calls) compete for resources, risking deadline misses.
• Solution: Stack Resource Policy (SRP) with dynamic priority adjustment:
  • Slices request resources in a predefined order (e.g., voice > IoT > background).
  • If a slice misses a deadline, its priority is temporarily boosted (like EDF with resource reservations).

7. Performance Analysis: Blocking Time and Schedulability

The blocking time (B_i) is the maximum time a task can be delayed by lower-priority tasks holding resources. It affects schedulability tests (e.g., Rate-Monotonic Analysis).

Worked Example: Schedulability with PCP Consider three tasks in a bank’s loan processing system:

• Task 1: C=10ms, T=50ms, priority 3 (high).
• Task 2: C=20ms, T=100ms, priority 2 (medium).
• Task 3: C=30ms, T=200ms, priority 1 (low).

Resources:

• database_lock (ceiling priority = 3, since Task 1 uses it).
• audit_log (ceiling priority = 2).

Scenario: Task 3 holds audit_log and requests database_lock. Task 1 requests database_lock but is blocked because its priority (3) is not ≥ the ceiling of audit_log (2). However, under PCP, Task 3 cannot run while holding audit_log if a higher-priority task (Task 1 or 2) is ready. Thus, Task 3 releases audit_log before requesting database_lock.

Blocking Time:

• For Task 1: B_1 = C_2 = 20ms (if Task 2 holds a resource Task 1 needs).
• For Task 2: B_2 = C_3 = 30ms (if Task 3 holds a resource Task 2 needs).

Schedulability Test (Rate-Monotonic): The utilization bound for n tasks is U ≤ n(2^(1/n) - 1). For 3 tasks: U ≤ 3(2^(1/3) - 1) ≈ 0.78. Total utilization: (10/50) + (20/100) + (30/200) = 0.2 + 0.2 + 0.15 = 0.55 ≤ 0.78. System is schedulable under PCP.

8. Real-Time Memory Management and Resources

Real-time systems often use memory protection to isolate tasks and prevent interference. Key mechanisms:

• Memory Partitioning: Each task gets a fixed-size memory partition (e.g., freertos).
• Shared Memory with Locks: Critical sections are protected by mutexes or semaphores.
• Memory-Mapped I/O: Devices are accessed via memory addresses (e.g., Raspberry Pi’s GPIO).

Example: In NTC’s fiber optic monitoring, each monitoring task runs in a separate memory partition to prevent one task’s crash from affecting others.

9. Exam Tip: How to Score Full Marks

1. Define Key Terms Clearly:

   • "Deadlock occurs when four conditions (mutual exclusion, hold-and-wait, no preemption, circular wait) hold simultaneously."
   • "Priority inversion is when a low-priority task delays a high-priority task by holding a resource."

2. Compare Protocols in a Table: Use a Markdown table to contrast PI vs. PCP vs. SRP (blocking time, deadlock prevention, complexity).

3. Draw a Scenario: For deadlock detection, sketch a wait-for graph (using Mermaid) and label the circular wait.

4. Worked Examples:

   • Given a set of tasks and resources, identify if a deadlock exists and propose a protocol (PI/PCP/SRP).
   • Calculate blocking time for a task under PCP.

5. Real-World Tie-Ins:

   • Relate Khalti’s payment system to PCP or Pathao’s dispatch to PI.
   • Discuss Ncell’s network slicing as an example of resource partitioning.

6. Common Pitfalls:

   • Forgetting the fourth condition (circular wait) in deadlock definitions.
   • Assuming PI prevents all priority inversion (it only reduces it).
   • Ignoring ceiling priorities in PCP calculations.

10. Summary Checklist

Before the exam, ensure you can:

• Explain the four conditions for deadlock and how to break them.
• Compare PI vs. PCP vs. SRP in terms of blocking time and deadlock prevention.
• Calculate blocking time for a given task set under PCP.
• Draw a wait-for graph and identify deadlocks.
• Relate real-world systems (Khalti, Pathao, Ncell) to resource access protocols.
• Discuss trade-offs between prevention, avoidance, and detection.