정의
우선순위 상한 프로토콜(priority ceiling protocol)은 각 세마포어에 그것을 잠글 수 있는 job들 중 최고 우선순위를 상한으로 정적으로 부여하고, 그 상한들을 기준으로 임계 구역 진입을 통제하는 우선순위 상속 프로토콜의 확장이다.[1]
우선순위 상속 프로토콜은 블로킹 시간에 상한을 주었지만 교착과 사슬 블로킹은 남겨 두었다. 상한 프로토콜은 락이 잠긴 뒤에 우선순위를 조정하는 대신 잠글 수 있는 시점 자체를 제한해 두 문제를 함께 없앤다.
원형 프로토콜
기본 착상은 이렇다. 어떤 job J가 다른 job의 임계 구역을 선점하고 자기 임계 구역을 실행하게 될 때, 그 새 임계 구역이 실행될 우선순위가 선점당한 모든 임계 구역의 상속 우선순위보다 반드시 높도록 보장한다. 이 조건을 만족시킬 수 없으면 J의 진입을 거부하고 J를 suspended 상태로 두며, J를 막게 된 job이 J의 우선순위를 상속한다.
이를 판정 규칙으로 옮기면, job J는 자기 우선순위가 J 외의 job들이 잠가 둔 모든 세마포어의 상한보다 높을 때에만 새 임계 구역을 시작할 수 있다.[1]
여기서 나오는 거부는 직접 블로킹도 push-through 블로킹도 아닌 셋째 형태이며 상한 블로킹(ceiling blocking)이라 부른다. 잠재적 문제를 미리 피하려고 때로 불필요한 블로킹을 만든다는 점에서 이 프로토콜은 비관적(pessimistic)이다. 그 대가로 최악 블로킹은 크게 개선된다 — 어떤 job도 낮은 우선순위 job의 임계 구역 하나가 실행되는 시간만큼만 블로킹된다. 실제 블로킹이 서로 떨어진 여러 구간에서 일어나더라도 총량은 그 한계를 넘지 않는다.
교착이 사라지는 이유도 같은 규칙에서 나온다. 진입을 거부당한 job은 임계 구역 밖에서 멈추므로 자원을 쥔 채 기다리는 상태가 만들어지지 않고, 따라서 서로를 기다리는 순환이 형성될 수 없다.
즉시 상한 방식
POSIX와 OSEK OS가 규정하는 것은 더 단순한 변형이다. 락 시도 시점에 잠긴 세마포어들의 상한과 비교하는 대신, 자원을 잠그는 순간 그 자원의 상한으로 우선순위를 곧바로 올린다.
POSIX가 규정하는 PTHREAD_PRIO_PROTECT 속성이 이 방식이다. 이 속성으로 초기화된 뮤텍스를 소유한 스레드는, 다른 스레드가 그 뮤텍스에 블로킹돼 있든 아니든 상관없이, 자기 우선순위와 자신이 소유한 뮤텍스들의 상한 중 가장 높은 값으로 실행한다.[2]
차이는 관측되는 거동에 나타난다. 원형 프로토콜에서는 높은 우선순위 job이 락을 시도하고 거부당해 블로킹되는 구간이 생기지만, 즉시 방식에서는 자원을 쓸 수 있는 job이 애초에 실행 상태로 들어오지 못하므로 락 시도도 블로킹도 발생하지 않는다.
OSEK 자원 관리
OSEK/VDX OS는 자원 관리에 즉시 상한 방식을 규정하며 이를 OSEK 우선순위 상한 프로토콜이라 부른다. 규정은 세 항으로 이루어진다.
- 시스템 생성 시점에 각 자원에 상한 우선순위를 정적으로 배정한다. 상한은 그 자원 또는 그 자원에 연결된 자원에 접근하는 모든 태스크의 최고 우선순위 이상이어야 하고, 동시에 그 자원에 접근하지 않으면서 접근 태스크들의 최고 우선순위보다 높은 태스크들의 최저 우선순위보다는 낮아야 한다.
- 태스크가 자원을 요구할 때 현재 우선순위가 그 자원의 상한보다 낮으면 상한까지 올린다.
- 태스크가 자원을 해제하면 그 자원을 요구하기 직전에 동적으로 배정돼 있던 우선순위로 되돌린다.
이 규정 위에서 OSEK OS는 두 태스크가 같은 자원을 동시에 점유할 수 없고, 우선순위 역전이 일어나지 않으며, 교착이 발생하지 않고, 자원 접근이 대기 상태로 이어지지 않는다고 선언한다. 실제로 이미 점유된 자원에 접근을 시도하는 상황 자체가 생기지 않는다. 대신 자원 상한 이하의 우선순위를 가진 태스크들에 지연이 생기며, 그 지연은 낮은 우선순위 태스크가 자원을 점유하는 최대 시간으로 제한된다. 자원이 해제되면 그 자원을 점유할 수 있는 다른 태스크가 실행 상태에 들어올 수 있고, 선점 가능한 태스크에게 이 지점이 재스케줄링 지점이 된다. 스케줄러 자체도 자원으로 다루어 RES_SCHEDULER라는 이름의 자원이 자동 생성된다.[3]
상한 배정은 설계 시점의 책임
상한 우선순위는 실행 중에 계산되지 않고 시스템 생성 시점에 고정된다.[3] 어떤 태스크가 어떤 자원을 쓰는지 설계 시점에 모두 알려져 있어야 하며, 나중에 태스크가 자원 접근을 추가하면 상한도 함께 다시 정해야 한다.
인터럽트 수준으로의 확장
OSEK OS는 자원 관리를 인터럽트 수준까지 넓히는 것을 선택 사항으로 둔다. 인터럽트에서 쓰이는 자원의 상한을 정하려면 모든 태스크 우선순위보다 높은 가상 우선순위를 인터럽트에 배정하고, 상한 계산에 태스크와 인터럽트 서비스 루틴을 함께 넣는다. 태스크와 인터럽트가 같은 자원을 나눠 쓰는 구성에서 두 흐름이 같은 자원을 동시에 점유하지 않게 만드는 것이 이 확장의 목적이다.[3] 소프트웨어 우선순위와 하드웨어 인터럽트 수준을 실제로 어떻게 조작할지는 구현에 맡겨져 있으며, 인터럽트 쪽 규정은 OSEK 인터럽트 처리에서 다룬다.