[OS] 스케줄링 알고리즘

스케줄러는 스케줄링 알고리즘에 따라 프로세서를 할당하고 작업을 완료한다. 대부분의 알고리즘은 대화식 사용자 환경과 빠른 응답 시간을 구현하는 것에 집중하는데, 여기서는 단일 처리 시스템을 기준으로 주요 스케줄링 알고리즘을 알아볼 것이다.

 

원칙적으로는 1개의 프로세스가 여러 프로세서 버스트를 가진다. 여기서는 간략하게 프로세서 버스트 1개의 길이를 프로세스 길이, 또는 프로세스 실행 시간이라고 칭한다.

 

기본 스케줄링

• 공평성 중시 : FCFS, RR
• 효율성 중시 : SPN, SRTN, HRN
  • 효율성 중시 알고리즘을 사용하기 위해서는 실행시간을 예측해야하는데 이에 대한 방법의 부재와 예측하는데 부하가 생길 수 있음.
    

    

 

선입선처리(FCFS, First-Come-First-Served) 스케줄링

---

• 선입선처리(FCFS, First Come First Served) 혹은 선입선출(FIFO, First In First Out) 스케줄링은 비선점 방법으로 프로세서 스케줄링 알고리즘 중 가장 단순하다.
• 프로세서를 요청하는 순서대로 프로세서를 할당하며, 선입선출(FIFO) 큐로 구현한다.
• 일관처리 시스템에서는 매우 효율적이나 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않다.
• 선입선처리는 대부분 성능이 좋지 않고 평균 대기 시간이 길 때도 있다.

※ 참고

비선점 스케줄링 : 한 프로세스가 자원(예: 프로세서) 을 선택했을 때 다른 프로세스가 해당 자원을 빼앗을 수 없다

 

선입선처리 스케줄링 예시 1

준비 큐에 프로세스 P1 ~ P5가 있고, 각각 실행 시간과 도착 시간은 위와 같다. 그리고 이 작업들을 선입선처리 스케줄링으로 실행하는 과정을 (b) 와 같은 간트 차트(Gant chart)로 나타낼 수 있다.

선입선처리 스케줄링 예시 2

프로세스들이 P3, P1, P4, P5, P2 의 순서로 준비 큐에 들어왔을 때는 아래와 같다.

그러면 평균 반환시간과 평균 대기시간은 [표 6-2] 와 같이 단축된다.

 

즉, 선입선처리에서 평균 반환시간과 평균 대기시간이 프로세스의 실행 시간에 따라 상당히 큰 폭으로 변할 수 있음을 알 수 있다.

 

 

동적 상황에서의 성능

예를 들어 프로세서 중심 프로세스 한 개와 입출력 중심 프로세스 3개가 있다고 가정

1. 프로세서 중심 프로세스가 프로세서를 할당받아 실행되는 동안 입출력 중심 프로세스는 입출력을 마치고 준비 큐로 이동하여 프로세서를 기다린다. 즉, 입출력장치들은 쉬게 된다(입출력장치는 비어 있음).
2. 프로세서 중심 프로세스가 프로세서의 사용을 마치고 입출력장치로 이동한다. 프로세서 버스트가 짧은 입출력 중심 프로세스가 프로세서를 신속하게 사용한 후 다시 입출력 장치를 사용하려고 입출력장치 큐로 이동한다. 이때 프로세서는 쉬게 된다(프로세서가 비어 있음)
3. 프로세서 중심 프로세스가 다시 준비 큐로 이동하여 프로세서를 할당받고 모든 입출력 중심 프로세스는 프로세서 중심 프로세스를 처리할 때까지 준비 큐에서 대기할 것이다.(반복 처리)

이처럼 큰 프로세스 하나를 처리하여 프로세서를 떠나기를 기다리는 것, 즉 프로세서 중심 프로세스 하나가 프로세서를 떠나기를 기다리는 현상을 호위 효과(convoy effect) 라고 한다. 프로세서 중심 프로세스나 입출력 중심 프로세스 중 한쪽으로 치우쳐 기다리는 불균형 상태를 의미하는 것이다. 

 

이 프로세서와 입출력장치는 실행 시간이 짧은 프로세스가 먼저 들어올 때보다 사용률이 떨어진다.

 

선입선처리 스케줄리의 장점과 단점

 

 

 

최소작업 우선(SJF, Shortest Job First) 스케줄링

---

• 최소작업 우선(SJF, Shortest Job First) 스케줄링은 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짦은 작업(프로세스)에 할당하는 방법이다.
• 프로세서 실행 시간이 동일하다면 선입선처리 스케줄링을 적용

 

최소작업 우선 스케줄링의 적용 예

아래 그림과 같이 실행 시간이 짧은 작업을 우선 처리할 때 평균 대기시간(W) 을 줄일 수 있다.

 

최소작업 우선 스케줄링 예

아래 예시를 보면 도착 시간이 0인 P1 은 우선처리 되지만 그 뒤로는 실행 시간이 짧은 프로세스가 먼저 처리되는 것을 확인할 수 있다.

 

최소작업 우선 스케줄링은 선점 또는 비선점이 가능하지만 비선점 스케줄링 알고리즘은 시분할 시스템에 사용하기 어렵다. 시분할 시스템에서는 각 사용자들이 일정한 간격으로 프로세서를 사용하기 원하므로, 특정 프로세스가 프로세서 사용을 연장하려고 하면 곤란하다.

 

선점 최소작업 우선 스케줄링 예

• 선점이면 시간 0일 때 큐에는 P1 밖에 없으므로 P1 을 시작한다.
• 시간 1에 P2 가 도착하지만 실행 시간이 29 이므로 아직 실행 시간이 더 짧은 P1 을 계속 실행한다.
• 시간 2에 도착한 P3 은 실행 시간이 6인데 P1 에 아직 실행 시간 8 이 남아 있으므로 선점하여 P3 을 실행한다.
• 시간 3에 P4 가 도착하면 실행 시간은 4이고 아직 P3 의 실행 시간 5가 남아 있으므로 선점하여 P4 를 실행한다.
• P4 가 실행을 완료하면 P3 의 나머지를 실행한다.
• 이러서 P1, P5, P2 순으로 실행한다.

 

선점형 알고리즘은 문맥 교환 시간이 소요되므로 반드시 비선점보다 유리하다고는 할 수 없다.

 

그리고 새로운 프로세스가 현재 실행 중인 프로세스의 남은 실행 시간보다도 실행 시간이 더 짧을 수 있어 선점 최소작업 우선 스케줄링은 최소잔여 시간 우선(SRTF, Shortest Remaining Time First) 스케줄링이라고 한다.

 

• 최소작업 우선 스케줄링은 주어진 작업(프로세스) 집합에서 평균 대기시간이 최소이므로 최적 알고리즘으로 볼 수 있다.
• 실행 시간이 짧은 작업(프로세스Short) 을 실행 시간이 긴 작업(프로세스Long) 앞에 놓아 긴 작업(프로세스) 의 대기시간은 증가하지만, 짧은 작업(프로세스)의 대기시간은 줄어 평균 대기시간을 줄였다.

 

최소작업 우선 스케줄링의 장점과 단점

• 일괄 처리 시스템에서는 작업(프로세스)의 제한 시간이 짧으면 빠른 응답을 요청하므로 사용자는 시간 한계를 정확하게 예상해야 한다.
• 시간 한계가 너무 짧으면 실행 시간이 제한 시간을 초과하여 작업을 다시 입력해야 할 수도 있다.
• 최소작업 우선 스케줄링은 작업(장기) 스케줄링에서 많이 사용된다.
• 단기 스케줄링에서는 다음 프로세스의 실행 시간을 예상할 수 없어 하드웨어를 구성하기 어렵다. 이것은 최소작업 우선 스케줄링 근사치를 사용하여 해결할 수 있다.

 

 

 

우선순위 스케줄링(Priority Scheduling)

---

• 준비 큐에 도착한 프로세스의 우선순위와 현재 실행 중인 프로세스의 우선순위를 비교하여 우선순위가 가장 높은 프로세스에 프로세서를 할당한다.
• 우선순위가 동일한 프로세스들은 선입선처리 순서로 스케줄링
• 최소작업 우선 스케줄링은 일반적인 우선순위 스케줄링의 특별한 경우

• 우선순위 스케줄링에서 우선순위(P) 는 예측된 다음 프로세서 버스트(실행 시간)의 역(τ)이다. 즉, P = 1 / τ.
• 실행 시간이 클수록 우선순위가 낮고, 우선순위는 0~7 또는 0~4,095 범위의 수를 사용한다. 단, 0을 최상위나 최하위로 정하지는 않았다.

 

프로세스의 우선순위 연산을 내부적 또는 외부적으로 정의

• 내부적 우선순위 : 제한 시간, 기억장소 요청량, 사용 파일 수, 평균 프로세서 버스트에 대한 평균 입출력 버스트의 비율 등
• 외부적 우선 순위 : 프로세스 중요성, 사용료 많이 낸 사용자, 작업을 지원하는 부서, 정책적인 요인 등

 

우선 순위 스케줄링도 선점 또는 비선점 가능

• 선점 우선순위 스케줄링 : 새로 도착한 프로세스의 우선순위가 현재 실행하는 프로세스의 우선순위보다 높으면 프로세서를 선점한다.
• 비선점 우선순위 스케줄링 : 단순히 준비 큐의 머리 부분에 새로운 프로세스를 넣는다.

네 단계 우선 순위를 갖는 준비 튜에서 실행 가능 프로세스는 우선순위가 가장 높은 큐(4) 의 프로세스를 실행한 후 큐(3)에 저장된 프로세스를 실행한다.

 

 

우선순위 스케줄링 예

선점 우선순위 스케줄링

• 시간 0일 때 큐에서 P1 밖에 없으므로 P1 을 시작한다.
• 시간 1에 P2 가 도착하지만 우선순위가 2이므로 P1을 계속 실행한다. 
• 시간 2에 P3 이 도착하면 우선순위가 4이므로 P1 에 아직 실행 시간 8이 남아 있지만 선점되어 P3 을 실행한다.
• P3의 실행을 완료하면 우선순위가 높은 P1 을 실행한다. 
• 이어서 P2 와 P5 는 우선순위가 2로 같으나 선입선처리 순서로 스케줄하므로 P2를 먼저 실행한다.
• 그리고 P5, P4 의 순서로 실행한다.

 

비선점 우선순위 스케줄링

• 시간 0일 때 큐에는 P1 밖에 없으므로 P1 을 시작한다.
• 이어서 가장 우선순위가 높은 P3 을 실행하고 P2, P5, P4 순으로 실행한다

즉, 단순히 준비 큐에서 우선순위가 높은 순서대로 실행하는 것이다. 

 

 

우선순위 스케줄링의 문제

• 우선순위 스케줄링의 주요 문제는 무한 정지와 기아 상태 이다.
• 실행 준비는 했으나 우선 순위가 높은 프로세스가 계속 들어오면 우선 순위가 낮은 프로세스는 무한정 기다려야하는 기아 상태가 발생한다.

 

이런 기다림 문제를 해결할 수 있는 방법이 에이징(aging) 이다.

 

에이징(aging) 

• 시스템에서 오래 대기하는 프로세들의 우선순위를 점진적으로 증가시키는 방법
• 시간이 지나면 점차 프로세스의 우선순위가 높아진다.

예를 들어 우선순위 범위가 0(낮음) 에서 127(높음) 까지라고 하자.

• 에이징을 적용하여 매 15분마다 대기 중인 프로세스 우선순위를 1씩 증가시키면 초기에 우선순위가 0이였던 프로세스가 시스템에서 우선순위가 가장 옾아져 처리할 수 있다.
• 이때 우선순위가 0인 프로세스가 127의 우선순위로 높아지는데 32시간 밖에 소요되지 않는다.

 

 

우선순위 스케줄링의 장점과 단점

 

 

 

 

라운드 로빈(Round-Robin) 스케줄링

---

• 라운드 로빈(round-robin) 스케줄링은 특별히 시분할 시스템을 위해 설계했다.
• 작은 단위의 시간인 규정 시간량(time quantum) 또는 시간 할당량(time slice) 을 정의했다.
• 보통 규정 시간량은 10 x 10 밀리초에서 100 x 100 밀리초 범위로 한다.
• 준비 큐를 순환 큐(circular queue) 로 설계하여 스케줄러가 준비 큐를 돌아가면서 한 번에 한 프로세스에 정의된 규정 시간량만큼 프로세서를 제공한다.

 

스케줄러는 준비 큐의 앞부붙에 있는 프로세스에 프로세서를 할당한다. 이와 동시에 규정된 시간량이 지나 인터럽트가 발생하도록 하면 다음 두 가지 경우가 가능하다.

 

1. 규정 시간 안에 작업을 마친 경우로 프로세서가 자유로워져 준비 큐에 있는 다음 프로세스를 진행
2. 현재 실행 중인 프로세스의 실행 시간이 규정 시간량보다 긴 경우

OS가 인터럽트하면, 중단된 프로세스의 레지스터들은 프로세스의 PCB에 저장하고 프로세스는 준비 큐의 마지막 위치에 입력된다. 그리고 스케줄러는 준비 큐에서 다음 작업을 가져와 실행한다.

 

 

라운드 로빈 스케줄링 예

규정 시간을 5로 설정

• P1 은 처음 5만큼의 시간을 실행한 후 아직 5가 남아 있지만 다음 프로세스 작업 그룹에 밀려 P2 가 프로세서를 선점하여 실행한다.
• P2 역시 5만큼의 시간을 실행한 후 P3 에 프로세서를 넘겨준다.
• P3 역시 5만큼의 시간을 실행한 후 P4 에 프로세서를 넘겨준다.
• P4 는 실행을 완료한 후 P5, 앞서 종료되지 않은 P1, P2, P3, P5 순으로 프로세스를 실행한다.

위 예시에서는 규정 시간량을 초과하여 프로세서를 할당하는 프로세스는 없다.

 

프로세스가 규정 시간량보다 많은 실행 시간을 요청할 때 스케줄러는 프로세스를 중단시키고 다음 프로세스로 대치하므로 라운드 로빈 스케줄링은 선점 스케줄링이다.

 

그리고 준비 큐에 프로세스가 n 개 있고 규정 시간량이 q 이면, 각 프로세스는 최대로 q 시간 단위로 프로세서 시간의 1/n 을 얻는다. 각 프로세스는 자신의 다음 규정 시간량을 할당 할 때까지 (n-1) x q 시간 이상을 대기하지 않는다.

 

예를 들어 규정 시간량이 20인 프로세스 5개가 있다면, 각 프로세스는 100마다 20의 시간 할당을 받는다. 따라서 라운드 로빈 스케줄링의 성능은 규정 시간량의 크기에 큰 영향을 받는다.

 

 

어떤 값이 최적의 규정 시간량일까?

대부분의 대화식 프로세스는 규정 시간량보다 짧은 시간을 요청한다. 대화식 프로세스는 실행을 시작할 때 입출력 요청을 할 정도만 프로세서를 잠시 사용한 후 대기한다. 그리고 해당 프로세스는 다음 프로세스에 프로세서를 양보한다. 

 

따라서 규정 시간량이 입출력까지의 계산 시간보다 커야 입출력 활용도를 극대화하고 대화식 프로세스에 비교적 빠르게 반응할 수 있다.

• 규정 시간량이 매우 크면 프로세스는 작업을 완료할 충분한 시간을 얻고 라운드 로빈이 선입선처리 방법으로 변한다. 즉, 작업 시간이 긴 프로세스들 때문에 작업 시간이 짧은 프로세스들이 대기하고 평균 대기시간은 길어진다.
• 규정 시간량이 매우 작으면( 예 : 1 μsec) 라운드 로빈을 프로세서 공유(processor sharing) 라고 하며, 이론적으로 마치 n 개의 프로세스가 실제 프로세서 속도의 1/n 속도로 실행하는 것처럼 보인다.

 

그렇다면 어떤 값이 최적의 규정 시간량일까?

• 물론 규정 시간량의 크기는 시스템 특성 및 오버헤드, 프로세스에 따라 다르다.
• 라운드 로빈 스케줄링에서는 프로세서 중심 프로세스에서 대화식 프로세스를 지원한다. 
• 그래서 선점을 이용하여 대화식 프로세스가 도착할 때 적절한 시간에 반응을 보여 주도록 보장하는 것이 프로세스들의 규정 시간량 차이보다 중요하다.

 

그런데 소프트웨어 측면에서 보면 다른 문제가 있다.

• 규정 시간량 만큼 수행하고 프로세서를 다른 프로세스에 넘겨줄 때 전 프로세스의 레지스터들을 저장해야 한다.
• 그리고 수행할 프로세스의 레지스터는 시스템에 적재되는 문맥 교환 때문에 발생하는 오버헤드가 너무 크면 시스템 성능이 감소하고, 의미 있는 일을 수행하기보다는 대부분의 시간을 문맥 교환에 사용한다.

※ 참고

프로세스에 할당하는 기본 규정 시간량

리눅스의 프로세스에 할당하는 기본 규정 시간량의 크기는 100밀리초이다. 반면에 윈도루 XP 의 프로세스에 할당하는 기본 규정 시간량의 크기는 20 밀리초이다. 리눅스는 프로세스의 우선순위와 동작에 따라, 윈도우 XP 는 전면 작업 도는 후면 작업에 따라 기본 규정 시간량의 크기가 변한다.

 

문맥 교환 시간이 라운드 로빈 스케줄링에 미치는 영향

• 규정 시간량이 작을 수록 문맥 교환 횟수는 많아지므로 문맥 교환에 소요하는 시간보다 규정 시간량을 충분히 크게 해야 한다.
• 문맥 교환 시간이 시간량의 10% 정도라면 프로세서 시간의 10% 정도를 문맥 교환에 소요한다고 보면 된다.

 

 

규정 시간량에 따른 반환 시간의 변화

• 아래 그림과 같이 한 프로세스 집합의 평균 반환시간은 규정 시간량의 크기가 증가하더라도 반드시 개선되지 않는다.
• 하지만 대부분의 프로세스가 단일 규정 시간량 안에 마칠 수 있다면 평균 반환시간은 좀 더 개선할 수 있다.

 

예를 들어

• 실행 시간이 10인 프로세스 3개가 있고 규정 시간량이 1시간으로 주어졌다면 평균 반환 시간은 29 [= (28 + 29 + 30)/3] 가 된다.
• 그러나 규정 시간이 10이라면 평균 반환시간은 20 [= (10 + 20 + 30)/3] 이 된다.

아래 그림과 같이 규정 시간량이 작으면 문맥 교환을 많이 하므로 평균 반환시간이 좋지 않다.

 

 

 

라운드 로빈 스케줄링의 장점과 단점

 

 

 

다단계 큐(MLQ, MultiLevel Queue) 스케줄링

---

• 다단계 큐(MLQ, MultiLevel Queue) 스케줄링은 각 작업을 서로 다른 묶음으로 분류할 수 있을 때 사용한다.
  • 예를 들어, 작업을 전면 작업(포그라운드 태스크, foreground task)과 후면 작업(백그라운드 태스크, background task) 으로 분류한다면 두 유형의 요청 반응시간은 다르므로 서로 다르게 스케줄링해야 한다.
    더욱이 전면 작업은 후면 작업에 비해 우선순위가 높을 때가 많다
• 준비 상태 큐를 종류별로 여러 단계로 분할해둔다. 그리고 작업을 메모리의 크기나 프로세스의 형태에 따라 특정 큐에 지정한다. 각 큐는 자신만의 독자적인 스케줄링을 갖는다.
  • 예를 들어, 전면 작업과 후면 작업을 분할된 큐에 지정하면 전면 작업 큐는 라운드 로빈 스케줄링하고, 후면 작업 큐는 선입선처리 스케줄링할 수 있다.
• 또 큐 사이도 스케줄링해야 하는데, 이는 고정된 선점 우선순위 스케줄링이다. 예를 들어, 전면 작업 큐는 후면 작업 큐보다 절대적인 우선순위를 가질 수 있다.

각 큐는 순서대로 절대적인 우선순위를 가진다. 우선순위가 높은 큐가 모두 비어 있기 전에는 낮은 우선순위 큐에 있는 프로세스를 실행할 수 없다.

 

예를 들어,

• 시스템 프로세스, 대화식 프로세스, 대화식 편집 프로세스 큐가 모두 비어 있어야 일괄 처리 프로세스를 실행한다.
• 일괄 처리 프로세스를 실행하는 동안에 대화식 편집 프로세스가 준비 큐에 들어오면, 일괄 처리 스로세스는 프로세서를 반납해야 한다.

 

또 큐 사이에 시간을 나눠 사용할 수도 있다. 각 큐는 프로세서 시간의 일정량을 받아서 큐에 있는 프로세스들을 스케줄링할 수 있다.

 

예를 들어,

• 전면 작업 큐는 자신의 프로세스 사이에 서 라운드 로빈 스케줄리을 하는 데 프로세서 시간의 80%를 할당하고,
• 후변 작업 큐는 선입선처리 방법으로 프로세스를 스케줄링하는데 프로세서 시간의 20%를 할당할 수 있다.

 

다단계 큐 스케줄링의 장점과 단점

 

 

다단계 피드백 큐(MLFQ, MultiLevel Feedback Queue) 스케줄링

---

다단계 큐 스케줄링의 단점

• 다단계 큐 스케줄링은 작업이 시스템에 들어가면 한 큐에서만 고정되어 실행한다. 즉, 작업을 다른 큐로 옮기지 않는다.
  • 예를 들어, 전면 작업과 후면 작업에 독립된 큐가 있어도 작업을 한 큐에서 다른 큐로 옮기지 않는다. 작업은 전면 작업과 후면 작업의 성질을 바꿀 수 없기 때문이다.
• 이 방법은 스케줄링 부담이 적다는 장점이 있느나 융통성이 떨어진다는 단점이 있다.

다단계 피드백 큐 (MLFQ, MultiLevel Feedback Queue)

• 작업이 큐 사이를 이동할 수 있다. 이때는 프로세서 버스트의 특성에 따라 분리한다.
  • 예를 들어 어떤 작업이 요청하는 프로세서 실행 시간이 너무 길면(프로세서 중심 프로세스) 작업을 낮은 단계 큐로 옮긴다.
  • 그리고 입출력 중심 작업과 전면 작업은 옾은 우선순위 큐에 놓고, 프로세서 중심 프로세스는 낮은 우선 순위 큐에 놓는다.

• 프로세서 퍼스트 시간이 작은 프로세스에 높은 우선순위를 주어 일찍 종료시키고 다음 입출력 버스트를 실행하도록 한다.
• 이는 입출력 위주의 프로세스에 우선권을 주는 방법이라고 할 수 있다.
• 그러나 높은 우선 순위의 큐가 완전히 비어야 낮은 우선순위의 준비 큐에 있는 작업을 실행할 수 있기 때문에 낮은 우선순위 큐에 입력된 작업이 무한정 기다리는 기아 상태에 빠질 수 있다는 문제가 있다.
  • 이때는 특정 큐에서 오래 기다린 프로세스를 우선순위가 높은 큐로 이동
  • 프로세서 점유 시간이 긴 작업을 우선순위가 낮은 큐로 이동
• 기아 상태를 예방하는 에이징(aging) 방법을 활용한다.

 

프로세스가 더 낮은 수준의 큐로 옮겨 갈 때 스케줄러는 해당 프로세스의 규정 시간량을 증가시켜 프로세스가 더 오래 작업할 수 있도록 한다.

 

다단계 피드백 큐 스케줄링 동작 방식

• 큐가 4개인 다단계 피드백 큐 스케줄링, 각 큐의 번호는 0~3으로 지정
• 처음에 스케줄러는 큐 0에 있는 작업을 실행
• 큐 0이 다 끝나면 큐 1의 작업을 실행
• 동일한 방법으로 큐 0과 큐 1이 비어 있을 때만 큐 2에 있는 프로세스들을 실행
• 큐 1에 도착한 프로세스는 큐 2에 있는 프로세스를 선점하고, 큐 1에 있는 프로세스는 큐 0에 도착한 프로세스가 선점

• 준비 큐로 들어오는 프로세스는 큐 0에 입력
• 큐 0에 있는 프로세스에는 규정 시간량 2가 주어짐.
• 프로세스가 주어진 시간 안에 끝나지 않는다면 큐 1의 끝으로 이동
• 큐 0이 비어있다면, 큐 1의 앞에 있는 프로세스에 규정 시간량 4가 주어짐
• 이 프로세스가 규정 시간 안에 완료하지 않는다면 선점되어 큐 2로 이동
• 큐 0과 큐 1이 비어 있을 때만 큐 2에 있는 프로세스에 규정 시간량 16이 주어짐.

이런 과정으로 마지막 큐 3은 선입선처리(FCFS) 방법으로 실행된다.

 

 

다단계 피드백 큐 스케줄링은 프로세서 버스트가 2 이하(실행 시간이 2이하) 인 프로세스에 최고의 우선순위를 부여한다.

최고의 우선순위를 부여받은 프로세스는 프로세서를 할당받아서 프로세서 버스트를 끝내고 다음 입출력 버스트로 이동한다. 4 이상 16 이하인 규정 시간량이 필요한 프로세스들은 규정 시간이 더 짧은 프로세스들보다 낮은 우선순위를 받지만, 역시 서비스를 빨리 받는다. 규정 시간이 긴 프로세스들은 자동으로 큐 3으로 이동하며, 큐 1과 큐2의 프로세서 주기에 여유가 생기면 선입선처리 방법으로 처리된다.

 

 

다단게 피드백 큐 스케줄링의 정의 방법

• 큐(quque) 수
• 각 큐에 대한 스케줄링
• 작업을 좀 더 높은 우선순위의 큐로 격상시키는 시기를 결정하는 방법
• 작업을 좀 더 낮은 우선순위의 큐로 격하시키는 시기를 결정하는 방법
• 프로세스들이 어느 큐에 들어갈 것인지 결정하는 방법
• 프로세스가 서비스를 받는 시기를 결정하는 방법

 

다단계 피드백 큐 스케줄링은 프로세서 스케줄링 중 가장 일반적이다. 그리고 이 정의들은 설계 중인 특정 시스템에 맞게 적용할 수 있다.

 

단점은 최상의 스케줄링을 정의하는 요소를 평가하는 방법이 필요하다는 것이다. 이는 아주 일반적인 방법이면서 가장 복잡한다.

 

 

 

다단계 피드백 큐와 라운드 로빈 스케줄링의 비교

• 동일한 시간(t=0) 에 프로세서 중심의 프로세스 시스템이 3개 있다고 가정
• 시스템은 각각 큐 1(1), 큐 2(2), 큐 3(4) 의 규정 시간량을 할당. 이때 라운드 로빈 스케줄링의 규정 시간량은 1
• (b) 는 다단계 피드백의 간트 차트

 

다단계 피드백 큐의 장점과 단점

 

 

HRN(Highest Response-ratio Next) 스케줄링

---

• 최소작업 우선(SJF) 스케줄링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평 등을 보완
• 비선점 스케줄링이며 우선순위 스케줄링의 또 다른 예
• 선입선처리 스케줄링과 최소작업 우선 스케줄링의 약점을 해결하려고 제안
• 각 작업의 우선순위는 작업이 서비스를 받을 시간 뿐만 아니라 서비스를 기다린 시간의 함수로 나타낸다.
• 일단 한 작업이 프로세서를 차지하면 작업을 종료할 때까지 실행된다.
• HRN 방법의 가변적 우선순위는 위 식에 따라 계산

• "서비스를 받을 시간" 이 분모에 있으므로 이 시간이 짧은 작업일 수록 우선순위가 높다.
• "대기한 시간"이 분자에 있으므로 이 시간이 긴 작업일수록 우선순위가 높다.
• 시스템의 반응시간은 아래와 같이 나타낼 수 있다.

 

HNR 스케줄링의 예

간트 차크 작성을 위한 우선순위 계산

• 시간 0일 때 큐에는 P1 밖에 없으므로 P1 을 시작
• 이어서 시간 10일 때 P1이 실행을 마친 후 각 프로세스의 우선순위는
  • P2 = (28 + 9) / 28 = 1.3
  • P3 = (6 + 8) / 6 = 2.3
  • P4 = (4 + 7) / 4 = 2.75
  • P5 = (14 + 6) / 14 = 1.4 
• 이므로 P4의 우선순위가 가장 옾아 P4 를 실행
• P4 가 완료된 시간 14일 때 각 프로세스의 우선순위는 
  • P2 = (28 + 13) / 28 = 1.4
  • P3 = (6 + 12) / 6 = 3
  • P5 = (14 + 10) / 14 = 1.7 
• 이므로 p3 의 우선순위가 가장 높아 P3을 실행
• P3 이 완료된 시간 20 일 대 각 프로세스의 우선순위는 
  • P2 = (28 + 19) / 28 = 1.7
  • P5 = (14 + 16) / 14 = 2.1
• 이므로 P5 가 실행된 후 완료된 시간 34일 때 마지막 P2를 실행

 

HRN 스케줄링의 잠점과 단점

 

 

 

다중 프로세서 스케줄링

---

• 프로세서가 여러 개이면 스케줄링 문제는 복잡해진다.
• 문제는 프로세서(처리기) 들의 현태가 다를 수 있다는 것이 중요하다.

여기서 강결합 다중 처리기 시스템을 중심으로 아중 프로세서 스케줄링을 살펴보자.

 

각 프로세서에는 독자적인 큐와 독자적인 스케줄링이 있으므로 프로세서가 다르면 가능한 선택의 경우 수가 상대적으로 제한된다. 작업은 프로세스의 구조에 따라 특정하게 지정하며, 특정 프로세서로 실행해야 한다.

• ex. 작업의 할당할 때 프로세스 구조를 고려하지 않는 것은 IBM 시리즈/1 에서 실행이 불가능한 Vax 어셈블리어로 작성된 프로그램을 IBM 시리즈/1 에서 억지로 실행시키려 하는 것과 같다.

따라서 프로세서들은 스스로 자신을 분류하고 스케줄링해야 한다.

 

하나의 시스템에 종류가 같은 프로세서가 여러 개이면 부하 공유가 발생한다. 이것은 각 프로세서에 서로 독립된 준비 큐를 제공하도록 하여 방지할 수 있다.

• 장점 :  프로세서를 모든 프로세스에 한 번만 할당하기 때문에 스케줄링 오버헤드가 적다
• 단점 :  어떤 프로세서는 큐가 비어 아무 일도 하지 않는 반면에, 다른 프로세서는 처리할 작업이 준비 큐에 가득 차 매우 바쁠 수 있다

 

이런 현상을 방지하려면 공동의 준비 큐를 사용하여 모든 작업이 이용 가능한 프로세서 큐로 가도록 스케줄링해야 한다.

그러면 프로세스가 메모리에 적재되는 동안 다른 프로세서에서 작업을 실행할 수 있다.

 

강결한된 공유 메모리 구조에서 모든 프로세서는 모든 프로세스에 대한 문맥 정보를 이용할 수 있다는 장점이 있다. 따라서 프로세스의 스케줄링 비용은 프로세스가 스케줄링되는 프로세서에 독립적이다. 

 

여기서는 두 가지 스케줄링 방법을 사용한다.

1. 프로세서 자신이 스스로 스케줄링한다. 각 프로세서는 공통의 준비 상태 큐에서 실행할 프로세스 하나를 선택한다.
   • 프로세서 2개가 같은 프로세스를 선택하지 않도록 해야 하고, 프로세스가 큐에서 누락되지 않도록 해야 한다.
   • 이때 앞서 설명한 단일 프로세서 스케줄링(우선순위, 순환 할당 등) 방법을 활용할 수 있으나 오히려 스케줄링이 복잡하여 오버헤드를 증가시킬 수 있다.
2. 비대칭 다중 처리(AMP, Asymmetric MultiProcessing) 는 한 프로세서를 다른 모든 프로세서의 스케줄러로 지정하고, 주종(Master / Slave) 구조를 보인다.
   • 이 구조에서 OS의 핵심 커널 기능들은 특정 프로세서에서 수행하고, 다른 프로세서들은 사용자 프로세스만 수행한다.
   • 주 프로세서는 프로세스들을 스케줄링하여 프로세스를 활성화시킨다.
   • 종 프로세스에 입출력 호출 증의 서비스가 필요하면 주 프로세서에 요청하여 서비스의 처리를 기다린다.
   • 이런 방법은 앞서 다룬 단일 프로세서 다중 프로그래밍 방법과 비슷하며, 자원 충돌 문제는 주 프로세서가 메인 메모리와 입출력 자원들을 제어하기 때문에 간단하게 해결할 수 있다.
   • 그러나 주 프로세서의 오류는 시스템 전체를 정지시키며, 주 프로세서의 과중한 오버헤드는 성능의 병목 지점이 될 수 있는 문제점이 있다.

 

 

 

스레드 스케줄링

---

• 스레드를 이용하여 응용 프로그램을 동일한 주소 공간에서 동시에 실행하고 협동하는 스레드들로 구현할 수 있다는 것이다. 즉, 입출력과 프로세서 처리를 중첩할 수 있다.
• 스레드 문맥 교환은 프로세스 문맥 교환보다 오버헤드가 적게드므로 응용 프로그램 하나의 여러 스레드를 동시에 다른 프로세서에서 실행한다면 성능을 현저하게 향상시킬 수 있다.
• 그러나 스레드 간의 많은 상호작용을 요청하는 응용 프로그램에서는 성능에 큰 영향을 줄 수 있다.

 

다중 프로세서 스레드 스케줄링과 프로세서 할당에 대한 일반적인 방법들

 

부하 공유 (load sharing)

• 프로세서를 특정 프로세스 하나에 할당하지 않고 전역 큐에서 프로세서를 유지한다.
• 쉬고 있는 프로세스는 전역 큐에서 스레드 한개를 선택한다.
• 단일 프로세서 환경에서 사용한 방법을 그대로 채택한 가장 단순한 방법

 

 

 

갱(gang) 스케줄링

• 관련된 스레드의 집합을 일대일(1 : 1) 대응 원칙에 따라 프로세서 집합에서 동시에 실행할 수 있도록 스케줄링하는 방법
• 단일 프로세스에 속한 스레드들을 동시에 스케줄링한다.
• 응용 프로그램의 어떤 부분을 실행 준비하는 동안에 다른 부분은 실행하지 못할 때 성능이 심각하게 떨어지는 응용 프로그램에서 사용한다.
  • ex. 스레드 한 개를 실행하다가 같은 프로세스의 다른 스레드와 동기화해야 한다고 가정
  • 프로세스의 다른 스레드가 실행되지 않고 준비 큐에 있다면, 첫 번째 스레드는 다른 스레드가 다른 프로세서에서 실행될 수 있도록 프로세스를 교환할 때까지 실행을 지연
• 따라서 밀접하게 관련된 프로세스들이 병렬로 실행된다면 동기화 대기 및 프로세스 문맥 교환의 횟수를 최소화하여 성능을 향상시킬 수 있다.
• 또 한 번의 스케줄링 결정이 다수의 프로세서와 프로세스에 영향을 주기 때문에 스케줄링 오버헤드를 줄일 수 있다.

※ 참고

동기화 

운영체제에서 동기화는 여러 프로세스나 스레드 간에 작업을 조정하고 동시에 실행하는 메커니즘이다. 동기화는 공유된 리소스에 대한 접근을 조절하고 충돌이나 데이터 일관성 문제를 방지하는 데 사용된다.

 

동기화는 주로 다음과 같은 상황에서 필요하다

 

공유 데이터 접근: 여러 프로세스 또는 스레드가 공유된 데이터에 접근하는 경우 동기화가 필요하다. 동시에 여러 프로세스 또는 스레드가 데이터를 수정하면 예측할 수 없는 결과가 발생할 수 있다. 동기화 메커니즘을 사용하면 데이터 접근을 조정하여 데이터 일관성을 유지할 수 있다.

 

상호 배제: 한 프로세스 또는 스레드가 특정 리소스를 사용 중인 경우, 다른 프로세스 또는 스레드는 그 리소스에 접근하지 못하도록 해야 한다. 상호 배제 메커니즘은 여러 프로세스 또는 스레드가 공유된 리소스를 순차적으로 사용하도록 보장한다.

 

조건부 실행: 여러 프로세스 또는 스레드가 특정 조건을 충족할 때까지 대기하고, 조건이 충족되면 실행되어야 할 때 동기화가 필요하다. 예를 들어, 한 스레드가 데이터를 생성한 후 다른 스레드가 해당 데이터를 소비해야 할 때, 소비 스레드는 데이터가 생성될 때까지 대기해야 한다.

 

동기화를 구현하기 위해 여러 동기화 메커니즘이 사용될 수 있다. 대표적인 동기화 메커니즘으로는 뮤텍스(mutual exclusion), 세마포어(semaphore), 조건 변수(condition variable) 등이 있다. 이러한 메커니즘을 사용하여 프로세스나 스레드 간의 상호 작용을 조정하고, 동시에 실행되는 작업들 사이에서 일관성과 안정성을 유지할 수 있다.

 

 

전용 프로세서 할당

• 부하 공유와는 반대로 스레드들을 실행 전담 프로세서에 할당하여 정의된 스케줄링을 제공하는 방법
• 각 프로그램은 실행되는 동안 프로그램의 스레드 수와 동일한 수의 프로세스를 할당받기 때문에 프로세스가 낭비될 수 있다.
• 한 응용 프로그램의 스레드를 다른 스레드와 동기화나 입출력 대기 때문에 보류한다면 그 스레드의 프로세서는 계속 쉬게 되어 프로세서들의 다중 프로그래밍이 어렵다.
• 따라서 활성화된 스레드 수를 시스템의 프로세서와 동일한 수로 제한하여 효율성을 높이는 등 프로세서의 합리적인 이용을 지원해야 한다.

 

 

동적 스케줄링

• 프로그램의 스레드 수는 실행 도중 변할 수 있다.
• 동적 스케줄링은 프로세스의 스레드 수를 동적으로 변경하여 OS 가 시스템 이용률을 높일 수 있도록 부하 조정을 허용한 방법이다.
• OS 는 작업 간의 프로세서들을 분할하는 역할(프로세서 할당)을 하여 각 작업을 스레드들에 매핑시켜 프로세스에 할당된 프로세서들을 사용한다.
• 실행 중인 프로세스를 선점할 때, 어느 스레드를 일시중지할 것인지는 각 응용 프로그램의 실행 라이브러리 루틴들이 결정한다.
• 물론 이 과정이 모든 응용 프로그램에 적합하지 않을 수 있지만, 어떤 응용 프로그램은 OS 의 이런 특별한 장점을 이용할 수 있다.

 

 

이 중 갱 스케줄링과 전용 프로세서 할당은 프로세서 단편화 문제를 회피하는 방법이다.

 

전용 프로세서 할당은 갱 스케줄링과 같이 프로세서를 효율적으로 할당하여 스케줄링 문제를 해결한다.

 

즉, 주어진 시간에 얼마큼 프로세서를 하나의 프로세스에 할당하느냐가 관심사이다. 이는 프로세스의 스케줄링 문제보다는 메모리 할당과 비슷하여 주어진 시간에 몇 개의 페이지 프레임을 프로세서에 할당할 것인가 하는 문제와 비슷한다.

※ 참고

메모리 단편화 현상과 같이 대기하고 있는 프로세스의 요청을 받기에는 충분하지 않아 프로세서를 할당할 수 없는 상황을 프로세서 단편화라고 한다.

 

 

 

---

참고

• 운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미