Threads는 어떻게 실행될까? : Alarm Clock, Priority Scheduling

Serye·2023년 4월 28일

운영체제

목록 보기

2/7

1-1 Alarm Clock

기존 방식

global ticks에 따른 busy waiting
* 🤔 busy waiting이란?
thread가 CPU를 점유하면서 대기하고 있는 상태로, 현재 시간이 목표 wake-up 시간을 초과했는지 확인한다. 조건이 만족되지 않으면 thread는 계속 루프를 돌며 시간을 다시 확인한다.
busy waiting의 경우 시간 확인 코드를 반복적으로 실행하여, CPU 자원을 소모한다. 수행할 의미 있는 작업이 없는 경우에도 thread가 지속적으로 활성화되기 때문에 비효율적인 CPU 사용으로 이어진다. CPU 자원을 지속적으로 소비하므로 다른 thread나 process가 CPU를 효과적으로 사용하지 못하게 하므로 비효율적인 접근 방식이다. 에너지를 낭비하고 전체 시스템 성능을 저하시킨다.

목표

타이머 인터럽트를 사용하여 Alarm Clock 구현

기본 컴퓨터 아키텍처에서 제공하는 타이머 하드웨어인 8254칩 즉, PIT(Programmable Interval Timer)를 활용한다.
경과 시간을 'tick'으로 추척한다. 각 타이머 인터럽트는 하나의 tick에 해당하므로 운영체제가 시간의 흐름을 정확하게 측정할 수 있다.
thread가 지정된 시간동안 잠자기를 원할 때는 원하는 수면 시간동안 타이머를 설정하는 함수를 호출한다. 그러면 thread는 blocked 상태가 되어 sleep list에 들어가게 된다.
타이머 인터럽트가 발생하면 인터럽트 핸들러가 시스템 tick 카운트를 증가시킨다. 그런 다음 휴면 목록을 확인하여 wake-up 시간에 도달한 thread가 있는지 확인한다. thread의 wake-up 시간이 현재 틱 카운트 이하인 경우(현재 틱 카운트가 wake-up 시간을 지난 경우) ready 상태가 되어 ready lsit에 들어가게 된다.
FIFO형식으로 running 상태이던 thread의 동작이 끝나면 ready list의 첫번째 thread가 running 상태로 바뀌고 실행된다.

1-2 Priority Scheduling

기존 방식

ready list에 들어온 순서대로 실행되는 FIFO 방식

목표

우선 순위 기반 스케줄링 알고리즘을 구현

여러 thread가 lock, semaphore, condition variable을 얻기 위해 기다릴 경우 우선순위가 가장 높은 thread가 CPU를 점유하도록 구현
cond의 waiters: sem_elem(sema 구조체의 요소)의 리스트. sem_elem은 특정 조건이 충족되기를 기다리는 thread이다.
sema의 waiters: t_elem(thread 구조체의 요소)의 리스트. t_elem은 세마포어를 획득하기 위해 대기 중인 thread이다.
thread는 wake-up 시간이 지나면 ready list로 가게 된다. 그러고 lock이 없다면 wait list로 가게 된다. 즉, wake-up 시간이 지났고, lock이 있는 thread는 순서가 되면 running thread가 된다.

semaphore랑 lock의 차이점

리소수 수

semaphore: 세마포어에는 일반적으로 사용 가능한 리소스의 수를 나타내는 카운터가 있다. 스레드는 자원을 획득하기 위해 카운터를 감소(대기 작업)하고 자원을 해제하기 위해 증가(신호 작업)할 수 있다.
lock: 잠금에는 고유한 리소스 수 개념이 없습니다. 본질적으로 바이너리이므로 잠기거나 잠금 해제된다. 잠금은 단일 스레드에 의해 유지되며 잠금을 획득하려는 다른 스레드는 잠금이 해제될 때까지 차단된다.
대기 매커니즘
semaphore: 리소스 수가 0이면(현재 모든 리소스가 사용 중임을 나타냄) 해당 쓰레드는 세마포어의 대기자 목록에 추가된다.
lock: 스레드가 현재 다른 스레드가 보유하고 있는 잠금을 획득하려고 하면 차단되고 잠금이 해제될 때까지 대기 상태가 됩니다. 잠금이 사용 가능해지면 대기 중인 스레드가 차단 해제되고 잠금을 획득할 수 있습니다.
소유권
semaphore: 소유권의 개념이 없다.
lock: lock을 획득한 thread는 lock을 해제할 때까지 해당 lock의 소유자가 된다.

Priority Inversion

우선 순위가 높은 thread가 우선순위가 낮은 thread를 기다리는 현상

예를 들어 아래의 세 가지 작업이 있다.

우선순위가 높은 작업(작업 A)
우선순위가 낮은 작업(작업 C)

우선 순위가 높은 작업 A는 실행할 준비가 되어 있으며 우선 순위가 낮은 태스크 C가 현재 보유하고 있는 공유 리소스에 대한 액세스, 즉 lock이 필요하다. 우선 순위가 가장 높은 작업 A는 작업 C가 보유한 리소스 없이는 진행할 수 없기 때문에 blocked 상태로 유지됩니다. 작업 C는 실행을 재개하고 결국 작업 A에 필요한 리소스를 해제한다. 마지막으로 우선 순위가 가장 높은 작업 A를 진행할 수 있다.

이렇게 진행이 되면 결국 작업 A는 우선 순위가 높지만 마지막에 실행되는 우선순위 역전 현상이 나타난다.

우선순위 역전 현상을 PintOS에서는 priority donation으로 해결했다.

Priority Donation

우선순위가 낮은 thread가 보유하고 있는 공유 리소스를 기다리는 높은 우선순위 thread의 우선순위와 일치하도록 일시적으로 낮은 우선순위 thread의 우선순위를 높인다.

예를 들어 작업 A는 자원 보유자인 작업 C에게 lock을 요청하고, 우선순위를 부여한다. 작업 C의 우선 순위는 작업 A의 우선 순위와 일치하도록 일시적으로 높아져 작업 C가 더 높은 우선 순위로 실행될 수 있다. 결과적으로 작업 C는 실행을 즉시 완료하고 공유 리소스를 해제할 수 있다. 그러면 작업 A는 lock을 획득하고 실행될 수 있다.