[운영체제]CPU 스케줄링(feat. PCB, Context Switching)

JANG SEONG SU·2023년 8월 22일

운영체제

목록 보기

3/4

1. PCB

CPU는 각 프로세스가 누군지 알아야 관리 및 실행을 할 수 있다. 이때 프로세스들의 특징을 갖고 있는 것이 바로 Process Metadata이다.

🫧Process Metadata

Process ID : 프로세스의 고유 ID

Process State : 준비(Ready), 대기(Wait) 등 CPU에 대한 소유권을 얻은 이후의 상태 - 실행(Running)상태의 프로세스 정보는 CPU 내부, 즉 레지스터에서 저장한다

Program Counter : 프로세스를 위해 실행될 다음 명령어의 주소

Register : Accumulator, General Register 등을 포함하는 CPU Register의 값

CPU Scheduling Information : 우선순위, 최종 실행시간, CPU 점유시간 등

Memory management information : 해당 프로세스의 주소 공간 정보

I/O Status : 프로세스에 할당된 입출력 장치 목록, 열린 파일 목록 등

이 메타데이터는 프로세스가 생성되면 PCB(Process Control Block)이라는 곳에 저장된다.

프로그램이 실행 ➡ 프로세스 주소 공간(stack,data,code) 생성 ➡ 이 프로세스의 메타데이터를 PCB에 저장

앞서 배울 Context Switching이 일어났을 때, 현재 실행 중인 프로세스의 정보를 PCB에 저장하여, 앞으로 다시 실행할 때 PCB를 통해 메타데이터를 읽어 실행하기 위함이다.

PCB 관리

프로세스의 생성과 소멸은 빈번하게 일어나기 때문에, Linked List방식으로 관리된다. PCB가 생성되면 PCB 연결 리스트의 Head에 추가되고, 소멸되면 삭제된다.

PCB 위치

PCB는 일반 사용자가 접근하지 못하도록 커널 스택의 가장 앞부분에서 관리된다. 커널 스택은 커널 권한을 가진 운영체제만이 접근 가능하다.

2. Context Switching

현재 실행중인 프로세스에 할당된 시간이 끝나거나 Interrupt가 발생하면, Context Switching이 발생한다. 하나의 CPU에는 하나의 프로세스만 실행이 가능하므로, 현대의 프로그램이 동시에 실행하는 것처럼 보이는 이유는 바로 Context Switching이 매우 빠른 속도로 진행되기 때문이다.

위 그림은 Context Switching의 동작 과정의 예시이다.
1. Process P1이 실행되는 도중 인터럽트가 발생하거나 CPU 사용 허가 시간이 지난다.
2. PCB1에 P1의 정보를 저장하고 PCB2의 상태를 불러온다.
3. Process P2를 실행한다.
4. P2가 실행되는 도중 인터럽트가 발생하거나 CPU 사용 허가 시간이 지난다.
5. PCB2에 P2의 정보를 저장하고 PCB1의 상태를 불러온다.
6. Process P1을 실행한다.

Context Switching이 발생하는 과정에서 다음 프로세스가 실행되기 전까지의 CPU의 idle시간이 발생하는데, 이를 오버헤드라고 한다.

🫧Context Switching이 필요한 이유
CPU는 한 번에 하나의 프로세스만 수행할 수 있다.
하지만, 실생활에서 우리는 여러 개의 프로세스를 동시에 수행하려고 한다. (ex: 노래 들으며 인터넷 하기)
따라서 CPU는 동시에 수행하는 처럼 보이게 하기 위해서 여러 개의 프로세스를 번갈아가며 수행한다.
이렇게 CPU가 프로세스를 바꿔가며 실행하기 위해서 Context Switching이 필요하게 되었습니다.

3. CPU 스케줄링

이제는 본격적인 CPU 스케줄링에 대해 알아보겠다.

CPU가 노는 상태가 될때마다, 운영체제는 Ready Queue에 있는 프로세스 중 하나를 선택해 실행해야 한다. 이때의 선택 절차는 CPU Scheduler에 의해 수행된다.

CPU 스케줄링의 목적

공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 특정 프로세스가 배제되어서는 안 된다.
효율성 : 시스템 자원을 놀리는 시간 없이 스케줄링해야 한다.
안정성 : 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 해야 한다.
반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.

이것은 면접 질문에 나온다고도 들어서, 한번 알아보고 가자

선점/비선점 스케줄링

선점(preemptive) 스케줄링 : 시분할 시스템에서 타임 슬라이스가 소진되었거나, 인터럽트나 시스템 호출 종료시에, 더 높은 우선순위 프로세스에 의해 현재 실행되고 있는 프로세스로가 CPU를 강제적으로 회수당하는 경우
비선점(nonpreemptive) 스케줄링 : 일단 CPU가 한 프로세스에 의해 할당되면, 프로세스가 종료 또는 대기 상태가 될때까지 CPU를 점유 보장

프로세스의 상태

선점 스케줄링 : Interrupt, I/O or Event Completion, I/O or Event Wait, Exit
비선점 스케줄링 : I/O or Event Wait, Exit
위의 상황에 대해 선점/비선점 CPU 스케줄링이 발생된다.

프로세스가 실행 상태에서 대기 상태로 전환 (I/O 발생) : I/O or Event Wait

프로세스가 실행 상태에서 준비 완료 상태로 전환 (인터럽트 발생) : Interrupt

프로세스가 대기 상태에서 준비 완료 상태로 전환 (I/O 종료) : I/O or Event Completion

준비 상태에 있는 프로세스 중 하나를 실행 : Scheduler Dispatch

프로세스 종료 : Exit

스케줄링 알고리즘

비선점 스케줄링

FCFS (First Come First Served)
- 큐에 도착한 순서대로 CPU 할당
- 실행 시간이 짧은 게 뒤로 가면 평균 대기 시간이 길어짐
SJF (Shortest Job First)
- 수행시간이 가장 짧다고 판단되는 작업을 먼저 수행
- FCFS 보다 평균 대기 시간 감소, 짧은 작업에 유리
- Starvation 발생할 수 있음

선점 스케줄링

Priority Scheduling
- 우선순위가 각 프로세스들에 연관되어 있고, CPU 코어는 가장 높은 우선순위를 가진 프로세스에 할당
- 우선순위가 같은 프로세스들은 보통 FCFS 방식으로 스케줄링
- Starvation 발생할 수 있음
- Aging 방법으로 오랫동안 대기하는 프로세스들의 운선순위를 점진적으로 증가하여 Starvation 해결 가능
Round Robin Scheduling
- Time Quantum or Time Slice 라는 실행의 최소 단위 시간 정의
- CPU 스케줄러는 Ready Queue에서 FCFS 방식으로 각 프로세스에게 동일한 시간의 Time Quantum 만큼 CPU를 할당 함
- 할당 시간(Time Quantum)이 크면 FCFS와 같게 되고, 작으면 Context Switching 잦아져서 오버헤드 증가
Multilevel-Queue(다단계 큐) Scheduling
- 우선순위 스케줄링이 라운드 로빈과 결합한 방식
- 작업들을 여러 종류의 그룹으로 나누어 여러 개의 큐를 이용하는 기법
- 우선순위가 낮은 큐들의 Starvation을 방지하기 위해 Time Quantam을 설정
- 우선순위가 높은 큐는 작은 Time Quantum 할당. 우선순위가 낮은 큐는 큰 Time Quantum 할당
Multilevel-Feedback-Queue (다단계 피드백 큐) Scheduling
- 프로세스가 큐들 사이를 이동하는 것을 허용
- 다단계 큐 스케줄링 + 동적인 프로세스 우선순위 변화
- 만약 실행 중인 프로세스가 자꾸 모든 타임 슬라이스를 소진하여 CPU 시간을 너무 많이 사용한다면
- 만약 하위 큐에 있는 프로세스가 타임 슬라이스를 다 소진하지 않고 대기 상태로 돌아가면서 CPU를 반납한다면 상위 큐에 삽입하여 위로 거슬러 올라감
- 가장 하위 큐는 FCFS로 스케줄링
- 낮은 우선순위의 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위의 큐로 이동시키는 Aging 통해 Starvation 예방