What is priority inversion?

Priority inversion is a scheduling problem in real-time operating systems where a high-priority task is blocked by a lower-priority task that holds a necessary resource. This occurs when a medium-priority task preempts a low-priority task, which in turn blocks a high-priority task.

Scenario example:

1. Task H (high priority) attempts to access resource R and gets blocked because R is busy.
2. Task L (low priority) holds resource R.
3. Task M (medium priority) becomes ready and preempts L.
4. Thus, H, despite its high priority, has to wait until M finishes, and then L resumes and releases R.

Solutions:

• Priority Inheritance Protocol: The task holding a resource needed by a higher-priority task temporarily inherits the higher priority during the resource hold.
• Priority Ceiling Protocol: Each resource is assigned a ceiling priority equal to the highest priority of any task that may use it. A task can access a resource only if its priority is higher than the ceiling of any resource currently held by other tasks, or if it already holds that resource.

// Example of simplified demonstration without real scheduling mechanisms
import Foundation

let resource = NSCondition()
var resourceInUse = false

func lowPriorityTask() {
    print("Low Priority: Trying to acquire resource...")
    resource.lock()
    while resourceInUse {
        resource.wait()
    }
    resourceInUse = true
    print("Low Priority: Acquired resource.")

    // Simulate work
    Thread.sleep(forTimeInterval: 2)

    resourceInUse = false
    print("Low Priority: Released resource.")
    resource.signal()
    resource.unlock()
}

func mediumPriorityTask() {
    print("Medium Priority: Running...")
    // Simulate work that can preempt low-priority task
    Thread.sleep(forTimeInterval: 3)
    print("Medium Priority: Finished.")
}

func highPriorityTask() {
    print("High Priority: Trying to acquire resource...")
    resource.lock()
    while resourceInUse {
        print("High Priority: Waiting for resource...")
        resource.wait()
    }
    resourceInUse = true
    print("High Priority: Acquired resource.")

    // Simulate work
    Thread.sleep(forTimeInterval: 1)

    resourceInUse = false
    print("High Priority: Released resource.")
    resource.signal()
    resource.unlock()
}

let lowQ = DispatchQueue(label: "com.example.low", qos: .utility) // Low priority
let mediumQ = DispatchQueue(label: "com.example.medium", qos: .userInitiated) // Medium priority
let highQ = DispatchQueue(label: "com.example.high", qos: .userInteractive) // High priority

// Launch tasks in an order that can lead to inversion (first low, then high, then medium)
lowQ.async { lowPriorityTask() }
Thread.sleep(forTimeInterval: 0.1) // Allow low task to start
highQ.async { highPriorityTask() }
Thread.sleep(forTimeInterval: 0.2) // Allow high task to block
mediumQ.async { mediumPriorityTask() }

// In a real OS, the scheduler manages priorities,
// here it is just a demonstration of lock/wait principle.

RunLoop.main.run(until: Date(timeIntervalSinceNow: 7))