Real-Time Synchronization

Question 1

What is a “resource”?

Answer 1

A resource is any software structure that can be used by a process to advance its execution. Ex. Data structure, set of variables, main memory area, file.

Question 2

What is a “shared resource”?

Answer 2

It is a resource that can be used by more than one tasks.

Question 3

What is a “critical session”?

Answer 3

It is the part of the code of a job that accesses a shared resource. (slides definition)

or

It is a piece of code executed under mutual exclusion constraints. (book definition)

Question 4

What does “mutual exclusion” mean?

Answer 4

It is the fact that access to a shared resource is only given to one job at a time.

Question 5

What is “synchronization”?

Answer 5

Synchronization is any constraint that imposes an order to the operations carried out by two or more concurrent jobs.

Question 6

What is the difference between “mutual exclusion” and “synchronization”?

Answer 6

Mutual exclusion focuses on ensuring consistency of data, but does not ensure that all jobs will eventually access the resource and does not ensure any order.

Synchronization focuses on ensuring order of “events”, but is not limited to share resources (ex. precedence constrains)

Question 7

In a system without synchronization strategy and several preemptive tasks that share a resource. Under which conditions can all tasks access the same resource at the same time without compromising consistency?

Answer 7

When all tasks perform only read operations.

Question 8

When mutual exclusion is needed, which mechanism can be used to implement it? Explain how it works.

Answer 8

OS constructs that can be accessed in atomic operations. For example, semaphores.
Semaphores are composed by three basic operations:
1. init() - initializes the semaphore
2. wait() - request semaphore. If granted, then all other jobs requesting same semaphore will be blocked
3. signal() - release semaphore. Whenever it is called, it triggers blocked job with highest priority.

Question 9

When a task is said “blocked”?

Answer 9

When a task is waiting for an exclusive resource, a task is said to be blocked on that resource.

Question 10

Explain the phenomenon “priority inversion”. Give an example.

Answer 10

Priority inversion occurs when a higher priority task is being unnecessary delayed by lower priority tasks.
Supposed a system running three tasks (T1, T2, T3). The priority of the tasks are equal to their number and as lower the number is, higher is the priority. T1 and T3 share an resource (R1). T3 starts to execute and gets the access to the shared resource. After a while, it is preempted by T1. T1 executes until it needs access to the shared resource R1 (simple blocking). Then T3 continues to execute, but it is preempted by T2 (higher priority than T3) and starts to execute delaying task T1 execution unnecessarily (priority inversion). After T2 completes its execution, T3 runs until it frees R1. From this point, T1 gets access to R1 and is able to continue its execution.

Question 11

What is a “chained block”?

Answer 11

Consider tasks T1, T2 and T3 with decreasing priorities that share two semaphores Sa and Sb. Suppose that T1 needs sequentially access to Sa and Sb, T2 accesses Sb and T3 access Sa. Also suppose that T3 locks Sa and it is preempted by T2 within its critical section. Similarly, T2 locks Sb and it is preempted by T1 within its critical section. In this situation, when attempting to use its resources, T1 is blocked for the duration of two critical sections, once wait for T3 to release Sa and then to wait for T2 to release Sb.

Question 12

What is the worst case of the chained block?

Answer 12

If T1 (highest priority task on the system) accesses n distinct semaphores that have been locked by n lower priority tasks, T1 will be blocked for the duration of n critical sections.

Question 13

What is “deadlock”? Give an example.

Answer 13

Deadlock is a situation in which two or more competing actions are each waiting for the other to finish, and thus neither ever does.

Consider two tasks (T1 and T2) that use two semaphores (Sa and Sb) in a nested fashion but in reverse order. Now suppose that, at time t1, Task 2 (T2) locks semaphore Sb and enters its critical section. At time t2, T1 preempts T2 before it can lock Sa. At time t3, T1 locks Sa, which is free, but then is blocked on Sb at time t4. At this time, T2 resumes and continues the execution. At time t5 a deadlock occurs, when T2 attempts to lock Sa.

Question 14

How the “Priority Inheritance Protocol” works?

Answer 14

When a task Ti blocks one or more higher-priority tasks, it temporarily assumes (inherits) the highest priority of the blocked tasks. This prevents medium-priority tasks from preempting Ti and prolonging the blocking duration experienced by the higher-priority tasks.

Question 15

Which problems are solved by the PIP?

Answer 15

Priority inversion

Question 16

Which problems are not solved by the “Priority Inheritance Protocol”?

Answer 16

Chained blocking and deadlock.

Question 17

Which protocol solves chained blocking and deadlock problems?

Answer 17

Priority Ceiling Protocol (PCP)

Question 18

How does PCP (“Priority Inheritance Protocol”) work?

Answer 18

Each semaphore has a static priority ceiling value defined as:
- maximum priority of all tasks that may use it:
ceil(S) = highest priority of all tasks that will request S
- calculated offline
Each task has an assigned static priority (may change at run-time due to priority inheritance).
Same run-time mechanism as PIP but if a task i request semaphore S the request is granted if:
- S not already allocated to some other task
AND
- priority of task i is higher than priority ceilings of semaphores currently locked by tasks other than task i at that time.

otherwise task i is blocked by task j that holds semaphore with highest ceiling. Task j executes with priority of task i.

Question 19

What is the schedulability test works for PCP?

Answer 19

Response time analysis + duration of the longest critical session (Bi), since basic algorithm assumptions are violated.
Ri = Ci + Bi + sum { ceiling[Ri/Tj] * Cj , for all j in hp(i)}

Question 20

What is the maximum blocking time in PCP?

Answer 20

It is the duration of the longest critical session Bi.

Question 21

What is the difference between IPCP and PCP?

Answer 21

The job priority of task on PCP is raised when higher priority blocked, while on IPCP it is raised as soon as it locks the semaphore.

Question 22

Which are the disadvantages of IPCP?

Answer 22

Priorities may be raised unnecessarily and lower priority tasks delay higher priority tasks without blocking as well.

Question 23

How does the Stack Resource Policy (SRP) extends PCP?

Answer 23

It extends in three essential points:

1. It allows the use of multi-unit resources;
2. It supports dynamic priority scheduling;
3. It allows the sharing of runtime stack-based resource.

Question 24

What is the essential difference between Stack Resource Policy and Priority Ceiling Protocol from the scheduling point of view?

Answer 24

The main difference is on the time at which a task is blocked. On SRP a task is blocked at the time it attempts to preempt, while on PCP the block occurs at the time it makes its first resource request. This early blocking slightly reduces concurrency but saves unnecessary context switches, simplifies the implementation of the protocol, and allows the sharing of runtime stack resources.