Overview

Resources are shared memory, printers, semaphore, mutex and so on
How to allocate and control shared resources between jobs?

Assumptions on resources and resource usage

System contains only 1 processor
Different types of resources that are serially reusable and referred as R1, R2, Rp
Each resouce may have multiple instances 1<= i <= p
Serially resuable resources are granted on a non premptive based and used in a mutually exclusive way
- so while a serial resource is being used by a job another job cannot use
Semaphore is a type of resource
- binary – can lock only 1 resource at a time
- counting – has multiple units so can lock multiple resource instances at a time
If resources are infinite then it has no impact on timing behavior while in case of finite resources there will be impact on timing

How to apply mutual exclusion and critical section on shared resource?

mutual exclusion
- use lock based concurrency control
- take lock when start to use resource and release lock when ending use of resource
- notations
  - Lock = L(Ri, ni) -> Lock (Resource1, lock 2 units)
    - if only 1 unit of resource then L(Ri)
  - Unlock = U(Ri, ni) -> Unlock (Resource1, unlock 2 units)
    - if only 1 unit of resource then U(Ri)
critical section
- segment of a job which starts with taking the lock on resource and ends by releasing lock on resource
- when a critical section is not nested inside another critical section then it is called outermost critical section
- with critical section one can mention the execution time of the critical section in which case it has to be ensured that critical section complete within the execution time if not then it will get preempted

Resource conflicts and blocking

if a job is requesting a resource which is already being used by another job then it is called resource conflict/blocking
a scheduler can deny a resource even if free in cases when it can see potential of an unexpected behavior
Example below shows how resource contention can delay execution of high priority jobs if resource is being used by lower priority job
- Note
  - (6, 14] = period, deadline
  - [R; 2] = 2 is critical section execution time
  - Black blocks show critical section on resource is executing
  - jobs are prioritized based on earliest deadline first so J1 has highest priority then J2 and J3

Impacts of Resource conflicts or blocking

Priority Inversion

higher priority task needs to wait for lower priority job due to resource confliect
above is an example of priority inversion problem
another example below

Uncontrolled priority inversion

Priority inversion can create timing anomalies like highest priority J1 misses its deadline

Deadlock

Deadlock (or deadly embrace) is when 2 jobs are unknowingly waiting on each other for resources on each other
Example
- 2 jobs require resource X and Y
- Say J1 holds X and request Y while J2 holds Y and requests X
To avoid deadlocks
- acquire all resources before proceeding
- acquire the resource in the same order and release the resource in reverse order
- kernels allows to give a timeout when acquiring a semaphore
  - return error code when timeout occurs so that job knows that semaphore was not acquired

Resource access control protocol

its a set of rules when and under what condition resources are granted and how jobs requiring resources are scheduled
Some well known resource access control protocols

Non premptive critical protocol

when a job takes a resource it is not prempted even if it is a lower priority job
uncontrolled priority inversion can never occur. in example: below waiting time for higher priority J1 is execution time of critical section of lower priority J3
in this case block time is

Basic Priority Inheritance Protocol

Basic Priority Ceiling Protocol

extends priority inheritance protocol
helps solve priority inversion problem
sets a priority (ceiling) to a resource based on the highest priority of jobs that are going to use it
makes 2 assumptions
- assigned priorities of jobs are fixed
- resources required by all jobs are known apriori

rules for this protocol (see example below to understand the rules)
- scheduling rules
  - …
- allocation rule
  - if resource is held by another job then the request for resource fails
  - if resource is free
    - priority of job J requesting resource > current priority ceiling, resource is allocated
    - OR job J is holding another resource whose priority ceiling is equal to current priority ceiling
- priority inheritance rule
  - when J becomes blocked, the job Ji which blocks J inherits the current priority of J

Black resource priority ceiling as 2 as highest priority of jobs J2, J4, J5
Shaded resource priority ceiling as 1 as highest priority of jobs J1, J4
At 0 since no job require resources the current system priority ceiling is set to 6
J5 is allocated Black since J5 priority is higher than current priority ceiling of 6
- And current priority ceiling is set to 2 equal to priority ceiling of resource Black
At time 3, J4 request for shaded resource is denied because
- current priority ceiling of system is 2 and J4 priority is lower
- and J4 is NOT holding another resource who priority is equaltme 5 to priority ceiling of the system
At time 3, J5 inherits J4 priority as J4 is blocked
At time 4, J3 is released since it has higher priority to J5 it executes
At time 5, J2 is released since it has higher priority to J3 it executes
At time 6, J2 requests for Black but since it is taken by J5, J5 inherits priority of J2 and J2 is blocked
At time 7, J1 is released since it has higher priority J5 it executes and J5 is preempted
At time 8, J1 requests for Shaded resource which is free and is allocated to J1. And current priority ceiling become 1
At time 9, J1 releases Shaded resources hence current priority ceiling is set to 2 which is priority ceiling of Black
At time 11, J5 releases Black which is then taken by J2 hence current priority ceiling is set to 2
At time 13, J2 completes execution hence J3 executes
At time 14, J3 completes execution hence J4 executes.
At time 14, J4 gets Shaded since Shaded is free and system priority ceiling is 6 (since all resources are free) hence allocated to J4.
- And then system priority ceiling is set to 1 which is priority ceiling of Shaded
At time 16, J4 gets allocated Black since it is holding Shaded resource who priority ceiling is equal to system priority ceiling of 1

Blocking and duration of blocking

blocking means higher priority task is blocked due to lower priority task holding the resource
to avoid deadlocks we block jobs
jobs need to at least wait for 1 critical section duration
to find blocking time of job, see example below

Example below with different types of blocking

Difference between priority inheritance vs priority ceiling

priority inheritance is greedy while priority ceiling is not since it is based on specific allocation rules
Blocking of jobs and duration of blocking
- in priority inheritance protocol blocking could happen multiple times
- in priority ceiling protocol blocking happens only once for duration of 1 critical section
  - there cannot transitive blocking (job1 blocked by job2 and job2 blocked by job 3) under the priority ceiling protocol
priority inheritance rules are the same between the 2
3 types of blocking can occur

Deadlock avoidance with priority ceiling protocol

simple is ordered resource technique
with priority ceiling deadlock can never occur. see example below

Resource priority ceiling
- Black = 2 since required by J2, J3
- Shaded = 2 since required by J2, J3
- Dotted = 1 since required by J1
At time 0.5, J3 starts and shaded resource is free and is allocated
J2 starts it preempts J3
J2 asks for black but since J3 is holding the resource and current system priority is 2 it does not get resource
- This ensures no deadlock occurrs between J2, J3

Fixed priority scheduling and priority ceiling protocol

Priority ceiling protocol is an excellent protocol in case of fixed priority scheduling so when tasks have fixed priority and there are periodic tasks

know the apriori duration of critical section in each task
possible to analyze potential resource contentions statically
the effect of resource contention (j2 is blocked due to j1 using resource) can be considered when testing the schedulability of tasks
to calculate execution time of a function we need to consider 2 factors
- blocking time – see example below
- context switching time
  - what is context switching time
    - when switching from T1 to T2 then context of T1 needs to be saved
    - and T2 context needs to be retrieved
    - context switching time = context saving time + context retrieval time
  - number of context switches
    - when task is independent then it has 2 context switches i.e. at start and end
    - when task is dependant on resource then tasks requires 4 context switches
      - such tasks can be blocked be blocked only

Example below we can see that apriori we can know T2 will miss its deadline and we can calculate the blocking time of tasks due to resource contention

where -> Tn = (release time, period, execution time;[resource, critical section time])

T4 is released before T1
T2 even if has deadline of 2.2 it is prempted by higher priority T1
T3 gets a chance to execute only when other priority tasks complete execution

Dynamic priority scheduling and priority ceiling protocol

in dynamic priority system priority of periodic tasks changes but the resource required by each task is constant
- For example: in case of EDF schedule there are 2 tasks T1 = (2,0.9) and T2=(5,2.3) and T1 requires X resource
  - Period 0 to 4 – T1 is priority 1 and T2 is priority 2 so priority ceiling of X is 1
  - Period 4 to 5 – T2 is priority 1 and T1 is priority 2 so priority ceiling of X becomes 2
to implement the priority ceiling protocol in a dynamic priority system
- when a job is released its priority is assigned relative to all other jobs in a queue based on dynamic priority algorithm
- and priority ceiling of all the resources are updated based on new priorities and ceiling of the system is updated based on new priority ceilings of the resources

Example

T1 = (0.5, 2.0, 0.2; [Black, 0.2]), T2 = (0, 3.0, 1.5; [Shaded, 0.7]), T3 = (0, 5.0,1.2;[Black, 1.0 [Shaded, 0.4]])
- where -> Tn = (release time, deadline, execution time;[resource, critical section time])
At 0 – T2 and T3 are released with priority 1, 2 respectively. Hence priority ceiling of Black is 2 while of Shaded is 1
At 0.3 – T2 takes Shaded so ceiling of system is set to 1
At 0.5 – T1 is released having priority 1 and priority of T1, T2, T3 becomes 1,2,3 respectively. Hence Black priority becomes 1 and Shaded priority become 2. So ceiling of system is set to 2
- Since T1 has higher priority to ceiling of system hence it takses Black, sets ceiling of system as 1 and starts execution
and so on

Note:

In dynamic priority system the blocking time is higher than fixed priority system
Worst Blocking time = execution time of longest critical section of all tasks other than T1

Stack Sharing Priority Ceiling Protocol

A resource in the system is the Run Time Stack. And we have assumed that each job has its own runtime stack
But in systems where # of jobs are high then jobs should share the same runtime stack to reduce the memory demand
Space in shared stacks is allocated to jobs contiguously in LIFO manner
- an executing job has space at top of the stack
- space is freed when a job completes
- in case of premption the prempting job j2 gets space above the prempted job j1. and j1 can execute only when jobs holding stack space above it have completed execution
In such cases of shared runtime stack, basic priority ceiling protocol could lead deadlocks like in example below

The Stack Sharing Priority ceiling protocol defines a set of rules that ensure such deadlocks do not happen since based on the rules below no job is blocked once execution begins due to resource not being available

The rules are as follows

Current ceiling of system (∏t) = highest priority ceiling of all the resources that are in use
Non existing priority level (⋂) = priority lower than lowest priority of all jobs
Rules
- Update of current ceiling: when all resources are free the system ceiling is (⋂). And (∏t) is updated whenever a resource is allocated or freed
- Scheduling rule: after a job is released
  - it is blocked if its priority < current ceiling of system (∏t).
  - if it is NOT blocked then it is scheduled as per assigned priorities
- Allocation rule: whenever a job requests a resource it is allocated a resource

Example below of based on rules above and it demonstrates how deadlocks are avoided in case of stack sharing

Black resource priority ceiling is 2 since is used by J2, J4, J5
Shaded resource priority ceiling is 1 since is used by J1, J4
J5 is released it starts execution and takes Black resource, the current ceiling of system is 2 (Black priority ceiling is 2)
J4, J3, J2 are released at 2, 4, 4.8 respectively. But since their priority 4,3,2 are <= current ceiling of system i.e. 2, they are not started
When J1 is released its priority 1 > current ceiling of system 2 hence it starts execution

Note:

Blocking time suffered by every job is same for stack based nad basic priority ceiling protocol
Context switching time is lower in stack based compared to basic priority ceiling protocol. This because
- no job is ever blocked once it starts execution
- no job ever suffers more than 2 context switches

Ceiling Priority Protocol

The job holding any resource executes at the highest priority of all jobs requiring the resource
Rules
- Scheduling rule
  - jobs executes at its assigned priority when it does not hold any resource. in case of jobs with same priority then FIFO basis is used
  - priority of job holding a resource is equal to highest priority ceiling of all resources held by the job
- Allocation rule: whenever a job requests a resource it is allocated a resource

Premption Ceiling Protocol

Premption level of a job means its potential to prempt other jobs
- It is derived from a combination of priority and release time
- In case of dynamic priority system like EDF derived based on deadline where job with shorter deadline have higher premption level
A job J1 has higher premption level than J2 if
- J1 can prempt J2
- J2 can never prempt J1 during execution
The premption ceiling protocol is
- each resource is assigned premption ceiling as highest preemption level amogst all jobs that use that resource
- each task is assigned a preemption level, based on its static or dynamic priority (for example, shorter deadlines imply higher preemption levels in EDF systems)
- So at any time t, the system’s preemption ceiling is
  - the highest ceiling of all resources currently in use
  - a task can only execute or be granted a new resource if its preemption level is higher than the system ceiling
Rules of Basic Preemption Ceiling Protocol
- Scheduling rule
  - After a task is released, it cannot start executing until its preemption level is higher than both the current system ceiling and the preemption level of the task currently executing
- Allocation rule
  - If a resource is free and the task’s preemption level is higher than the system ceiling, the resource is allocated to it
  - If the resource is free but the task’s preemption level is not higher than the system ceiling, the resource is granted only if that task already holds resource(s) with the current ceiling. Otherwise, the task is blocked
- Priority inheritance rule
  - when J becomes blocked, the job Ji which blocks J inherits the current priority of J
Rules of Stack based Preemption Ceiling Protocol
- Current ceiling of system (∏t) = highest priority ceiling of all the resources that are in use
- Non existing priority level (⋂) = priority lower than lowest priority of all jobs
- Rules
  - Update of current ceiling: when all resources are free the system ceiling is (⋂). And (∏t) is updated whenever a resource is allocated or freed
  - Scheduling rule: after a job is released
    - it is blocked if its priority < current ceiling of system (∏t).
    - if it is NOT blocked then it is scheduled as per assigned priorities
  - Allocation rule: whenever a job requests a resource it is allocated a resource
  - Inheritance rule: when a job j2 is blocked from starting, the blocking job j3 inherits the highest priority of all the blocked jobs

Controlling access to multiple unit resources

When there are multiple units of resources the there are changes in protocol as follows

Priority ceiling protocol

3 resources x, y, z each with 2,3,1 units respectively
Each job requires different units of each resource as given in figure below
How is priority ceiling calculated implies
- (pie (*, 0)) = if a resource say x has 0 resources available then priority ceiling = highest priority which will get blocked if 0 resources available. In example below it will be J1 highest priority job getting blocked
- pie (*, 1)) = if a resource say y has 1 resources available then priority ceiling = highest priority which will get blocked if 1 resources available. In example below it will be J2 highest priority job getting blocked (since it requires 2 resources)
The system priority ceiling is highest of the priority ceiling of x,y,z resources
Premption ceiling protocol follows the same approach

Rules are modified as follows

Scheduling rule
Allocation rule
- When job requests K units and less then K units available then Job becomes blocked
- When job request K units and K or more units available
  - if job priority is higher than current system priority ceiling then resource is allocated

Priority inheritance rule
- when there is 1 unit of resource and job J is blocked by lower priority job then lower priority job inherits priority of job J
- when more than one lower priority job is responsible for blocking higher priority job J. For example: J2 requies 2 while J3, J5 have taken 1 resource each
  - the highest priority out of the blocking job (in example: J3) then it inherits priority of Job J (in example: J2)

At time

0 = J5 is released starts executing
0.5 = System ceiling is 0 so J5 takes Black
1.5 = J4 takes Black
- At this point since 2 units of Black are taken then system priority ceiling is set as per available Black units i.e. 3 = 2 (see table)
3 =
- J2 is denied Shaded since its priority is not higher than current ceiling of system
- J4 takes Black since …?

Controlling concurrent access to Data objects

Coming soon…

scientia-blue

Real time systems – Resource Allocation