Resource and Resource Access Control (only on Fixed Priority System)

Mutually exclusive resource sharing

위의 경우 A Resource에 두 Task가 동시에 접근이 가능한 경우인데, 이 경우 A의 값이 정상적으로 업데이트 되지 못한다. 

아래의 경우는 Mutually Exclusive가 적용된 케이스로 A가 최종적으로 2로 업데이트 되게 된다.

Unbounded Priority Inversion

1. 우선순위 반전 개념
   • 높은 우선순위 작업이 낮은 우선순위 작업에 의해 지연될 때 발생
   • 즉, 높은 우선순위 작업이 낮은 우선순위 작업에 막혀서 실행되지 못하는 현상
2. 반전의 발생 조건
   • 주로 동기화(Synchronization) 중 발생
   • 상호 배제(mutual exclusion)때문에 Job간에 지연 발생 가능

 

가령 낮은 우선순위 작업이 자원을 갖고 있는 상태에서, 높은 우선순위 작업은 이 자원을 기다리고, 동시에 중간 우선순위 작업들이 돌아가면서 실행될 경우, 높은 우선순위 작업은 끝없이 기다리는 상황이 발생할 수 있다. 

 

Basic Priority Inheritance Protocol

1. 규칙1 (우선순위 상속)
   • 낮은 우선순위의 Task가 Critical Section에서 높은 우선순위의 Task를 Blocking하면, 낮은 우선순위 Task는 Blocking된 Task들 중 가장 높은 우선순위를 상속받음
   • 이렇게 하면 높은 우선순위 Task가 최대한 빠르게 진행될 수 있도록 낮은 우선순위 Task가 더 빨리 스케줄됨
2. 규칙2 (우선순위 복귀)
   • Critical Section을 벗어나면, 해당 Task는 자신의 원래 우선순위로 복귀함 
3. 규칙3 (Transitivity - 전이성)
   • 우선 순위 상속은 전이적인데, A(높은 우선순위)가 B(중간 우선순위)에게 막히고 B가 C(낮은 우선순위)에게 막힐 경우, C는 A의 우선순위를 상속받는다.

 

Chained Blocking under PIP

PIP 하에서의 차단 유형

1. 직접 차단(Direct Blocking)

• 높은 우선순위 작업이 낮은 우선순위 작업과 세마포어를 공유할 때 발생
• 각 낮은 우선순위 작업이 한 번씩 높은 우선순위 작업을 차단할 수 있음
• 이 차단의 지속시간은 해당 임계 구역 중 가장 긴 구간

 

2. 간접 차단(Indirect Blocking)

• 높은 우선순위와 낮은 우선순위 작업이 세마포어를 공유하지만, 다른 작업을 통해 간접적으로 차단되는 경우
• 낮은 우선순위 작업이 높은 우선순위 작업의 우선순위를 상속받아 스케줄링 됨 -> 이로 인해 간접적으로 다른 높은 우선순위 작업이 지연됨

3. 총 차단 시간 = 직접 차단 시간 + 간접 차단 시간 

 

Blocking Time under PIP

$$b_i(rc)=\sum_{j=i+1}^{n}cs_j \cdot rc_{i,j}$$

• $b_i(rc)$: 우선순위가 $i$인 작업이 받을 수 있는 최대 차단 시간
• $cs_j$: 우선순위 $j$ 작업의 가장 바깥 Critical Section의 실행 시간
• $rc_{i,j}$: 차단 여부를 나타내는 이진 변수

$$rc_{i,j}=\begin{Bmatrix}
1 \,\,\,task_j\,\,\, preempt\,\,\, task_i \\ 0
\end{Bmatrix}$$

먼저 가장 상단에 있는 세마포어 정보를 가지고 왼쪽 아래에 있는 그래프를 그린다.

오른쪽 아래 표는 직접 차단, 간접 차단 여부를 표로 나타낸 것인데, 가로 축이 Block을 하는 쪽이고, 새로 축이 대상이다.

직접 차단은 판단하기 쉬운데, 공유 세마포어가 존재하면 Y, 없으면 N이다.

간접 차단의 경우, 특정 자원을 획득하여 우선순위가 상대적으로 높아졌을 경우 블럭킹하는 경우를 마킹하면 된다. 

가장 오른쪽의 총 차단 시간의 경우에는 직접 차단 + 간접차단 값을 더하면 되는데, 만약 같은 Task에 의해서 직간접 차단인 경우에는 1회만 더한다. 

 

Deadlock Under PIP

만약에 두 Task가 두 개의 자원을 공유한다고 할 때, PIP 환경 하에서는 위와 같이 Deadlock(교착상태)에 빠질 수 있다. 

 

 

PCP - Priority Ceiling Protocol

1. Priority Ceiling 
   • 각 세마포어에는 Priority Ceiling이 할당됨
   • 이는 해당 세마포어를 사용할 수 있는 가장 높은 우선순위 Task의 값이다
2. Active Ceiling
   • 세마포어가 Lock 상태일 때, 해당 세마포어의 우선순위 Ceiling값이 활성화됨
3. System Priority Ceiling
   • 현재 시스템의 우선순위 Ceiling값은 모든 Lock된 세마포어의 우선순위 Ceiling값 중 최대값

 

Rule

1. 기본 스케줄링
   • 모든 Task는 자신의 원래 우선순위로 스케줄링됨
2. Ceiling Rule
   • Task는 현재 시스템 우선순위 Ceiling보다 높을 때만 세마포어를 Lock할 수 있음
   • 같거나 낮으면 불가
   • 단, 이미 해당 세마포어를 보유하고 있는 Task는 예외
3. 우선순위 상속 규칙(Priority Inheritance Rule)
   • 만약 Task J가 우선순위 Ceiling값으로 다른 높은 우선순위 Task를 막고 있다면, J는 그 Task의 우선순위를 상속받음
4. 복귀 규칙
   • Task가 Critical Section을 벗어나면, 자신의 원래 우선순위로 복귀함

최초에 $\tau_3$이 S2를 Lock하는 순간, 세마포어 우선순위는 S2의 우선순위 Ceiling값인 $\tau_1$의 우선순위가 된다. 이때 $\tau_2$가 S1에 접근하고자 하는데 $\tau_1$은 세마포어 우선순위 Ceiling값보다 낮으므로 차단된다. 이때 $\tau_3$는 차단된 $\tau_2$의 우선순위를 상속받게 된다. (Critical Section동안) 그리고 $\tau_1$이 S1에 접근하는데 이때도 블럭된다. 이유는 세마포어 우선순위 Ceiling값이 $\tau_1$과 같기 때문이다. 이 때 $tau_3$은 $\tau_1$의 우선순위를 상속받게 된다. 이후에 $\tau_3$이 세마포어를 반납하면서 자신의 원래 우선순위로 돌아가게 된다.

 

$tau_2$가 S2를 취하면서 시스템 우선순위 Ceiling 값은 $\tau_1$의 우선순위가 되었다. 따라서 $\tau_1$의 S1 접근은 차단되며, 동시에 $\tau_2$는 $\tau_1$의 우선순위를 상속 받는다. $\tau_2$의 모든 작업이 끝나고 나서 비로소 $\tau_1$이 작업을 수행할 수 있게 된다 .

 

PCP 속성

1. Blocking은 최대 한번
   • 어떤 작업이 낮은 우선순위 작업에 의해 차단되는 것은 최대 한 번만 발생 가능
   • 공유하는 세마포어 수와는 무관하게 1회만 차단
   • PCP는 Deadlock을 원천적으로 방지
2. 간접 차단 존재
   • PCP에서도 Indirect blocking 존재 가능
   • 그렇지만, 직접 또는 간접 포함해서 총 한 번의 차단만 허용
3. 차단 시간 계산
   • Blocking Time = max(outermost CS during blocking jobs)

 

Blocking Time under PCP

$$b_i(rc)=max_{j=i+1}^{n}cs_j \cdot rc_{i,j}$$

$$rc_{i,j}=\begin{Bmatrix}
1 \,\,\,task_j\,\,\, preempt\,\,\, task_i \\ 0
\end{Bmatrix}$$

 

여기서 앞에 두 개는 쉽게 이해할 수 있다. Directly Blocked는 말 그대로 같은 자원에 접근하는 경우를 체크하면 되고, PIP Block의 경우에는 자원을 획득해서 얻은 우선순위가 비교우위일 경우 체크하면된다. (왜냐하면 PCP에서도 PIP 성질을 그대로 쓰기 때문에)

PCP Block은 가령 내가 세마포어로 획득한 자원의 시스템 우선순위에 의해 다른 Task가 다른 세마포어에 접근 못할 경우를 세어주면 된다.  (같은 경우 아님, 같은 세마포어 접근 시는 직접 차단으로 분류됨)

PIP는 직접, 간접의 차단 시간의 합을 구했지만, PCP는 차단 시간 중 가장 큰 값을 취하면 된다.