면접을 위한 CS 전공지식 노트 (9) - CPU 스케줄링 알고리즘 & 운영체제(OS) Summary

CPU Scheduling & Algorithm

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당

• 프로그램이 실행될 때는 CPU스케줄링 알고리즘이 어떤 프로그램에 CPU소유권을 줄것인지 결정
• CPU스케줄링 알고리즘 목표
  • CPU 이용률은 높게
  • 주어진 시간에 많은 일을 하게
  • 준비 큐(ready queue)에 있는 프로세스는 적게
  • 응답 시간은 짧게 설정하는것

01. CPU스케줄링 알고리즘 - 비선점형 방식

비선점형 방식(non-preemptive)은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않습니다. 따라서 컨텍스트 스위칭으로 인한 부하가 적다.

• FCFS

FCFS (First Come, First Served)는 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. (FIFO 큐랑 비슷하네,,?)
길게 수행되는 프로세스 떄문에 ‘준비 큐에서 오래 기다리는 현상(convoy effect’이 발생하는 단점이 있다.)

• SJF

SJF (Shortest Job First) 는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다. 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며, 평균 대기 시간이 가장 짧습니다. 하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용합니다. 반대 개념으로 LJF 이 있습니다.

• 우선순위

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었습니다.
이는 오래된 작업일수록 ‘우선순위를 높이는 방법(aging)’ 을 통해 단점을 보완한 알고리즘을 말합니다.

02. CPU스케줄링 알고리즘 - 선점형 방식

선점형 방식(preemptive)은 현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU소유권을 할당하는 방식을 말한다.

• 라운드 로빈(Round Robin)

라운드 로빈(RR) 은 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링(priority scheduling)의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 가는 알고리즘입니다.

예를 들어 q만큼의 할당 시간이 부여되었고 N개의 프로세스가 운영된다고 하면 (N - 1) * q 시간이 지나면 자기 차례가 오게 됩니다. 할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커집니다.

일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있습니다. 또한, 이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로도 쓰입니다.

• SRF

SJF 는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그다음 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘입니다.

• 다단계 큐

다단계 큐는 우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말합니다. 큐 간의 프로세스 이동이 안 되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있습니다.

OS Summary

01. 운영체제의 역할

1. CPU 스케줄링과 프로세스 관리
   • CPU 소유권을 어떤 프로세스에 할당할지, 프로세스의 생성과 삭제, 자원 할당 및 반환을 관리합니다.
2. 메모리 관리
   • 한정된 메모리를 어떤 프로세스에 얼만큼 할당해야 하는지 관리한다.
3. 디스크 파일 관리
   • 디스크 파일을 어떠한 방법으로 보관할지 관리합니다.
4. I/O 디바이스 관리
   • I/O 디바이스들인 마웃, 키보드 등과 컴퓨터 간에 데이터를 주고받는 것을 관리합니다.

02. PCB란 무엇인가?

PCB(Process Control Block)은 운영체제에서 프로세스에 대한 메타데이터를 저장한 ‘데이터’를 말합니다. 프로세스 제어 블록 이라고도 합니다. 프로세스가 생성되면 운영체제는 해당 PCB를 생성합니다.

프로그램이 실행되면 프로세스가 생성되고 프로세스 주소 값들에 앞서 설명한 스택, 힙 등의 구조를 기반으로 메모리가 할당됩니다. 그리고 이 프로세스의 메타데이터들이 PCB에 저장되어 관리됩니다. 이는 프로세스의 중요한 정보를 포함하고 있기 때문에 일반 사용자가 접근하지 못하도록 커널 스택의 가장 앞부분에서 관리됩니다.

03. 메모리 계층에 대해 설명

메모리 계층은 레지스터, 캐시, 메모리, 저장장치로 구성되어 있습니다.

• 레지스터

CPU 안에 있는 작은 메모리, 휘발성, 속도 가장 빠름, 기억 용량이 가장 낮다.

• 캐시

L1, L2 캐시를 지칭하며 휘발성, 속도 빠름, 기억 용량이 낮습니다. 참고로 L3 캐시도 있다.

• 메모리

주 기억장치로는 RAM을 가리킵니다. 휘발성, 속도 보통, 기억 용량이 보통입니다.

• 저장장치

보조기억장치로는 HDD, SDD 를 일컬으며 비휘발성, 속도 낮음, 기억 용량이 높습니다.