운영체제(CPU) 200512036국지웅

CPU 스케줄링의 개요 CPU가 주로 수행하는 것은 사용자의 작업과 프로그램이지만 그 외 다른 시스템활동도 수행해야 한다. 즉, 컴퓨터의 모든 동작은 CPU에 의해 시작된다. CPU는 오류, 프로그램의 요구 사항, 입출력 인터럽트 등에 대해서 대응 조치를 취해야 한다. 인터럽트는 시분할(time-sharing) 단말기 키보드에서 개별적 특성일 수도 있고,채널 프로그램의 결과일 수도 있다. 단일 사용자 시스템에서도 대화형 작업과 여러 개의 일괄 처리 프로그램들을 수행하는 식으로 여러 프로그램을 동시에 수행할 수 있다. 사용자는 어느 순간 한 프로그램 밖에 수행할 수 없지만, 운영체제는 자신의 내부활동들 을 지원할 필요 있다. 시분할 기법 한 개 또는 여러 개의 CPU를 가진 컴퓨터 시스템에서 동시에 여러 프로세서들에게 CPU를 분할 사용하여 CPU의 이용율과 처리율을 높이는 것이다. 공간 분할 기법(Space Sharing) 하나의 자원을 분할하여 여러 프로세서가 동시에 같이 사용하는 기법이다.

프로세서의 실행 프로세스 실행은 CPU 실행과 입출력 대기 상태의 순환인데, 프로세스는 이 두 상태를 오가며 실행된다. LOAD STORE ADD READ from file INCREMENT INDEX WRITE to file ADDSTORE I/O의 대기 CPU 버스터 I/O 버스터

프로세스 제어 블록 프로세스 프로그램 계수기 CPU 레지스터 주기억 장소 관리 정보 계정 정보 입출력 상태 정보 프로세스의 실행은 CPU 버스트와 입출력 버스트의 혼합된 연속이며, CPU 버스트로 시작되고 끝난다. 생성, 활동, 대기, 중단 프로그램 계수기 다음 실행할 명령어의 주소를 표시 CPU 레지스터 누산기, 색인 레지스터, 범용 레지스터, 조건코드 등에 관한 정보를 말하며 컴퓨터 구조에 따라 수나 형태가 변화한다 주기억 장소 관리 정보 기준 레지스터, 한계 레지스터, 페이지 표를 표함한다 계정 정보 CPU사용시간, 실제사용시간, 한정된 시간, 프로세스 번호 를 포함한다 입출력 상태 정보 입출력 상치 할당 정보, 개방된 파일 목록 등을 가지고 있다 CPU 스케쥴링 정보 프로세스 우선 순위, 스케쥴링 큐에 대한 포인터, 그외 다른 스케줄 매개 변수를 가지고 있다

스케줄링의 목적 목적 : 시스템 성능 향상을 위해서 스케줄링 : 특정 자원에 대해 그 자원을 요청하고 있는 대상들 중 누구에게 먼저 그 자원을 할당해 줄 것인가를 결정하는 일(대상이 누구인가에 따라 정해짐) 성능지표 ○ 응답시간 : 시스템이 사용자 요구에 응답하는 시간 ○ 작업처리량 : 단위 시간 내의 프로세스 처리량 ○ 자원 활용도 : 주어진 시간 동안의 특정 자원 활용 정도 * OS는 해당 응용 도메인에 맞는 성능 지표를 고려하여 스케줄링을 해야한다. 일반 시스템의 OS에서 고려하게 되는 성능 지표 ○공평성 (Fairness)-우선순위에 맞도록 조정 ○작업처리량(throughput) - 주로 일괄처리시스템의 성능지표로 사용됨 ○평균응답시간(mean response time)-주로 대화형 시스템의 성능지표로 사용됨 ○예견성(predictability) -시간적 제약을 가진 실시간 시스템에서 주로 사용 ○자원활용도 ○무기한 연기방지(no indefinite postponement) 어느 특정한 프로세스가 계속해서 자원을 사용하지 못하는 것 스케줄링의 편향성에 의해 나타나며 에이징기법(대기 시간이 경과할 수록 우선순위를 높여줌)으로 해결

작업 스케쥴링의 유형 작업 스케쥴링 프로세스 스케쥴링 기능별 분류 선점 스케쥴링 CPU 스케쥴링 비선점 스케쥴링 방법별 분류 알고리즘별 분류 작업 스케쥴링 프로세스 스케쥴링 선점 스케쥴링 비선점 스케쥴링 우선순위 스케쥴링 기한부 스케쥴링 FIFO 스케쥴링 Round Robin 스케쥴링 SJF(shortest job first) 스케쥴링 SRT(shortest remaining time) 스케쥴링 HRN(highest response ratio next) 스케쥴 MLQ(multi level queue) 스케쥴링 MFQ(multilevel feedback queue) 스케쥴링 FSS(fair share 스케쥴링)

작업 스케쥴링 프로세스 실행 : CPU 실행과 입출력 대기의 순환으로 구성되어, 이들 두 - 입출력 중심의 프로그램 : 전형적으로 매우 짧은 CPU 버스트를 많이 가짐. - CPU 중심의 프로그램 : 매우 긴 CPU 버스트를 조금 가짐.

스케줄링 구조 ◎ CPU 스케쥴링 결정 조건 ■ 프로세스가 실행 상태에서 대기 상태로 전환될 때(예를 들어, 입출력 요청이나 자식 프로세스 중의 하나가 종료되기를 기다리는 호출시) ■ 프로세스가 실행 상태에서 준비 상태로 전환될 때(예를 들어, 타이머 인터럽트가 발생할 때) ■ 프로세스가 대기 상태에서 준비 상태로 전환될 때(예를 들어, 입출력의 종료시)프로세스가 수행을 마치고 종료될 때 스케쥴링의 목적과 기준 스케쥴링의 목적 공정한 스케쥴링,처리량 극대화 응답 시간 최소화,반환시간 예측 가능 균형있는 자원 사용,응답 시간과 자원 이용간의 조화 실행의 무한 연기 배제,우선 순위제를 실시 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스를 제공

스케줄링 단계별 분류법 상위수준 스케쥴링 상위수준(high level, long term) 스케쥴링, 작업 스케쥴링, 승인 스케쥴링. 어떤 작업이 시스템의 자원들을 차지 할 수 있도록 할 것인가를 결정. 일단 승인이 되면 작업들은 프로세스들 또는 프로세스의 그룹들을 형성. 중위 수준 스케쥴링 중위 수준(intermediate level, short term) 스케쥴링은 어떤 프로세스들이 중앙처리 장치를 차지할 것 인가를 결정. 프로세스들을 일시 보류시키고 또 다시 활성화시키는 기법을 사용하여 시스템에 대한 단기적인 부하를 조절하는 버퍼 역활. 하위수준 스케쥴링 하위수준(low level, dispatcher) 스케쥴링은 중앙 처리 장치가 다음 프로세스를받아 들일 수 있을 때 어떤 준비 완료 프로세스에게 중앙 처리 장치를 할당할것인가를 결정. 디스패쳐(dispatcher)에 의해서 매초 여러 번 작동

방법별 분류 스케줄링 선점/비선점 스케쥴링 1) 선점 스케쥴링 선점(preemptive) : 한 프로세스가 CPU를 차지하고 있을때 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있는 경우. 높은 우선 순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용. 특징 ● 우선순위가 높은 프로세스가 먼저 수행할 때 유리 ● 빠른 응답시간을 요구하는시분할 시스템에 유용 ● 많은 오버헤드를 초래

알고리즘별 스케줄링 우선순위 스케쥴링 - nonpreemptive ■ 각 프로세스에게 우선 순위를 부여하여 순위가 높은 순서대로 처리하는 방법. ■ 우선 순위의 기법 종류 정적 우선 순위 방법 : 실행이 쉽고 상대적으로 오버헤드는 적으나, 반면 주위 여건의 변화에 적응하지 못하고 우선 순위를 바꾸지 않음. 동적 우선 순위 방법 : 상황 변화에 잘 적응. 구현하기가 복잡하고 오버헤드가 많으나, 시스템의 응답도를 증가시켜 주므로 효율성. ■ 4개의 우선순위를 갖는 시스템 예. 우선순위 종류 1인 실행 가능한 프로세스가 있는 한, 라운드 로빈 방식으로 주어진 하나의 프로세스가 할당시간 동안 곧바로 실행. 만약 우선순위 종류 1인 프로세스가 비게 되면, 우선 순위 종류 2인 프로세스가 라운드 로빈 방식으로 실행되고, 우선순위 종류 1,2가 비게 되면 운선순위 종류 3이 실행.

기한부 스케줄링 기한부 스케쥴링 - nonpreemptive ▶기한부(deadline) 스케쥴링은 작업들이 명시된 시간이나 기한내에 완료 되도록 계획되며, 이들 작업들의 결과가 시간내에 구해지면 유용하고 마감 시간이 지난 후에 결과가 구해지면 쓸모가 없게 됨. 사용자는 사전에 작업이 요구하는 정확한 자원을 제시. 문제는 미리 예측 하기가 어려움. 만약, 기한 시간내에 일을 끝내지 못하면 막대한 손해를 초래. 시스템은 기한까지 일을 끝내기 위하여 자신의 자원 안배를 주의 깊게 계획. 만약, 많은 기한부 작업들이 동시에 실행된다면 스케쥴링이 너무 복잡. 기한부 스케쥴링에 의해서 요구되는 집중적인 자원 운영은 많은 오버헤드.

FIFO 스케줄링 ■ SJF 스케쥴링에 대한 Gantt 차트. ■ 예를 들어, 시간 0에 도착한 다음의 프로세스들의 P1, P2, P3, P4 집합을 고려. CPU 버스트 시간의 길이는 10ms. ▶ 각 프로세스의 대기시간: P1은 3ms, P2는 16ms P3은 9ms, P4는 0ms. ▶평균 대기 시간 = (3 + 9 + 16 + 0)/4 = 7 * 10 ms. ▶평균 반환시간은 (9 + 24 + 16 + 3)/4 = 13 * 10 ms. 프로세스 버스트 시간 대기시간 반환시간 P1 6 3 9 p2 8 16 24 p3 7 9 16 p4 3 0 3 P4 P1 P3 P2 0 3 9 16 24

우선순위 스케쥴링 우선순위를 할당해 우선순위가 높은 순서대로 처리하는 방법 고정적 우선순위 가변적 우선순위 구입된 우선순위 비선점 마감시간 스케쥴링 프로세스가 주어진 시간내에 작업이 끝나도록 계획. 마감시간을 계산해야 하기 때문에 막대한 오버헤드와 복잡성이 발생. FIFO 스케쥴링 작업이 시스템에 들어온 순서대로 수행하는 방법. 대화형에 부적합. 간단하고 공평. 반응 속도를 예측가능. RR FIFO 방식의 변형으로서 일정한 시간을 부여하는 방법 시분할 방식에 효과적. 할당시간이 크면 FIFO와 같음.할당시간이 작으면 문맥 교환이 자주 발생. 선점 SJF 수행 시간이 적은 작업을 우선적으로 처리하는 방법 작은 작업에 유리하고 큰 작업은 상당히 시간이 많이 걸림. SRT 수행도중 나머지 수행시간이 적은 작업을 우선적으로 처리 작업 처리는 SJF와 같으나 이론적으로 가장 작은 대기시간이 걸림. HRN SRT의 큰 작업이 시간이 많이 걸리는 점을 보안한 방법. (대기시간+수행시간) 우선순위=------------ 수행시간 MLQ 서로 다른 작업을 각각의 큐에서 time-slice에 의해 처리. 각각의 큐는 독작적인 스케쥴링 알고리즘을 사용. MFQ 하나의 준비 상태 큐를 통해서 여러 개의 피드백 큐를 걸쳐 일을 처리. CPU와 I/O 장치의 효율을 높일수 있음 종 류 방 법 특 징

끝 감사합니다