[Computer Science] 운영체제 - CPU 스케줄링, 문맥교환(Context-switching)

CPU 스케줄링이란?

 

 

 

어떤 스레드가 어떤 우선순위로 CPU를 사용할 것인지 결정하고 수행하는 과정

즉, 스레드가 작업을 처리하기 위해 중앙처리를 할당 받는 정책을 계획하고 처리하는 방식

​

목적

• CPU 효율성 향상
• 응답시간의 최소화를 통해 시스템 내의 자원 활용을 최대화
• 특정 프로세스 실행의 시한성 보장
• 공평성, 예측성 향상 및 급격한 성능 저하 방지

​

1. 장기 스케줄러

• 어느 작업을 등록하여 시스템 자원을 이용할 수 있게 할 것인지 결정

2. 중기 스케줄러

• 어느 프로세스에게 메모리를 할당할 것인지를 결정

3. 단기 스케줄러

• 준비 상태의 프로세스들 중 어떤 것에 CPU를 할당할 것이지를 결정

​

스케줄링 방식​

# 선점형(Preemptive) 스케줄링

- 선점형 스케줄링 방식은 한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 CPU를 차지할 수 있게 하는 스케줄링 방식 (빠른 응답시간을 요구하는 시분할 시스템에 유용)

특징 : 오버헤드를 초래할 수 있으며, 문맥교환이 자주 발생할 수 있음

​

1.라운드 로빈(Round Robin)

- 각 프로세스는 같은 크기의 CPU 시간을 할당하는 방식

- 시분할 방식에 효과적, 할당시간의 크기가 중요하다. 할당시간이 크면 FCFS와 같게 되고 작으면 문맥교환이 자주 발생하게 된다.

​

2. SRT(Short Remaining Time)

- 수행 시간이 가장 짧은 프로세스를 먼저 수행하는 방식이다. 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비큐에 생기면 언제라도 실행중인 프로세스가 선점 됨

긴 작업은 SJF보다 대기 시간이 길다.

​

3. 다단계 피드백 큐(multilevel feedback queue)

- 준비 큐를 여러 단계로 배치하고 각 단계의 제한 시간을 점차 늘려서 배치하는 방식이다. 각 단계의 큐는 FIFO형태로 이동하고, 작업이 끝나거나 입출력, 다른 사건 발생 등으로 인해 CPU를 양도하는 경우에 큐잉 네트워크(한 개 이상의 대기 큐들이 서로 연결되는 큐)를 떠나게 된다. 만일 프로세스가 CPU를 자발적으로 양도하기 전에 시간 할당량이 긑나면 그 프로세스는 다음 번 낮은 수준의 큐로 배치된다.

 

 

https://terms.naver.com/entry.naver?docId=830028&cid=42344&categoryId=42344

​

 

# 비선점형(nonpreemptive) 스케줄링

- 한 프로세스가 CPU를 할당 받으면 그 프로세스의 수행이 마칠 때까지 점유하는 방식이며 다른 프로세스는 CPU를 사용할 수 없다.

특징 : 짧은 작업을 수행하는 프로세스가 긴 작업이 종료될 때까지 기다려야 한다. 모든 프로세스들에게 공정하고 응답시간의 예측이 가능하다.

​

1. 우선 순위(Priority)

- 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방식이다. 각 프로세스에게 우선순위가 주어지며, CPU는 가장 우선순위가 높은 프로세스에게 CPU를 할당하며 우선순위가 동일할 경우 선입 선처리(FCFS)로 처리 된다.

(1) 정적(static) 우선순위 방법 : 상황 변화와 상관없이 실행 중 우선순위를 바꾸지 않는다. 구현이 쉽고 오버헤드가 적다.

(2) 동적(dynamic) 우선순위 방법 : 상황 변화에 적응하여 우선순위가 변경된다. 구현이 복잡하고 오버헤드가 많다. (시스템의 응답속도를 증가시켜 효율적이다.)

 

우선순위는 내부적 요인과 외부적 요인으로 구분된다.

• 내부적 우선순위 : 기계내부의 성능에 영향을 미치는 작업처리의 제한 시간, 주기억 장소에 대한 요구량, 사용되는 파일의 수, 평균 CPU 버스트에 대한 평균 I/O 버스트의 비율 등
• 외부적 우선순위 : 기계외적 요인으로 인한 정책적 배려로 결정된다. 단점으로는 우선순위가 높은 작업이 계속적으로 들어오게 될 때는 우선순위가 낮은 작업은 무한정 기다리게 되는 무한 정지 이거나 기아 상태가 될 수 있다.

​

2. FIFO(First Input First Out) / FCFS

- 프로세스가 대기큐에 도착하는 순서에 따라 CPU를 할당하며, 프로세스가 CPU를 차지하고 난 후에는 그 프로세스가 CPU를 반환할 때까지 다른 프로세스가 선점할 수 없게 된다.

- 특징 : 일괄처리 시스템에서 주로 사용, 작업 완료 시간을 예측하기 용이하지만, 빠른 응답을 요구하는 대화식 시스템에서는 부적절하며, 단독으로 사용되는 경우가 없다. 실제로는 다른 스케쥴링 알고리즘에 보조적으로 사용되는데, 예를 들어 우선순위 스케쥴링 기법에서 같은 우선순위인 경우에 FCFS 기법을 보조적으로 사용한다.

​

3. HRN(Highest Response Ratio Next)

- 대기중인 프로세스 중 현재 응답률(response ratio)이 가장 높은 것을 선택한다. 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법이다. 짧은 작업이나 대기시간이 긴 작업은 우선순위가 높아진다. (response ratio = (대기시간 + 서비스 시간) / 서비스 시간)

​

4) SJF(Shortest Job First)

- 준비 큐 내의 작업 중 수행시간이 가장 짧은 것을 먼저 수행한다. FCFS보다 평균 대기 시간(average waiting time)이 감소하지만 긴 작업은 무한연기 가능성이 있다. 각 프로세스에서 CPU 버스트 길이를 비교하여 CPU가 이용 가능해지면 가장 작은 CPU 버스트를 가진 프로세스를 할당한다.

(프로세스 집합에 대해서 평균대기 시간이 최소가 되는 최적 알고리즘)

​

문맥교환

쓰레드에 의한 문맥교환(Context Switching)의 장점

프로세스 중심 시스템에서 프로그램이 단일 프로세스로 생성되어 실행되면 하나의 실행점(Execution)만이 존재함으로 단일 프로세스 내에서는 병행 처리가 불가능하다. 만약 프로그램이 여러 개의 프로세스로 생성되면 각 프로세스 마다 동일한 많은 정보들이 중첩돼 비효율적이다.

단일 프로세스를 다수의 스레드로 생성하여 병행성을 증진하고, 실행환경을 공유시켜 문맥 교환 등의 오버헤드를 줄여 운영 체제의 성능을 개선할 수 있다.