개요
중앙처리장치 (CPU) : 컴퓨터 자원 중 가장 중요한 자원
CPU 스케줄링 : 프로세스들에게 CPU를 할당하기 위한 정책을 설정하는 것
프로세스 스케줄링 : ready 상태에 있는 프로세스 중 어느 것을 CPU에 할당시킬 것인지 결정하는 것
CPU 스케줄링의 목적
- CPU 효율 및 처리율의 최대화
- 반환시간의 최소화
프로세스 관리
프로세스 : 주기억장치에 저장된 프로그램이 CPU에 의해 실행되거나 실행 준비 상태가 된 것
프로세스의 다양한 정의
- 실행중인 프로그램
- PCB(Process Control Block)를 지닌 프로그램
- 프로그램 카운터를 지닌 프로그램
- 능동적 객체로, 순차적으로 수행하는 프로그램
운영체제의 프로세스 관리 관련 기능
- 사용자 프로세스와 시스템 프로세스의 생성과 삭제
- 프로세스의 일시 중지(suspend)와 재수행(resume)
- 프로세스 스케줄링
- 프로세스의 동기화
- 프로세스 간 통신
- 교착 상태(deadlock) 처리
프로세스 구성 요소
[그림 1]은 RAM에 적재된 하나의 프로세스 구조를 나타낸 것
- 코드 영역 : 바이너리 코드 형식의 프로그램 코드
- 데이터 영역 : 프로그램의 전역 변수나 정적 변수의 할당을 위해 존재하는 공간
- 스택 영역 : 지역 변수 할당과 함수 호출 시 전달되는 인수 값 저장
- 힙 영역 : 사용자에 의해 메모리 공간이 동적으로 할당되고 해제되는 공간
프로세스 상태
작업이 접수되어 완료될 때까지 여러 상태 변화를 거침
- 실행 상태 : 프로세스가 CPU를 차지하고 있는 상태
- 준비완료 상태 (ready) : CPU가 사용 가능하게 될 때 그것을 할당받을 수 있는 상태
- 보류 상태 (block) : 프로세스가 CPU를 차지하고 처리하다가 입출력 처리 등을 하게 되면 CPU를 양도하고 입출력 처리가 완료될 때 까지 기다리고 있는 상태
- 디스패치 (dispatch) : 준비완료 상태 → 실행 상태
- timer runout : 실행 상태 → 준비완료 상태
- block : 실행 상태 → 보류 상태
- wakeup : 보류 상태 → 준비완료 상태
프로세스 제어 블록 (PCB)
PCB (Process Control Block) : 프로세스에 관한 모든 정보를 가지고 있는 데이터베이스
PCB 구성
- 프로세스의 현재 상태(실행, 준비완료, 대기 등)
- 프로세스의 고유 이름(identifier)
- 프로세스의 우선순위
- 프로세스가 적재된 기억장치의 주소를 가지는 포인터
- 할당된 자원(장치 등)을 가리키는 포인터
- CPU의 각종 레지스터 상태를 저장하기 위한 공간
프로세스 생성
UNIX에서 프로세스를 생성하는 함수는 fork()
[그림 4]는 fork()가 실행된 후 두 개의 프로세스가 실행중인 모습을 나타냄
이 때 위의 것을 부모 프로세스, 아래의 것을 자식 프로세스라고 함
#include <unistd.h>
int main() {
pid_t pid;
printf("Before fork() '\n');
pid = fork(); // run fork()
if(pid == 0) { // child process
printf("I'm child. Pid is %d '\n', pid);
} else if(pid > 0) { // parent process
wait(NULL);
printf("I'm parent. Pid is %d '\n', pid);
}
else printf("error");
}
프로세스 스케줄링
스케줄링의 목적
- 공정성 (fairness)
- 처리 능력의 최대화
- 응답 시간의 최소화
- 예측 가능
- 오버헤드 최소화
- 자원 사용의 균형 유지
- 응답과 이용 간의 균형 유지
- 실행의 무한 지연 피하기
- 우선순위제 실시
- 주요 자원들을 점유하고 있는 프로세스에게 우선권을 주게 한다
- 좀 더 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스 제공
- 과중한 부하 완만히 줄이기
스케줄링 기법의 고려 사항 (기준)
- 입출력 위주의 프로세스인가?
- 연산 위주의 프로세스인가?
- 프로세스가 일괄 처리형인가? 대화형인가?
- 긴급한 응답이 요구되는가?
- 프로세스의 우선순위
- 프로세스가 페이지 부재를 얼마나 자주 발생시키는가?
- 높은 우선순위를 지니는 프로세스에 의해서 얼마나 자주 프로세스가 선점되는가?
- 프로세스가 받은 실행 시간은 얼마나 되는가?
- 프로세스가 완전히 처리되는 데 필요한 시간은 얼마나 더 요구되는가?
CPU 스케줄링의 세 가지 중요한 단계별 분류
- 상위 단계 스케줄링 (highlevel scheduling)
- 어떤 작업에게 시스템의 자원들을 차지할 수 있도록 할 것인지 결정
- 중간 단계 스케줄링 (intermediate level scheduling)
- 어떤 프로세스들에게 입출력장치를 차지할 수 있도록 할 것인지 결정
- 하위 단계 스케줄링 (lowlevel scheduling)
- 어떤 준비완료 프로세스에게 CPU를 할당할 것인지 결정
- 디스패처(dispatcher)에 의해 매초 여러 번 작동
방법 / 환경별 분류
- 선점 / 비선점 스케줄링
- 비선점 : 프로세스가 CPU를 차지하면 CPU가 프로세스의 수행이 끝날 때까지 작업하여야 함
- 선점 : 프로세스가 CPU를 차지하고 있더라도 다른 프로세스가 수행 중인 프로세스를 중지하고 CPU 점유 가능
- 우선순위 (priority) 스케줄링
- 각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방법
- 우선순위 기법의 두 가지 방법
- 정적 우선순위 : 실행이 쉽고 상대적으로 오버헤드가 적으나 주위 여건의 변화에 적응하지 않고 우선순위를 변경하지 않음
- 동적 우선순위 : 각 프로세스에 부여된 처음의 우선순위는 필요에 따라 재구성되어 잠시 동안만 그 순위를 가지며 다시 조정될 수 있음
- 기한부 (deadline) 스케줄링
- 작업들이 명시된 시간이나 기한 내에 완료되도록 계획
- 다중 프로세서 스케줄링
- 두 가지 스케줄링 방식
- 각 프로세스가 스스로 스케줄링하며, 공동 준비 큐를 조사하여 실행할 프로세스 선택
- 한 프로세서가 다른 프로세서를 위한 스케줄러로서 지정되어 주 / 종(master / slave structure) 구성
- 두 가지 스케줄링 방식
프로세스 스케줄링 알고리즘
스케줄링 알고리즘의 평가 척도
- 서비스 반환시간 = 서비스 완료시간 – 서비스 시간
- 서비스 대기시간 = 서비스 시작시간 – 도착시간 = (서비스 완료시간 – 서비스 시간) – 도착시간 = 서비스 완료시간 – (도착시간 + 서비스 시간)
1. FCFS (First Come First Served) 스케줄링
- 가장 간단한 비선점 스케줄링 방식
- 프로세스들은 대기 큐에 도착한 순서에 따라 CPU 할당
| 프로세스 | 버스트 시간 (birst time) |
| P1 | 21 |
| P2 | 3 |
| P3 | 6 |
- 3개의 프로세스의 평군 반환시간과 평균 대기시간 계산
- 평균 반환시간 : (21 + 24 + 30) / 3 = 25
- 평균 대기시간 : (0 + 21 + 24) / 3 = 15
- 프로세스 도착 순서가 P2, P1, P3인 경우 평균 반환시간과 평균 대기시간 계산
- 평균 반환시간 : (3 + 24 + 30) / 3 = 19
- 평균 대기시간 : (0 + 3 + 24) / 3 = 9
- 호위 효과(convoy effect) 발생
2. SJF (Shortest Job First) 스케줄링
- 성능 평가의 기준으로 사용
- 기다리고 있는 프로세스 중에서 수행시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링 방식
- FCFS보다 평균 대기시간을 감소시키는 반면 큰 프로세스에 대해서는 대기시간들의 분산이 FCFS 방식에 비해 크고 예측하기가 어려움
- 문제점
- 수행될 프로세스가 얼마나 길게 걸릴지 정확히 예측할 수 없음
| 프로세스 | 버스트 시간 (burst time) |
| P1 | 7 |
| P2 | 8 |
| P3 | 3 |
| P4 | 6 |
- FCFS 방식의 평균 반환시간 : (7 + 15 + 18 + 24) / 4 = 16
- SJF 방식의 평균 반환시간 : (3 + 9 + 16 + 24) / 4 = 13
3. 우선순위 (Priority) 스케줄링
- 우선순위가 각 프로세스에게 주어지며, CPU는 우선순위대로 작업 처리
- 우선순위가 같다면 FCFS로 처리
| 프로세스 | 버스트 시간 | 우선순위 |
| P1 | 8 | 2 |
| P2 | 2 | 3 |
| P3 | 1 | 1 |
| P4 | 2 | 3 |
| P5 | 6 | 4 |
- 5개의 프로세스의 평균 반환시간과 평균 대기시간 계산
- 평균 반환시간 : (1 + 9 + 11 + 13 + 19) / 5 = 10.6
- 평균 대기시간 : (0 + 1 + 9 + 11 + 13) / 5 = 6.8
- 우선순위 스케줄링은 선점이거나 비선점이 될 수 있음
- 주요 문제
- 무한 대기
- 기아 현상
- 해결책 : 에이징 (aging) – 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
4. 라운드 로빈 (Round-Robin) 스케줄링
- 시분할 시스템을 위해 고안된 선점 스케줄링 방식
- 대화식 사용자들에게 알맞은 응답시간을 보장해 주어야 하는 시분할 방식의 시스템에서 효과적
- 할당시간의 크기는 컴퓨터 시스템의 효과적인 동작에 절대적인 영향을 미침
- 할당시간이 너무 크면, 라운드 로빈 방법은 FCFS 방식과 다를 바가 없어짐
- 할당시간이 너무 작으면, 문맥 교환을 위한 오버헤드로 인해 시스템의 성능 저하
5. SRT (Shortest Remaining Time) 스케줄링
- SJF 기법에 선점 방식을 도입한 변형된 방법으로서 시분할 시스템에서 유용
- 새로 도착한 프로세스를 포함하여, 처리가 완료되는 데 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행
- 실행 중인 프로세스가 선점될 수 있음
6. 다단계 큐(Multilevel Queue) 스케줄링
- 작업들을 여러 그룹으로 나누어 여러 개의 큐를 이용하는 기법
7. 다단계 피드백 큐 (Multilevel Feedback Queue) 스케줄링
- 작업들이 여러 큐로 갈아타게 하는 기법
8. HRRN (Highest Response Ratio Next) 스케줄링
- 한 작업이 CPU를 차지하면 완성될 때 까지 실행, 대기시간이 고려되어 긴 작업과 짧은 작업 간의 불평등을 어느 정도 완화
- 우선순위 계산법 : (대기시간 + 서비스를 받을 시간) / 서비스를 받을 시간 = 시스템 응답시간(클수록 우선순위 높아짐)
| 프로세스 | 대기시간 | 버스트 시간 |
| P1 | 16 | 4 |
| P2 | 10 | 5 |
| P3 | 7 | 7 |
| P4 | 18 | 6 |
- 위 표에 대한 우선순위 계산
- P1 : (16 + 4) / 4 = 5
- P2 : (10 + 5) / 5 = 3
- P3 : (7 + 7) / 7 = 2
- P4 : (18 + 6) / 6 = 4
- 우선순위는 P1, P4, P2, P3 순으로 배정
스레드 (Thread)
스레드 : 프로세스가 CPU에 보내져 실행되는 흐름의 단위
- 스케줄링의 단위가 된 스레드의 특성
- 각 스레드는 서로 독립적
- 스레드의 실행 / 종료 순서 예측 불가
- 스레드의 수행을 위해 스케줄 되고 결과들은 프로세스에게 전달
- 프로그램에 있는 스레드의 수는 다른 스레드에게 알려지지 않음
- 스레드는 프로그램의 외부에서 보이지 않음
- 스레드는 서로 독립적이지만, 한 스레드가 취한 행동은 프로세스에 있는 다른 스레드에 영향을 미침
- 스레드는 프로세스의 일부분이기 때문에 프로세스의 자원들을 공유하지만 그 자신의 처리시간과 스택, 레지스터들이 할당됨
- 한 프로세스가 exit() 시스템 콜을 통해 종료되면, 모든 스레드들도 종료
- 단일 스레드 프로세스는 힙, 정적, 코드, 레지스터, 스택 공유
- 다중 스레드 프로세스는 힙, 정적, 코드 공유 / 스레드마다 고유한 레지스터, 스택을 가짐
- 중량 프로세스(Heavy Weight Process) – 하나의 스레드를 가진 프로세스
- 경량 프로세스(Light Weight Process) – 프로세스 내에 두 개 이상의 스레드를 포함
- 스레드 제어
- KLT : 스레드들이 커널에 의해 지원
- ULT : 사용자 수준에서 라이브러리 호출 집합을 통해 커널의 상위 수준에서 지원
자바 스레드 스케줄링
'Operation System' 카테고리의 다른 글
| [OS] 운영체제 개요 (0) | 2025.04.30 |
|---|
댓글