FRAP: A Flexible Resource Accessing Protocol for Multiprocessor Real-Time Systems

느낀점

 

사전 필요 지식

멀티프로세서 실시간 시스템에서 공유 자원에 대한 상호 배타적 접근과 관련하여 데이터 무결성을 보장하고 예측 가능한 타이밍을 유지하기 위해서 여러 자원 공유 프로토콜이 개발되었다. 기존 멀티프로세서에서 자원 공유 프로토콜은 크게 두 가지 범주로 분류할 수 있다.

1. 서스펜션 기반(Suspension-based) 프로토콜: 자원 요청이 즉시 충족되지 않으면 Task가 스케줄러에 의해 전환(Switch Away)된다. 이는 빈번한 Context Swtiching을 야기하여 상당한 Overhead를 발생시킬 수 있다.

2. 스핀 기반(Spin-based) 프로토콜: Task는 자원이 부여될 때까지 해당 프로세서에서 자원을 적극적으로 대기(Spin)한다. Spin Lock은 복잡성이 낮아서 실제 산업계에서 널리 적용되는 기술이다. 예를 들어, AUTOSAR 표준에서는 Spin Lock을 사용하도록 규정하고 있다. 스핀 기반 접근 방식은 해당 프로세서에서의 다른 Task에 지연을 만들 수 있다. 

주류 Spin-based 자원 공유 프로토콜은 일반적으로 FIFO(First-In-First-Out) 순서로 자원을 서비스한다. 로컬 자원(단일 프로세서 내에서 공유되는 자원)은 FP-FPS 시스템에서 Priority Ceiling Protocol(PCP)에 의해 제어된다. 

• Multiprocessor Stack Resource Protocol(MSRP): FIFO Spin Lock을 사용하는 Non-Preemptive 자원 공유 방식이다. Task는 자원을 위해 비선점적으로 스핀하며, 자원을 획득한 후에도 비선점적으로 실행된다. MSRP는 자원 접근 Task를 강력하게 보호하지만, 로컬 고 우선순위 Task의 실행에 영향을 미칠 수 있다.  Critical Section 길이가 긴 자원에 대해서는 Task가 다른 Task에게 긴 Blocking을 부과할 수 있으므로 MSRP가 유리하다고 볼 순 없다.
• Preemptable Waiting Locking Protocol(PWLP): Task는 기본 우선순위(선점 가능)로 스핀하지만, 자원을 가지고 실행할 때는 비선점적으로 수행한다. 스핀하는 동안 고 우선순위 Task에 의해  선점될 수 있으며, 이 경우 Task의 요청이 취소되고 FIFO 대기열에서 제거된다. Task가 재개되면 대기열 끝에서 자원을 다시 요청하고 다시 스핀을 한다. 선점 시 취소 매커니즘으로 인해 Task는 자원 스핀 중 선점될 경우 재요청으로 인한 추가 블록킹을 겪을 수 있다. 
• Multiprocessor resource sharing Protocol(MrsP): Task는 로컬 Task 중 해당 자원을 요청하는 Task의 최고 우선순위인 천장 우선순위(Ceiling Priority)로 스핀하고 자원을 가지고 실행한다. 대기열의 헤드 상태일 때 선점되면, 해당 Task는 동일한 자원을 위해 스핀하는 Task가 있는 다른 프로세서로 마이그레이션될 수 있다. 마이그레이션 비용이 상당할 수 있으며, Task가 빈번한 마이그레이션을 경험하면 추가 지연이 발생할 수 있다.

또한 스핀 기반과 서스펜션 기반 접근 방식을 모두 사용하는 하이브리드(Hybrid) 자원 공유 솔류션도 존재한다. 이는 낮은 스핀 우선순위로 Spin Lock을 구현하여 서스펜션을 실현하기도 한다. 이러한 하이브리드 접근 방식은 자원 관리에 유연성을 제공할 수 있지만, 서스펜션으로 인해 여러 우선순위가 Priority Inversion Blocking과 Overhead가 발생할 수 있으며, 두 가지 잠금 방식에 의한 블로킹 효과를 모두 분석해야하므로 해당 분석이 크게 복잡해지고 비관적(pessimistic) 분석범위로 이어질 수 있다. 

 

Problem Statement

무엇이 문제인가? 

멀티프로세서 실시간 시스템에서 fully-partitioned fixed-priority scheduling(FP-FPS) 하에서 공유 자원을 사용할 때, 기존의 spin-based 프로토콜은 다음과 같은 한계를 가진다. 

• 고정된 spin priority policy -> 모든 Job에 일률적인 정책 강제 
• 긴 Resource Request 또는 긴 Critical Section에 대해 비효율적
• Blocking Time에 대해 과도하게 보수적인 분석 -> System Schedulability 저하
• Non-predictable Priority Inversion 발생 가능

 

해결해야 할 핵심 문제:

• Shared Resource 접근 시 다양한 상황에 대응 가능한 유연한 Priority 지정
• 정확하고 덜 보수적인 Blocking Analysis
• 다른 Job의 긴급성에 따라 Blocking을 조절하는 능력

 

Key Contributions

FRAP의 주요 기여:

1. FRAP(Flexible Resource Accessing Protocol) 제안:

•  Job이 Resource 접근 시, Base Priority <= Spin Priority <= Max Priority 사이의 Priority에서 회전 가능 

2. MCMF(Minimum Cost Maximum Flow) 기반의 Blocking Analysis 제안:

• 기존 분석에서는 처리 불가능한 Bi(Arrival Blocking), Wi(Additional Blocking)의 상호작용을 정확하게 모델링 

3. Spin Priority Assignments Algorithm 개발:

• 각 Job이 접근하는 Resource마다 적절한 Spin Priority를 계산하여 High Priority Job의 Blocking 최소화

4. 실험결과: 

• 기존 Spin Based Protocol 대비 15.20% ~ 32.73% 향상, 최대 65.85% 향상
• 하이브리드 방식 대비 76.47% 평균 성능 개선 

 

Algorithms

Job Response Time Analysis Formula(FRAP 전반에 해당):

$$ R_{i}=C_{i}+E_{i}+B_{i}+W_{i}+I_{i}$$

• $C_{i}$: WCET + Resource 접근 시간 
• $E_{i}$: Spin Delay
• $B_{i}$: Arrival Blocking
• $W_{i}$: Additional Blocking 
• $I_{i}$: High-Priority Interference 

 

Spin Delay($E_{i}$):

$$E_{i}=\sum_{r_{k}\in R}^{}(\sum_{\lambda \neq A_{i}}^{}min(\zeta_{i}^{k},\xi _{i,m}^{k})\cdot c_{k})$$

• $\zeta_{i}^{k}$: Task와 그 보다 Priority가 높은 Task Request 수 
• $\xi_{i,m}^{k}$: Remote Processor의 Resource Request 수

 

 Bi + Wi Blocking Analysis (MCMF-Based Optimization):

• Blocking Item Set들을 각 Task의 Bi 및 Wi와 연결
• 문제는 MCMF(Minimum Cost Maximum Flow)로 변환하여 최대 Bi + Wi를 효율적으로 계산
• MILP보다 계산량이 적고 실용적

 

Spin Priority Assignments 알고리즘 개요:

• 각 Job에 대해 높은 Priority부터 순차적으로 처리 
• Resource가 Arrival Blocking을 유발하면 해당 Resource에 대해 하위 Job들의 Spin Priority를 감소시킴
• 일정 조건에서 Resource 접근 Priority를 Base Priorit로 초기화 가능

 

Intuition

기존의 경직된 정책의 한계를 극복하려면? 

• MSRP: Non-preemptive Spin으로 Bi 큼, Wi 없음
• PWLP: Preemptive Spin으로 Bi 작음, Wi 큼

-> 각 방식은 상황에 따라 장단점이 달라져 "하나로 통합"이 어려움

 

FRAP의 핵심 직관: 

• Job의 성격(긴급도, 자원 사용 패턴)에 따라 개별적으로 Resource 접근 Priority를 조절
• Spin 중 Preemptive 허용 여부, Resource별 Priority 유연성 부여 -> 정밀한 Blocking 관리
• MCMF로 Bi + Wi를 함께 최적화 -> 기존 기법의 한계 해결