CPU는 프로그램의 기계어 명령을 실제로 수행한느 컴퓨터 내의 중앙처리장치.

• 레지스터가 현재 cpu에서 수행할 코드의 메모리 주소값을 가지고 있게 됨
• 한 시스템 내에 하나 밖에 없기에 매우 효율적으로 관리되어야 하는 자산

기계어 명령

일반 명령

• cpu 내에 수행되는 명령
  • add : 레지스터 내에 있는 두 값을 더해 레지스터에 저장하는 명령
• 접근을 필요로 하는 명령
  • load : 메모리에 있는 데이터를 cpu로 읽어옴
  • store : cpu에서 계산된 결과값을 메모리에 저장

특권 명령

• 입출력을 동반하는 명령
• 오랜 시간 소요됨

💡 사용자 프로그램이 수행되는 과정은 cpu작업과 I/O 작업의 반복으로 구성됨.

CPU 버스트

• cpu를 직접 가지고 빠른 명령을 수행하는 일련의 단계
• io 한 번 수행한 후 다음 번 i o를 수행하기까지 직접 cpu를 가지고 명령을 수행하는 일련의 작업

I/O 버스트

• I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
• I/O 작업이 요청 된 후 완료되어 다시 cpu 버스트로 돌아가기까지 일어나는 일련의 작업을 말함

CPU 바운드 프로세서

• cpu 버스트가 길게 나타나는 프로세스
• cpu 작업에 소모하는 계산 위주의 프로그램

i/o 바운드 프로세서

• 사용자로 부터 인터렉션을 계속 받아가며 프로그램을 수행시키는 대화형 프로그램

프로세스들의 cpu 버스트 분포는 다수의 짧은 cpu 버스트와 소수의 긴 cpu 버스트로 구성됨

→ 다시 말해서 cpu를 한 번에 오래 사용하기보다는 잠깐 사용하고 i/o작업을 수행하는 프로세스들이 많음

대화형 작업 → 사용자에 대한 빠른 응답이 중요함

cpu스케줄링 → cpu 버스트가 짧은 프로세스에게 우선적으로 cpu를 사용할 수 있도록 하는 스케줄링이 필요함

💡 cpu 스케줄링 시 i/o 바운드 프로세스의 우선순위를 높여주는 것이 바람직 함

• 응답성 + 효율성
• i/o 장치의 이용률이 올라감
• cpu 바운드 프로세스에게 먼저 cpu를 할당하면 그 프로세스가 cpu를 다 사용할 때 까지 i/o 장치도 그 시간 동안 작업을 수행하지 않는 휴면 상태가 됨

1. cpu 스케줄러

💡 cpu스케줄러는 준비 상태에 있는 프로세스들 중 어떠한 프로세스에게 cpu를 할당할지 결정하는 운영체제의 코드

cpu 스케줄링이 필요한 경우

1. 실행 상태에 있던 프로세스가 i/o 요청 등에 의해 봉쇄 상태로 바뀌는 경우
2. 실행 상태에 있던 프로세스가 타이머 인터럽트 발생에 의해 준비 상태로 바뀌는 경우
3. (io → 봉쇄 상태) → 준비 상태
4. 실행 상태에 있는 프로세스가 종료되는 경우

비선점형

• cpu를 획득한 프로세스가 스스로 cpu를 반납하기 전까지 cpu를 빼앗기지 않는 방법1 , 4

선점형

• cpu를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 스케줄링 방법 2, 3
• 타이머 인터럽트 발생

2. 디스패처

💡 cpu를 할당받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제의 코드

• 프로세스의 문맥을 그 프로세스의 PCB에 저장
• 새롭게 선택된 프로세스의 문맥을 PCB로부터 복원
• 그 프로세스에게 CPU를 넘김

디스패치 지연시간

• 하나의 프로세스를 정지시키고 다른 프로세스에게 cpu를 전달하기 까지 걸리는 시간
• 디스패치 지연시간의 대부분은 문맥교환 오버헤드에 해당됨

3. 스케줄링 성능 평가

시스템 관점

이용률

• 전체 시간 중에서 cpu가 일을 한 시간의 비율을 나타냄
• cpu가 일을 하지 않고 휴면(idle) 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표가 됨

처리량

• 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지 (cpu 버스트를 완료한 프로세스의 개수)
• 주어진 시간에 더 많은 프로세스들이 cpu 작업을 완료하기 위해서는 cpu 버스트가 짧은 프로세스에게 우선적으로 cpu를 할당하는 것이 유리

사용자 관점

소요시간

• 프로세스가 cpu를 요청한 시점부터 자신이 원하는 만큼 cpu를 다 쓰고 cpu 버스트가 끝날 때까지 걸린 시간,
• 준비 큐 기다린 시간 + 실제로 cpu를 사용한 시간의 합

대기시간

• cpu 버스트 기간 중 프로세스가 준비 큐에서 cpu를 얻기 위해 기다린 시간의 합
• 한 번의 cpu 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있다.

응답시간

• 프로세스가 준비 큐에 들어온 후 첫 번째 cpu를 획득하기까지 기다린 시간
• 타이머 인터럽트가 빈번히 발생할수록 각 프로세스가 cpu를 연속적으로 사용할 수 있는 시간이 짧아지므로 처음 cpu를 얻기까지 걸리는 시간은 줄어들게 되어 응답시간이 향상됨
• 대화형 시스템에 적합한 성능 척도

4. 스케줄링 알고리즘

1. 선입선출 스케줄링

💡 선입선출(First-Come First-served: FCFS) 스케줄링은 프로세스가 준비 큐에 도착한 시간 순서대로 cpu를 할당하는 방식을 말함

먼저 온 요청을 먼저 처리함

보기엔 합리적 but 비효율 적인 결과를 초래함

비효율 예시

• cpu 버스트가 긴 프로세스 하나가 짧은 프로세스 보다 먼저 도착
• 평균 대기시간 길어짐
• 이용률 까지 내려감

콘보이 현상(Convoy effect)

• cpu 버스트가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상

2. 최단작업 우선 스케줄링

💡 최단작업 우선(Shortest-job First:sjf) 스케줄링 알고리즘은 cpu버스트가 가장 짧은 프로세스에게 제일 먼저 cpu를 할당하는 방식

• 평균 대기시간을 가장 짧게 하는 최적 알고리즘

비선점형 방식

• 현재 cpu를 점유하고 있는 프로세스가 cpu버스트를 모두 수행 하고 cpu를 내어놓을 때까지 스케줄링을 하지 않음
• 준비 큐에 한꺼번에 도착하고 그 후에는 따로 도착하지 않는 환경에선 선점형과 동일한 결과를 냄

선점형 방식

• 현재 cpu에서 실행 중인 프로세스의 남은 cpu버스트 시간보다 더 짧은 cpu 버스트 시간을 가지는 프로세스가 도착할 경우 cpu를 빼앗게 된다.
• SRTF(Shortest Remaining Time First) 라고 불름
• 대기 시간을 최소화 하는 최적의 알고리즘이 됨

SJF 스케줄링 기법의 구현에서 현실적으로 어려운 부분은 프로세스의 cpu 버스트 시간을 미리 알 수 없다는 점

예측을 통해 cpu 버스트 시간을 구한 후 예측치가 가장 짧은 프로세스에게 cpu를 할당함

(n+1)번째 cpu 버스트의 예측시간

• a가 0 Tn+1 = Tn-1 고정된 값이 예측값으로 계속 사용
• a가 1 Tn+1 = Tn이 되어 바로 전에 사용한 cpu 버스트 시간을 예측값으로 사용됨

과거를 통해 미래를 예측하는 데 있어서 더 오래된 과거일수록 그 영향력이 적어지도록 반영하는 방식

기아현상

• cpu버스트가 짧은 프로세스가 계속 도착할 경우 프로세스 a는 영원히 cpu를 할당받지 못할 수도 있다.

3. 우선순위 스케줄링

💡 우선순위 스케줄링(priority scheduling)이란 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 cpu를 할당하는 방식.

• 우선순위 값이 작을수록 높은 우선순위를 가지는 것으로 가정함

• cpu버스트 시간을 우선순위 값으로 정의하면 우선순위 스케줄링은 sjf 알고리즘과 동일한 의미를 갖게됨

• 시스템과 관련된 중요한 작업을 수행하는 프로세스의 우선순위를 높게 부여하면 이러한 프로세스가 cpu를 빨리 할당받을 수 있게 할 수 도있음

비선점형, 선점형 방식으로 구현 할 수 있음

문제점

• 기아 현상이 발생할 수 있음
• 문제점을 해결하기 위해 노화(aging ) 기법을 사용

해결 방법: 노화(aging)기법

• 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 cpu를 할당받을 수 있게 해주는 방법

4. 라운드 로빈 스케줄링

💡 각 프로세스가 cpu를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되며, 이 시간이 경과하면 해당 프로세스로 부터 cpu를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 cpu를 할당함

준비큐의 제일 뒤에 가서 줄을 서 다음 번에 차례가 오기를 기다림

최대 할당시간(time quantum)

• 한번에 cpu를 연속적으로 사용할 수 있는 최대시간

할당시간이 너무 길면 라운드 로빈 스케줄링은 FCFS와 같은 결과를 나타냄

할당시간이 너무 짧으면 cpu를 사용하는 프로세스가 빈번하게 교체되어 문맥교환의 오버헤드가 커짐

• 일반적으로 할당시간을 수십 밀리초 정도의 규모로 설정함
• 대화형 프로세스가 cpu를 한 번 할당받기까지 지나치게 오래 기다리지 않을 정도의 시간 규모에 해당 됨
• 모든 프로세스는 (n-1)q시간 이내에 적어도 한 번은 cpu를 할당 받을수 있게됨

빠른 응답시간을 보장

cpu 버스트가 긴 프로세스에게 특별히 불이익이 가는 것도 아님

대기 시간이 그 프로세스의 cpu버스트 시간에 비례함

cpu를 적게 쓰는 프로세스는 대기시간도 짧아짐

sjf와 라운드 로빈 비교

sjf

• sjf 는 평균 대기시간 측면에서 가장 우수
• cpu버스트 시간이 짧은 프로세스에게만 유리함
• 긴 프로세스들은 전체 시스템의 성능을 향상시키기 위해 희생해야 함
• 형평성을 간과함
• sjf 스케줄의 경우 cpu버스트 시간이 1초인 프로세스의 소요시간이 10초라고 해도 cpu 버스트 시간이 10초인 프로세스는 이보다 더 짧은 cpu 버스트를 가진 프로세스가 계속 도착할 경우 무한정 기다리게 될 수 밖에 없음

라운드 로빈

• 라운드 로빈 스케줄링은 공정한 스케줄링 방식

• cpu버스트 시간을 매우 작은 단위로 나누어 실행함

• 자신이 cpu를 쓰고자 하는 양이 적으면 소요시간이 짧아짐

• cpu를 쓰고자 하는 양이 많으면 소요시간도 거기에 비례해서 길어짐

• cpu 버스트 시간이 1초인 프로세스 작업 10초 걸림

• cpu 버스트 시간이 10초 10배

• 그것의 10배 100초

• 평균적으로 위와 같은 결과

• 라운드 로빈은 할당시간을 너무 짧게 설정하면 문맥교환 오버헤드로 인해 전체 시간 중 일부는 cpu가 작업을 수행하지 못하기 때문

5. 멀티레벨 큐

프로세스들이 cpu를 기다리기 위해 한줄로 서는게 아니라 여러줄로 서는 것

• 어떤 줄에 서있는 프로스세르르 우선적으로 스케줄링 할 것인가
• 어느 줄에 세워야 할지 결정하는 메커니즘 필요

대화형 작업과 (interactive job)

그렇지 않은 작업

전위큐 (foreground queue)와 - 대화형 작업

후위 큐 (background queue

고정 우선순위 방식

• 큐에 고정적인 우선순위를 부여해 우선순위가 높은 큐를 먼저 서비스하고 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스하게 된다.
• 전위 큐에 있는 프로세스에게 우선적으로 cpu가 할당
• 큐가 비어 있는 경우에만 후위 큐에 프로세스에게 우선적으로 cpu가 할당됨

타임 슬라이스(time slice)바식

• 전위큐 80% 후위 큐 20% 할당

6. 멀티레벨 피드백 큐

여러 큐에 줄 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동이 가능 함
큐의 수, 각 큐의 스케줄링 알고리즘, 프로세스를 사이 큐로 승격시키는 기준

• 상위에 있는 큐일수록 우선순위가 높음

• 상위 2개의 큐는 각 할당시간이 5, 10 인 라운드 로빈 스케줄링 사용,

• 세번째 큐 FCFS 스케줄링 기법

• 우선순위가 가장 높은 큐에 줄을 섬

• cpu작업 시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 더욱 빠른 서비스가 가능하도록 함

• 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 cpu 작업에만 열중할 수 있도록 fcfs방식을 채택

7. 다중 처리기 쓰케줄링

• cpu가 여러 개인 시스템을 다중처리기 시스템(multi-processor system)이라고 부름

• 더욱 복잡함

💡 ex) 헤어 디자이너가 여러 명 있는 미용실에서 먼저 도착한 순서대로 헤어디자이너가 결정되어 서비스를 받는 것이 아니라, 특정 손님이 특정 헤어디자이너에게 서비스를 받겠다고 하는 경우와 유사

• 여러 줄로 줄 세우기를 하는 경우 일부 cpu에 작업이 편중되는 현상 발생할 수 있음

• cpu가 적절히 분산 되도록 하는 부하균형(load balancing) 메커니즘 필요로 함

대칭형 다중처리

• 각 cpu가 각자 알아서 스케줄링을 결정하는 방식

비대칭형 다중처리

• 하나의 cpu가 다른 모든 cpu의 스케줄링 및 데이터 접근을 책임지고 나머지 cpu는 거기에 따라 움직임

8. 실시간 스케줄링

• 시분할 시스템에서 작업의 처리가 빠를수록 좋지만 특정 시간 이내에 처리하지 못했다고 해서 심각한 상황이 발생하는 것은 아님

• 작업에 데드라인이 존재하지 않음

💡 실시간 시스템(real-time system)에서는 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야 한다.

실시간 시스템

• 미사일 발사
• 원자로 제어
• 시간을 정확히 지켜야 하는 시스템을 말함

연성 실시간 시스템

• 멀티미디어 스트리밍 시스템이 연성 실시간 시스템의 대표적인 예
• 시간당 정해진 프레임 수만큼의 서비스가 이루어지지 않으면 화면이 중간에 끊기는 현상이 발생하는 것이 그 예임
• 데드라인이 지켜지지 않았다고 해서 시스템이 붕괴되거나 치명적인 결과를 초래하지는 않음

EDF(Earlist Deadline First)

• 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 스케줄링

5. 스케줄링 알고리즘 평가

큐잉모델 (queueing model)

• 주로 이론가들이 수행하는 방식
• 확률분포를 통해 프로세스들의 도착률과 cpu의 처리율을 입력값으로 주로 복잡한 수학적 계산을 통해
• 각종 성능지표인 cpu의 처리량, 프로세스의 평균 대기시간 등을 구하게 됨

구현 및 실측(implementation & measurement)

• 이론가와 정방대인 구현가들이 수행할 수 있는 방식으로, 운영체제 커널의 소스 코드 중
• cpu 스케줄링을 수행하는 코드를 수정해서 커널을 컴파일 한 후 시스템에 설치하는 과정을 필요로함
• 동일한 프로그램을 원래 커널과 cpu스케줄러를 수정한 커널에서 수행시켜보고 실행시간을 측정

시뮬레이션(simulation)

• 프로그램의 cpu 요청을 입력값으로 넣어 어떠한 결과가 나오는지를 확인하는 방법
• 실제 시스템에서 추출한 입력값을 트레이스(trace) 함

트레이스

• 몇 초에 어떤 프로세스가 도착하고 각각 cpu 버스트 시간을 얼마나 하는지에 대한 정보를 시간 순서대로 적어놓는다.

Reference

반효경, 운영체제와정보기술의원리, 이화여자대학교출판문화원, 2020.05.04, p145~176