Stack-Based Scheduling of Real-Time Processes

느낀점

Stack 메모리의 효율적 사용이라는 실용적 문제를 수학적으로 분석한 점이 인상 깊었다. Fixed Priority Scheduling 환경에서 공유 Stack 모델의 안전성과 효율성을 정량적으로 입증해주며, 직관적으로 설명해준다는 점이 좋았다. 

Problem Statement

이 논문에서는 실시간 시스템에서 발생하는 Priority Inversion, Deadlock, 그리고 Blocking 문제를 해결하기 위해 기존의 Priority Ceiling Protocol(PCP)를 확장한 새로운 정책인 Stack Resource Policy(SRP)와 Minimal SRP(MSRP)를 제안한다.  

실시간 시스템에서는 우선순위 기반 스케줄링 시 발생하는 대표적 문제:

• Priority Inversion (우선순위 역전)
• Deadlock (교착상태)
• Stack Memory 최적화 부족
• Transitive Blocking (다중 블록킹)

기존의 Priority Ceiling Protocol(PCP)는 어느정도 이 문제를 해결했지만:

• 그 해결책은 Binary Semaphore 중심 (0 아니면 1)
• Fixed Priority 환경에 제한적
• Stack Sharing 문제를 고려하지 않았다. 

특히, EDF(Earliest Deadline First)와 같은 동적 우선순위 스케줄링에서 적용이 복잡하다

간략하게 정리하면 위와 같다. 

 

Fixed Priority real time systems에서 Task들이 공유 Stack 공간을 효율적으로 사용하는 방법에 관한 문제를 다룬다. 특히 Task간의 Preemption으로 인해 발생하는 Stack Overhead를 줄이기 위해 Stack Based Scheduling 방식을 제안한다. 

1. 기존 실시간 스케줄링에서는 각 Task마다 별도의 Stack이 필요해 공간 낭비가 발생
2. 특히 Fixed Priority Schedulingdp서는 Stack 메모리의 최악의 경우 크기 계산이 어려움

 

다른 방향으로 정리해보면 아래와 같다. 

이 논문에서 제시된 Stack-Based Scheduling은 실시간 시스템에서 발생하는 여러가지 핵심과제를 해결하는 것을 목표로 하는데 정리하면 다음과 같다. 

1. 절대적인 타이밍 요구사항 충족(Deadline): Hard Real Time Computer System은 종종 Deadline으로 표현되는 절대적인 타이밍 요구사항을 가진다. 시스템 설계가 주어진 자원 제약 내에서 타이밍 요구사항을 충족할 수 있는지 사전에 검증하는 것이 필수적이다.

2. 자원 제약 및 사용량 분석의 어려움: Real Time System은 종종 심각한 자원 제약을 받으며, 특히 제한된 메모리가 문제이다. 프로그램의 타이밍 및 자원 사용 속성을 검증하는 것은 본질적으로 어렵다.

3. 스케줄링의 복잡성: Task Set의 고정된 Deadline까지 실행을 완료하도록 스케줄링될 수 있는지 판단하는 것은 제약이 없는 한 NP-Hard문제로 알려져 있다. 

4. 공유 자원 및 동기화 처리: 초기 스케줄링 모델(Liu and Layland)은 Task간 동기화 요구사항이 없다고 가정했지만, 실제 시스템에서는 Task들이 공유 자원을 사용하고 동기화해야 한다.

5. Priority Inversion 방지: 공유 자원 사용 시 발생하는 핵심적인 문제 중 하나는 Priority Inversion이다. 이는 우선순위가 낮은 Task가 자원을 점유하여 우선순위가 높은 Task의 실행을 방해하는 상황이다. 일반적인 운영 체제 기법은 실시간 스케줄링 분석에 적합할 만큼 Blocking에 대한 충분히 엄격한 상한을 제공하지 못하며, 여러 개의 낮은 우선순위 Task에 의해 Block될 수 있다. PCP(Priority Ceiling Protocol)과 SRP(Stack Resource Policy), MSRP(Minimal SRP)는 이러한 우선순위 역적을 엄격하게 제한하여 스케줄 가능성을 향상시키는 것을 목표로 한다. 

6. DeadLock 및 다중 우선순위 역전 방지: 우선순위 역전의 극단적인 형태인 DeadLock과 하나의 Task가 둘 이상의 낮은 우선순위 Task의 Critical Section 기간 동안 Block되는 다중 우선순위 역전을 방지하는 것이 중요하다. SRP는 자원 할당 정책을 통해 이러한 상황을 방지한다. 

7. Runtime Stack 공간 공유 지원: 기존 프로세스 기반 모델에서는 각 프로세스가 자체 Runtime Stack을 필요로 하여 많은 메모리가 요구될 수 있다. SRP의 주요 동기 중 하나는 Task들이 Runtime Stack을 공유할 수 있도록 지원하는 것이다. 이를 통해 필요한 저장 공간을 크게 줄일 수 있다.

8. Stack 공유로 인한 문제 해결: Stack 공유는 새로운 문제(Stack Blocking)를 야기할 수 있으며, 이는 다른 Non-preemptive 자원에 대한 Blocking과 상호작용할 때 DeadLock이나 무한한 우선순위 역전으로 이어질 수 있다. SRP는 Stack 사용을 자원 중 하나로 처리하여(Ceiling 값을 0으로 정의함) Stack 사용으로 인한 Blocking 문제를 해결한다. 

9. Context Switching Overhead 감소: Context Switching 비용은 프로세서에 따라 상당할 수 있다. SRP는 early blocking 정책을 통해 PCP와 같은 다른 정책에 비해 불필요한 Context Switching을 줄일 수 있다.

10. 블필요한 Blocking 최소화: SRP는 경우에 따라 PCP보다 더 보수적으로 Blocking을 유발할 수 있다는 단점이 있다. MSRP는 단일 Stack 및 특정 우선순위 정책 하에서 불필요한 Blocking을 최소화하면서도 Deadlock과 다중 우선순위 역전을 방지하는데 최적화된 정책이다. 

 

그러면 SRP/ MSRP와 PCP 및 기타 정책과 어떻게 비교되는지에 알아보자

Stack Based Scheduling 정책인 SRP(Stack Resource Policy)와 MSRP(Minimal SRP)는 Real Time System의 핵심 과제를 해결하기 위해 기존의 스케줄링 정책들, 특히 Priority Ceiling Protocol(PCP)을 확장하고 개선한 것이다. 이 정책들은 Task간의 공유 자원 사용 및 동기화로 인해 발생한느 문제점을 다룬다. 

기존 정책과의 비교:

1. Liu and Layland 모델: 초기 Liu and Layland의 연구는 Task간 동기화 요구사항이 없다고 가정했다. 그러나 실제 시스템에서는 Task들이 공유 자원을 사용하고 동기화해야 한다. PCP, SRP, MSRP는 이러한 공유 자원 사용 시 발생하는 문제를 해결하기 위해 개발되어야 한다. 

2. 일반 운영 체제 기법: 일반적인 운영 체제 기법 (예: 단순 우선 순위 상속)은 실시간 시스템의 엄격한 스케줄링 분석에 적합할 만큼 Blocking에 대한 충분히 엄격한 상한을 제공하지 못하며, Task이 여러 개의 낮은 우선 순위 Task에 의해 Block될 수 있다. (다중 우선 순위 역전). 또한 DeadLock과 같은 문제가 발생할 수 있다. SRP와 MSRP는 이러한 문제들을 해결하고 Blocking을 엄격하게 제한하는 것을 목표로 한다. SRP는 DeadLock과 다중 우선 순위 역전을 방지한다. MSRP는 단일 Stack 및 특정 우선 순위 정책 하에서 불필요한 Blocking을 최소화하면서도 DeadLock과 다중 우선 순위 역전을 방지하는데 최적화된 정책이다.

3. Havender의 자원 할당 기법: Havender의 순서 지정 자원 할당 기법은 Task가 최대 n개의 낮은 우선 순위 Task에 의해 Block될 수 있다. SRP는 자원 획득 순서를 제한하지 않으며, 시작 전에 모든 자원을 할당하는 Havender의 집단 할당 (Collective Allocation)과는 달리, 필요한 자원만 실제로 요청될 때 할당한다.

Priority Ceiling Protocol (PCP)과의 비교 (SRP/ MSRP의 확장 및 차이점):

SRP와 MSRP는 PCP를 여러 면에서 확장하고 개선한 것이다. 주요 차이점은 다음과 같다. 

• 우선 순위 vs. 선점 수준 (Preemption Levels):
  • PCP는 각 Task의 선점 수준이 고정된 우선 순위와 동일하다고 가정한다.
  • SRP는 Task의 우선 순위(동적일 수 있음, 예: EDF)와 선점 수준(정적)을 분리한다. 이를 통해 SRP는 동적 우선 순위 정책인 EDF(Earliest-Deadline-First)에 직접 적용될 수 있으며, 동적으로 Ceiling Priority를 재계산할 필요가 없다.
• 프로세스 모델:
  • PCP 모델은 각 프로세스가 동일한 유형의 Task 요청 시퀀스로 구성된다고 본다.
  • SRP는 하나의 프로세스가 서로 다른 선점 수준을 가진 여러 Task를 요청할 수 있다고 가정한다. 
• 자원 유형:
  • 원래 PCP는 Binary Semaphores를 다루며, 이후 확장되어 읽기-쓰기 잠금(reader-writer locks)을 처리한다.
  • SRP는 다중 단위 자원(multi-unit resource)을 허용한다. 자원의 Ceiling을 현재 사용 가능한 단위 수에 따라 달라지는 함수로 취급하여 Binary Semaphore와 읽기-쓰기 잠금을 포함한다.
• Runtime Stack 공간 공유:
  • PCP는 Stack 공유를 허용하지 않는다. 전통적인 프로세스 모델에서는 각 프로세스가 자체 Stack을 필요로 하여 메모리 사용량이 많아질 수 있다. 
  • SRP는 공유 Runtime Stack을 자원으로 취급하여 Stack 공유를 지원한다. SRP는 공유 Stack의 Ceiling을 0으로 정의하여 Stack 사용으로 인한 Blocking을 무시하고, Stack 공유 시스템에서 발생하는 DeadLock이나 무한한 우선 순위 역전 문제를 해결한다. 이를 통해 필요한 저장 공간을 크게 줄일 수 있다. 
• Early Blocking:
  • PCP는 Task가 실행을 시작한 후 첫번째 자원 요청 시점에 Block한다. 
  • SRP는 모든 Task가 공유 Stack 사용을 요청하는 것처럼 처리하여, 필요하다면 Task가 Stack 공간을 차지하려 할 때 (즉, 선점하려 할 때), Block한다. 이는 Task가 실행을 시작한 후 Block되는 가능성을 제거하고, 불필요한 Context Switching을 줄여준다. SRP는 Context Switching 비용이 큰 프로세서에서 특히 유리하다.
• Blocking 분석의 엄격성
  • SRP의 사전 Blocking 정책은 경우에 따라 PCP보다 더 보수적으로 Blocking을 유발할 수 있다. (예: 자원을 전혀 사용하지 않는 Task의 경우). 하지만 SRP 하에서 비선점 자원을 사용하는 Task의 최대 우선 순위 역전 시간은 PCP 하에서보다 길지 않다. 
  • MSRP는 SRP의 한계를 개선하여, 특정 조건 하에서 불필요한 Blocking을 최소화하는데 최적화되었다.
• MSRP의 추가적인 특징:
  • MSRP는 SRP보다 약간 더 복잡한 변형이다.
  • MSRP의 선점 테스트는 SRP보다 더 복잡하지만, Deadlock 및 다중 우선 순위 역전 방지라는 동일한 바람직한 특성을 가진다.
  • MSRP는 단일 공유 Run time Stack 환경 하에서 Deadlock이나 다중 Blocking을 허용하지 않는 어떤 정책보다도 최소한의 Blocking만을 부과한다. 즉, MSRP는 Stack 공유 환경에서 불필요한 Blocking을 최소화하면서도 안전성을 보장하는 최적의 정책으로 간주된다.

요약하자면, Stack Based Scheduling 정책(SRP/ MSRP)은 기존의 Liu and Layland 모델에서 고려하지 않은 공유 자원 및 동기화 문제를 해결하기 위해 PCP를 확장한 것이다. 특히, 우선 순위와 선점 수준을 분리하여 EDF와 같은 동적 우선 순위 스케줄링을 더 쉽게 지원하고, 다중 단위 자원을 처리하며, 결정적으로 Run time Stack 공유를 지원하고 이로 인한 문제 (Stack Blocking, Deadlock)를 해결하다. 또한, 사전 Blocking 정책을 통해 Context Switching Overhead를 줄이는 장점을 가진다. MSRP는 SRP에서 발생할 수 있는 불필요한 Blocking을 최소화하여 Stack 공유 환경에서 최적의 성능을 제공하고자 한다. 

목표: 자원 공유, 선점 제어, Stack Memory 효율성을 동시에 보장할 수 있는 확장된 스케줄링 정책 필요

 

Contributions

1. Stack Based 실행 모델 제안:

• LIFO 순서 기반의 Stack 관리 방식을 제안하며, 여러 Task가 공유 Stack 공간을 사용하도록 설계

2. Stack 공간의 Upper Bound 계산 기법 개발:

• 우선순위 기반의 Task Set에 대해 최악의 경우에 필요한 Stack 크기를 정량적으로 계산할 수 있는 방법을 제공

3. Stack Resource Policy(SRP) 개념과 연결:

• Task가 자원을 요청하는 시점을 제어함으로써 Stack 사용 최적화 및 Deadlock 방지 가능성을 제시 

4. Overhead 감소 및 Scheduling 효율성 향상:

• 메모리 사용량을 줄이면서도 Deadline 준수를 보장할 수 있는 현실적인 시스템 설계 전략을 제공

 

Key Ideas

1. Shared Stack Allocation:

• 각 Task가 개별 Stack을 갖는 대신, Preemption 관계를 고려한 공유 Stack 설계
• 실행 중인 Task가 Preemption될 때, Stack Frame을 LIFO 순서로 Push/ Pop하는 것을 보장

2. Stack Depth Analysis:

• Stack 사용량의 상한을 계산하기 위해 Preemption Chain을 분석함
• 특정 우선순위를 가진 Task가 동시에 실행될 수 있는 Preemption 가능한 결로를 추적해 누적 Stack 깊이를 결정

3. Preemption Thresholds & Priority Inheritance:

• 실행 가능한 Task 중, Stack 깊이에 영향을 주는 우선순위 경로를 제한함으로써 Stack 크기 최소화

 

Mathematical View

핵심 정의 및 기본 전제

• Fixed-Priority Scheduling(FPS): Task는 정해진 우선순위를 가지고, 항상 우선순위가 높은 Tassk가 먼저 실행됨
• Preemption: 더 높은 우선순위 작업이 도착하면 현재 Task가 중단되고 저장됨
• LIFO Stack Discipline: Stack은 후입선출 구조로, 가장 나중에 Preemption된 Task가 먼저 복귀함

 

Lemma 1 : Maximum Stack Depth Occurs at a Busy Period

The maximum stack depth required for a fixed-priority task set occurs during a critical insstant, i.e., a time at which all higher-priority tasks are released simultaneously with the task

가장 깊은 Stack 사용은 Task가 모든 높은 우선순위 Task와 동시에 요청될 때 발생한다는 사실을 보장한다. 이는 Liu & Layland의 Critical Instant Theorem과 유사한 개념이다.

증명

• Task $\tau_i$가 요청되고, 모든 우선순위가 더 높은 Task $\tau_1,...,\tau_{i-1}$도 동시에 요청될 경우,
• Stack은 각 Task의 호출 시점마다 깊이가 증가하며, 가장 깊은 체인이 형성된다.
• 이 상황을 제외하고는 Stack 사용량이 작기 때문에, 최대 깊이는 이 시점에서 발생

 

Theorem 1 : Stack Depth Upper Bound

Let $T = {\tau_1, \tau_2,...,\tau_n}$ be a set of fixed-priority periodic taskss with $\tau_1$ having highest priority. Let each task $\tau_i$ have worst-case execution time $C_i$. The maximum stack depth $S$ needed is bounded by:

$$S\leq \sum_{i=1}^{n}C_i$$

단, 이때 모든 Task가 동시에 시작되며 Preemption은 LIFO 구조를 따름

설명

모든 Task가 동시에 요청되면 우선순위가 높은 Task부터 실행되며, 하위 Tasks는 모든 Stack에 잠시 저장된다. 이 과정에서 필요한 Stack의 최대 깊이는 모든 Task의 실행 시간 합보다 클 수 없음을 보장한다.

수학적 증명

가정:

• Task는 우선순위 순으로 실행됨: $\tau_1 > \tau_2 > ... > \tau_n$
• 각 Task $\tau_i$의 실행 시간: $C_i$
• Preemption LIFO 구조: Preemption 당한 Task는 그대로 Stack에 보관됨

논리:

•  $\tau_n$이 실행되기 전에 $\tau_1$부터 $tau_{n-1}$까지 $n-1$개의 Task가 순차적으로 실행되며 모두 Stack에 저장됨
• 그러므로 최대 Stack 깊이는 다음과 같다:

$$S_{max}=\sum_{i=1}^{n-1}C_i\leq \sum_{i=1}^{n}C_i$$

(실제로는 $\tau_n$은 현재 실행 중이므로 Stack에 쌓이지 않는다.)

이것은 Worst Case Scenario에서도 Stack이 과도하게 커지지 않음을 보장한다. 

 

Theorem 2 : Stack Requirement Under Non-Preemptive Execution

If tasks are executed non-preemptively, the maximum stack requirement is equal to the maximum execution time among all tasks:

$$S_{non-preemptive}=max_{i\leq i\leq n}C_i$$

설명

Task가 Preemption없이 끝날 때까지 실행된다면, Stack은 한 번에 한 Task만 저장하면 되므로 가장 긴 Task의 실행 시간만큼의 공간이면 충분하다.

증명

• 어떤 Task도 실행 중에 Preemption되지 않음
• 한 번에 하나의 Stack Frame만 필요 -> 모든 $C_i$ 중 최대값이 곧 Stack 깊이

 

Stack Depth Analysis Algorithm (Pseudocode)

stack_depth = 0
for each task τi in priority order:
    if τi can be preempted:
        stack_depth += Ci

이 알고리즘은 Task를 우선순위 순으로 시뮬레이션하고, Preemption이 일어나는 시점에 Stack 깊이를 갱신한다.

정리해보면

1. 모든 Task가 동시에 요청될 때가 가장 깊은 Stack 사용량을 만든다.
2.  Stack 깊이는 실행 시간의 총합 이하로 제한된다. (Theorem 1)
3. Preemption이 없다면 단일 Task 실행 시간만 필요 (Theorem 2)
4. LIFO 구조는 Stack 공간을 재사용할 수 있는 강력한 기법이며, 실시간 시스템에서 매우 효과적이다.

 

Ref

• [1] T. P. Baker, "Stack-based scheduling of real-time processes," *Real-Time Systems*, vol. 3, no. 1, pp. 67-99, Mar. 1991, doi: 10.1007/BF00365393.