CS Week 2 - 운영체제(1)

¿curious_jin¿·2025년 11월 9일

Context Switching Gantt 차트 MLFQ OS PCB RR SRTF 드라이버 디스패처 비선점형 선점형 쉘 스레드 스케줄러 스케줄링 시스템콜 운영체제 커널 프로세스

CS(Computer Science) 독학

목록 보기

2/3

Table of Content

지난 주차 컴퓨터를 이루는 CPU와 메모리, 캐시 메모리 등 여러 하드웨어적인 요소들에 이어 이번 주차는 컴퓨터의 두뇌, 운영체제와 관련된 내용을 공부하였다.

그 중에서도 운영체제와 프로세스, 스레드에 대해 알아보고 운영체제가 이들을 어떻게 관리하고 이들이 어떻게 실행되는지에 대해 차근차근히 알아보자.

주제	세부 핵심 내용
1. 운영체제에 대해서 - 운영체제의 4요소	- 운영체제(OS)란 ?
	- 커널(Kernel)이란 ?
	- 시스템 콜(System Call)이란 ?
	- 드라이버(Driver)란 ?
	- 쉘(Shell)이란 ?
2. 프로세스에 대해서 - 독립 공간과 PCB	- 프로세스란?
	- 프로세스의 구조
	- PCB(Process Control Block)와 Context Switching
3. 프로세스 상태와 큐 - CPU 자원의 효율적 분배	- 프로세스의 상태(State)와 상태 전이(State Transition)
	- 큐(Queue)와 디스패처(Dispatcher)
	- 스케줄러(Scheduler)
4. 컨텍스트 스위칭 - 멀티태스킹의 정체와 그 비용	- 컨텍스트 스위칭(Context Switching)
	- 비용의 정체
5. 스레드 vs 프로세스 - 하나의 프로세스, 여러 스레드	- 스레드란 ?
	- 스레드 관리 방식
6. 스케줄링 목표 & CPU/I-O burst 모델 - “빠르게 보다 매끄럽게”	- 스케줄링의 목표
	- CPU–I/O Burst 모델
7. 스케줄링 알고리즘 - Gantt 차트	- Gantt 차트
	- 선점형(Preemptive) vs 비선점형(Non-Preemptive)
	- 스케줄링 알고리즘
8. 문제 - 스케줄링 알고리즘 위주 - 스케줄링 알고리즘 위주	- 문제 P1. (SRTF 스케줄링 표)
	- 문제 P2. (RR with q=3)
	- 문제 P3. (MLFQ 시뮬 기초)
	- 문제 P4. (주관식)

1. 운영체제에 대해서 - 운영체제의 4요소

운영체제(OS)란 ?

컴퓨터마다 깔려있는 운영체제, OS 란 결국 커다란 시스템을 일컫는 말로 컴퓨터를 어떻게 운영할 것이냐에 대한 대답 자체이다.
이 거대한 시스템은 OS의 뇌를 담당하는 커널, 프로그램과 소통하는 시스템 콜, 하드웨어 장치와 소통하는 드라이버, 사용자와 소통하는 쉘로 나누어 볼 수 있다.

CPU, RAM 과 같은 컴퓨터의 여러 하드웨어와 가장 밀접히 맞닿아있는 첫 번째 계층의 소프트웨어라고 보면 되겠다.
커널(Kernel)이란 ?

커널이란 운영체제의 핵심 뇌 역할을 하는 소프트웨어를 말한다.

이러한 커널은 1️⃣ 프로세스를 관리하고,
2️⃣ 해당 프로세스에 맞게끔 메모리를 할당, 관리하고
3️⃣ 여러 외부 요청을 받는 시스템 호출 인터페이스를 제공하고
4️⃣ 여러 기기의 입출력(I/O)를 관리하며
5️⃣ 내부 디스크의 파일을 관리하는 등의 역할을 맡고 있다. 말 그대로 다 하는 셈.
- 커널 공간
  
  커널은 자신의 일을 오롯이 해결하기 위해 스케줄러, 디스패처, 페이지 테이블 등 여러 별도의 도구를 필요로 한다. 이를 위해 운영체제는 메모리 공간, RAM을 “사용자 공간”과 “커널 공간”으로 나누어 이 도구들과 PCB 등의 여러 중요한 데이터를 저장해 놓는다. 커널 공간은 일반 프로그램이나 사용자가 직접 접근할 수 없고 운영체제, 커널을 통해서만 접근할 수 있으며 이 커널 공간을 통해서만 디스크나 파일 구조 등의 하드웨어에 직접 접근할 수 있다. 말 그대로 커널 전용 공간.
  1. 커널 코드 영역
    
    OS의 두뇌가 되는 커널의 핵심 코드가 담긴 공간이다. OS 자체의 코드, 예를 들어 프로세스 선택을 담당하는 스케줄러, CPU 할당을 담당하는 디스패처, 메모리 관리자 등이 여기에 저장되어있다.
  2. 커널 데이터 영역
    
    커널의 핵심 데이터가 담긴 공간이다. 커널이 일을 하기 위해 필요한 여러 추가적인 데이터를 여기에 담게 된다. 예를 들어 프로세스의 정보가 담긴 PCB, 가상 주소 변환을 위한 페이지 테이블 등의 자료가 저장되어있다.
  3. 커널 스택 영역
    
    커널의 함수 스택이 담긴 공간이다. 각 프로세스는 아래에 서술되는 “시스템 콜”을 이용하여 커널을 호출, 여러 작업을 하게 되는데 이를 스택 구조를 이용하여 쌓는 영역으로 각각의 프로세스마다 별도로 관리된다.
  4. 커널 힙 영역
    
    커널이 동적으로 사용할 수 있는 메모리 공간이다. 커널이 활동 중 커널 데이터 영역에 담을 여러 데이터를 생성할 때 할당되는 공간이다.
- 사용자 공간
  
  커널 공간을 제외한 나머지 RAM 공간이다. 대부분을 차지하며 일반 프로그램이나 사용자가 접근할 수 있다. 단, 일반 프로그램들은 각각 격리된 공간, 격리된 RAM 상에 존재하기에 이들을 넘어 다른 프로세스에 접근하고자 하면 제한을 받게 된다.
시스템 콜(System Call)이란 ?

외부에서 컴퓨터 내부 파일에 쉽게, 혹은 몰래 접근하지 못하도록 설정된 하나의 통로이다. 이에 따라 사용자든 프로그램이든 모두 시스템 콜이라는 통로를 통해서만 커널에 접근할 수 있고 파일의 관리, 메모리의 관리 등 여러 요청은 결국 커널이 해결하게 된다.

시스템 콜을 통해 커널이 어떠한 요청을 받게 되면 비로소 CPU 는 유저 전용 모드에서 커널 전용 모드로 모드 전환(Mode Switch)이 일어나고 내부 하드웨어에 접근할 권한을 얻게 된다. 이후 꺼내온 데이터 결과를 별도로 저장, 유저 전용 모드로 돌아가 사용자나 프로그램에 값을 다시 전달해준다.
드라이버(Driver)란?

드라이버란 컴퓨터의 뇌가 되는 커널과 외부에서 들어온 새 하드웨어를 연결해주기 위한 프로그램이다. 커널은 각 하드웨어에 맞는 드라이버에게 “명령”만을 내리고 이를 받은 드라이버는 명령을 하드웨어 장치에 맞게 해석하여 실행하는 식이다.

예를 들어 키보드는 눌린 자판을 별도의 드라이버가 인식하여 이에 맞는 전기 신호로 커널에 전달해주며, 그래픽 카드는 전달받은 이미지 정보를 GPU 명령으로 변환하여 실행하는 기능을 가지고 있다.
쉘(Shell)이란?

쉘은 시스템 콜의 사용자 친화적인 버전으로 사용자가 직접 시스템 콜을 사용할 수 있도록 하기 위해 만들어준 하나의 프로그램이라고 볼 수 있겠다. 사용자와의 “정해진 명령어”를 통해 소통하며 해당 요청을 시스템 콜을 거쳐 커널이 대신 작업해주는 형태이다.

그 큰 분류로는 CLI(Command User Interface)와 GUI(Graphic User Interface)가 존재하며 각각 명령어 기반 쉘, 아이콘이나 버튼 기반 쉘이라고 볼 수 있겠다.

2. 프로세스에 대해서 - 독립 공간과 PCB

프로세스란?

우리가 실행하는 어떤 프로그램(ex. 카카오톡이나 웹 브라우저 등)은 결국 어떠한 파일로 작성되어있다. 이러한 프로그램이 실행되는 하나하나의 개별 단위를 프로세스라고 한다.

더 정확히는 실행되는 개별 프로그램과 해당 프로그램 실행에 요구되는 캐시를 비롯한 모든 데이터를 포괄하는 개념이다.
프로세스의 구조

이러한 개별 프로세스는 실행되기 위해 WEEK 1 에서 이야기했듯이 RAM 상에 올라가게 되고 CPU와 상호작용 할 수 있는 상태가 된다. 그 과정에서 서로 다른 프로세스가 섞이지 않도록 컴퓨터의 운영체제, 커널은 이들을 각기 다른 “개별 메모리 공간”에 넣어 관리한다. 이러한 개별 메모리 공간은 일반 프로그램일 뿐이므로 RAM의 커널 공간이 아닌 사용자 공간에 저장된다.

이렇게 관리되는 하나의 개별 프로세스는 독립된 자신만의 공간 속에서 여러 영역으로 나누어 명령어와 데이터를 관리하게 된다.
1. 코드 영역
  
  실제 프로그램에 작성되어있는 “명령어”들이 저장되는 영역이다. 이 영역을 따로 분리함으로써 명령어가 중간에 수정되는 위험을 제거할 수 있다.
2. 데이터 영역
  
  프로그램이 실행되는 동안 생성되는 여러 데이터가 저장되는 공간으로 전역 변수, 정적 변수 등이 모두 포함되는 영역이다.
3. 힙(Heap) 영역
  
  고정되어 관리되는 데이터 영역과 다르게 일시적으로, 그리고 프로그램 실행 도중 동적으로 할당되는 메모리 공간을 말한다. 예를 들어 크기 n의 배열 객체 생성의 경우 이 영역에 데이터가 생성되고 주소가 할당된다.
4. 스택(Stack) 영역
  
  스택 영역은 데이터가 아닌 함수 호출을 관리하기 위해 할당된 메모리 공간이다. 여러가지 함수의 호출과 그 과정에서 생겨나는 지역 변수들, 함수 호출이 완료된 이후 돌아갈 리턴 주소 등의 정보가 이 공간에 저장된다.
5. 빈 영역
  
  이러한 영역들은 WEEK 1에서 말했듯 모두 가상 주소로 관리되어 커널에 의해 실제 RAM 주소에 매핑된다. 그렇기에 OS 는 힙 영역과 스택 영역의 동적인 특성을 반영하기 위해 가상 주소 상에서 커다란 빈 영역을 만들어 위 영역들의 동적인 확장에 대응, RAM 의 실제 메모리는 낭비하지 않는 효율적인 방법을 사용하게 되었다.
  
  예를 들어 0x0000~0x0100 이 힙 영역이고 0x0900~0x1000이 스택 영역이라면 그 사이 0x0101~0x0899가 빈 영역이 되며 힙 영역의 확장 시 아래 공간을 할당, 스택 영역의 확장 시 윗 공간을 할당함으로써 이에 대응하는 방식이다.
PCB(Process Control Block)와 Context Switching

CPU는 한 번에 하나의 프로세스만을 운영할 수 있기 때문에 이렇게 구성되는 프로세스는 하나의 컴퓨터에서 메모리 상에서 얽히지 않는 것 뿐 아니라 CPU가 보기에도 헷갈리지 않아야 한다.

그래서 나온 것이 PCB(Process Control Block), 개별 프로세스의 신분증이자 상태 기록표이다. 프로세스의 관리 정보를 담은 이들은 프로세스를 관리하는 OS의 커널의 메모리 공간에 저장된다.

이런 PCB는 어떤 정보로 이루어져 있느냐 ?

별도의 PID / PPID 를 통해 프로세스의 ID 와 부모 프로세스의 ID 를 저장, 구별하며 마지막 실행 시의 CPU 상태를 저장하기 위해 프로그램 카운터(PC), 당시 레지스터 값, 마지막에 끝난 스택 영역의 위치(SP) 등의 레지스터 스냅샷, 해당 프로세스의 우선순위 등의 스케줄링 정보와 페이지 테이블 등의 메모리 관리 정보 등 모든 메타 데이터가 여기에 저장된다고 보면 되겠다.

이렇게 저장된 PCB를 보고 CPU가 여러 프로세스를 왔다갔다 하는 것을 Context Switching이라고 한다.

이러한 스위칭은 1️⃣ 프로세스의 점유 시간이 다 되었을 때
2️⃣ 프로세스가 입/출력 대기중일 때
3️⃣ 해당 프로세스가 우선순위에서 밀릴 때
4️⃣ 해당 프로세스 내에서 시스템 콜이 발생하였을 때 발생할 수 있다.

3. 프로세스 상태와 큐 - CPU 자원의 효율적 분배

프로세스의 상태(State)와 상태 전이(State Transition)

앞서 CPU는 한 번에 한 가지 종류의 프로세스밖에 돌리지 못하기에 프로세스의 신분증인 PCB, Process Control Block을 통해 CPU가 이들 사이를 왔다갔다 돌아다닌다고 하였다. (Context Switching)

이를 위해 PCB에는 자신의 고유 ID와 레지스터 스냅샷 등의 정보 외에도 “내가 일을 할 수 있나?”를 나타내는 상태(State) 값이 별도로 존재한다. 이 상태 값은 5가지로 나뉜다.
1. NEW - 생성 중. 프로세스가 처음 실행되는 중. PCB 등이 새롭게 할당되는 상태.
2. READY - 실행 대기 완료. CPU 할당만 받으면 되는 상태.
3. RUNNING - 실행 중. 해당 프로세스가 CPU를 점유하는 상태.
4. BLOCKED (WAITING) - 대기 중. 별도의 I/O나 event를 기다리는 상태.
5. TERMINATED - 실행 종료. 프로세스가 닫히는 상태.
  
  위 5가지 상태에 따라 프로세스는 아래와 같은 상태 전이를 거치게 된다.
  
  1) NEW - READY - (스케줄러에 의해 CPU 할당) - RUNNING - (I/O 대기) - BLOCKED - (I/O 입력 완료) - READY - (스케줄러에 의해 CPU 할당) - RUNNING - TERMINATED
  
  2) NEW - READY - (스케줄러에 의해 CPU 할당) - RUNNING - (점유 시간 초과) - READY - RUNNING - (우선순위 밀림) - READY - RUNNING - TERMINATED
큐(Queue)와 디스패처(Dispatcher)

위 상태 중 CPU에 할당되는 프로세스는 READY 상태를 가진 프로세스 뿐이다. 따라서 READY 상태인 프로세스들을 관리하고 CPU를 효율적으로 배정하기 위해 운영체제는 이들만을 별도로 담는 Ready-Queue 자료구조를 만들어 관리한다.
- Ready-Queue
  
  Ready-Queue에는 프로세스들의 PCB 주소, 포인터만이 담기며 대개 우선순위 큐 구조를 가지고 있다.
  
  이 곳에 존재하는 우선순위가 높은 프로세스부터 PCB 주소 포인터를 타고 들어가 PCB를 확인, 레지스터를 복구하고 CPU를 할당받게 된다. 이들은 프로세스를 관리하는 핵심 자료구조로 커널의 메모리 공간에 저장된다.
- I/O-Queue
  
  Ready-Queue가 CPU 할당을 위해 대기하는 프로세스들의 집합이라면 각각의 별도 하드웨어, 드라이버 할당을 위해 대기하는 I/O-Queue도 존재한다.
  
  특정 하드웨어를 필요로 하는 프로세스들의 PCB 주소, 포인터가 담긴 자료구조로 마찬가지로 여기에서 순차적으로 뽑혀 각 하드웨어에 맞는 운영체제의 “드라이버”에 연결되는 것이다.
  
  이는 각 드라이버, 각각의 입/출력 장치별로 따로 존재한다.
I/O-Queue가 각각의 드라이버로 연결된다면 Ready-Queue는 어디로 연결되느냐 ?

Ready-Queue에서 선택받은 프로세스들은 별도의 커널 도구, 디스패처(Dispatcher)로 연결된다. 디스패처는 프로세스에 실제 CPU를 할당해주는 역할로 선택된 프로세스의 PCB를 참고, 마지막 저장 기록을 되돌리고 CPU를 연결하는 컨텍스트 스위칭을 실제로 수행한다.
스케줄러(Scheduler)

앞서 프로세스의 구조, 이들의 상태와 이들의 대기 장소인 Ready-Queue 등, 실제로 CPU를 할당하는 디스패처에 대해 배웠다. 이제 “실행할 프로세스는 누가 정할건데 ?”에 대한 답변을 들을 차례이다.

운영체제, OS는 위와 같은 프로세스들의 상태 뿐만 아니라 CPU의 점유 상태와 RAM의 점유율 등을 모두 참고해 “CPU의 사용 순서”를 정하는 스케줄러를 가지고 있다.

당연하게도 운영체제의 4 요소 중 커널의 “프로세스 관리” 역할을 이루는 구성 요소 중 하나이다.

이러한 스케줄러가 해야 하는 일로는 1️⃣ 프로세스를 RAM에 올리기
2️⃣ 프로세스에 CPU를 배정하기
3️⃣ 프로세스를 RAM에서 내리기가 있다.
1. 장기 스케줄러(Long-Term Scheduler)
  
  디스크에서 RAM에 올릴 프로세스를 정하는 스케줄러이다. 실행할 프로세스를 대기 공간, Ready Queue에 올려놓는다. RAM의 사용자 공간에 있는 프로세스에 대한, 커널 공간 속 커널 메모리 영역에 있는 PCB에 대한, 주소를 이곳에 담아 놓는다는 뜻이다.
2. 단기 스케줄러(Short-Term Scheduler)
  
  준비 완료 상태의 프로세스들이 모여있는 Ready Queue에서 CPU를 할당할 프로세스를 정하는 스케줄러이다. 여기서 선정된 프로세스는 디스패처(Dispatcher)에 의해 CPU를 할당받는다.
3. 중기 스케줄러(Medium-Term Scheduler)
  
  RAM이 부족한 경우 일시적으로 잠시 중단시킬 프로세스를 정하는 스케줄러이다. 메모리 관리를 위한 스케줄러로 이 과정을 스와핑(Swapping)이라고 한다.
  
  이들은 CPU의 최대 이용률, 전체 처리량, 낮은 대기 시간 및 응답 시간 등을 고려해 스케줄링을 진행하게 된다. 예를 들어 가장 단순한 FCFS(First Come First Served)부터 프로세스의 대기 시간이 제일 짧은 SJF(Shortest-Job-First), 균형있는 MLFQ(Multi-Level Feedback Queue) 등의 정책이 존재한다. 자세한 것은 6, 7번에서 살펴보자.

4. 컨텍스트 스위칭 - 멀티태스킹의 정체와 그 비용

이제 우리는 운영체제-커널의
1) 장기 스케줄러가 실행할 프로세스를 RAM에 올린 뒤 Ready Queue에 이 PCB 주소를 등록,
2) 단기 스케줄러가 그 중 CPU를 할당할 프로세스를 선정,
3) 디스패처가 CPU를 직접 할당한다는 사실을 알게 되었다.

그 CPU 할당 과정에서 발생하는 프로세스 변경, 컨텍스트 스위칭의 자세한 내용에 대해 알아보자.

컨텍스트 스위칭(Context Switching)

컨텍스트 스위칭이란 프로세스를 왔다갔다 하는 것, 더 구체적으로는 프로세스 실행 당시의 CPU 실행 맥락을 복구하는 작업을 말한다.

그렇다면 CPU 실행 맥락이란 무엇인가 ?

이는 PCB의 기록된 프로세스 정체성, 레지스터 스냅샷, 스케줄링 정보, 메모리 정보 중 레지스터 스냅샷을 일컫는다.

WEEK 1에서 보았던, 해당 프로세스의 마지막 실행 당시 계산 값들이 담겨있는 레지스터들이다. 예컨대, 다음에 실행할 명령어가 담겨 있는 프로그램 카운터(PC), 연산 정보 및 데이터가 담겨 있는 범용 레지스터(GPR), 현재 함수의 스택 위치를 나타내는 스택 포인터(SP) 등처럼 말 그대로 “맥락을 담고 있는 레지스터”만을 다시금 불러오게 된다.
비용의 정체

이와 같은 컨텍스트 스위칭은 프로세스를 변환할 때 마다 주요한 레지스터를 저장하고 다시 전부 바꿔야 한다는 부하를 주게 된다.
- 캐시 오염(Cache Pollution)
  
  하지만 눈에 보이는 부하가 전부가 아니다.
  
  각각의 프로세스는 별도의 공간을 이용하기에 가상 주소 변환 테이블, 페이지 테이블이 필요했으며 이를 따로 담아 놓는 TLB(Translation Lookaside Buffer)라는 별도의 캐시 공간이 있었다.
  
  주소 공간이 바뀌게 되면 이 TLB를 flush, 다시금 refill 해야 하는 부하가 걸리게 된다.
  
  뿐만 아니라 기존에 사용하던 L1~L3의 캐시 역시 전혀 다른 프로세스의 데이터를 담고 있을 것이기에 의미 없는 캐시 값이 되게 된다. 이를 캐시 오염(Cache Pollution)이라고 한다.
- 브랜치 예측기 오염(Branch Predictor Pollution)
  
  더 낮은 단계로 내려 가보자.
  
  WEEK 1에서 5단계 파이프라인의 작동에 대해 배울 때, CPU의 병렬적인 명령 처리 과정에서 분기나 점프 등으로 인해 PC 값이 꼬이는 제어 해저드가 존재했었으며 이를 해결하기 위한 방법이 분기나 점프를 예측하는 브랜치 예측기(Branch Predictor)였다.
  
  이 역시 프로세스가 바뀌게 되면 전혀 다른 경향성을 보이므로 오염되게 된다. 이를 브랜치 예측기 오염(Branch Predictor Pollution)이라고 한다.
이처럼 기본적인 레지스터 저장 및 변경 외에도 캐시 오염, 브랜치 예측기 오염 등의 문제로 컨텍스트 스위칭은 많은 비용을 껴안게 된다.

5. 스레드 vs 프로세스 - 하나의 프로세스, 여러 스레드

실제 사용환경에서 운영체제는 수많은 프로세스 변환, 즉 수많은 컨텍스트 스위칭 과정을 겪게 된다. 이는 레지스터 변경 및 캐시 오염 등 여러 비용을 가지게 되고 이러한 비용 문제를 줄이기 위해 출현한 것이 스레드(Thread)이다.

스레드란 ?

스레드란 하나의 프로세스 안에서 나뉘는 여러 실행 단위이다.

만일 프로그램을 실행할 때 하나의 프로그램이 하나의 프로세스, 즉 하나의 실행 단위로만 실행된다면 해당 프로그램 내에서 명시적으로 운영체제가 할 수 있는 작업은 한 번에 하나로 제한되는 상황이 발생한다.

이를 방지하고자 하나의 프로세스 내에서 여러 작업을 병렬적으로 수행하기 위해 여러 스레드를 놓는 것이다.

만일 스레드가 없다면 음악이 나오는 페이지에서 사용자가 클릭 행위를 하면 이를 처리하기 위해 음악이 멈춰버리는 식이다.
- 스레드의 특징
  
  이러한 스레드는 이 중 자신만의 진행 과정이 담긴 함수 스택 영역만을 제외, 프로세스의 코드 / 데이터 / 힙 영역을 서로 공유한다.
  
  프로세스가 각각의 정보를 담은 PCB에 의해 관리된다면, 스레드는 해당 프로세스의 PCB 내에 존재하는 TCB(Thread Control Block)에 의해 관리된다. TCB는 당연하게도 커널의 데이터 영역에 존재하며 스레드의 고유 ID, 당시 레지스터 스냅샷, 스케줄링 정보, 메모리 정보 등을 동일하게 가지고 있다.
- 스레드의 비용
  
  그렇다면 무슨 장점이 있느냐 ?
  
  스레드 역시 각각의 작업이므로 이들 간의 컨텍스트 스위칭 시 앞서 발생했던 레지스터 저장 및 변경의 비용이 여전히 발생하게 된다.
  
  하지만 이들은 동일 프로세스 내에 존재, 동일한 주소 공간을 공유하므로 주소 공간의 변환을 담당하는 페이지 테이블이 담긴 별도의 캐시인 TLB의 스위칭 과정이 없어지게 된다. 뿐만 아니라 이들은 동일한 프로세스에 존재하므로 유사한 데이터를 공유, 캐시 히트율이 유지되어 캐시 오염 문제 역시 발생하지 않게 된다.
스레드 관리 방식

그럼 이런 스레드들은 어떻게 관리할 것인가 ?
1. 1:1 모델 (Kernel-Level Thread, KLT)
  
  각각의 스레드 자체만을 하나의 독립된 실행 단위로 보고 운영체제가 이들을 각각 관리하는 방법이다. 앞선 스케줄러가 프로세스가 아닌 스레드를 중심으로 CPU(커널 스레드)를 할당하는 방식으로 현재 대부분의 운영체제가 이 방법을 채택하고 있다.
2. M:N 모델 (Hybrid Threading)
  
  M개의 스레드를 N개의 커널 스레드에 매핑하는 방식이다.
3. N:1 모델 User-Level Thread (ULT)
  
  프로세스를 독립된 실행 단위로 보고 하나의 프로세스가 CPU를 할당받는 구조이다. 프로세스가 여러 스레드를 갖더라도 한 번에 하나의 스레드만을 실행할 수 있기에 사용자 수준에서 이를 관리하는 작업이 필요하다.

6. 스케줄링 목표 & CPU/I-O burst 모델 - “빠르게 보다 매끄럽게”

앞서 소개하였던 커널의 스케줄러, 그 스케줄러가 일을 하는 방식에 대해 더 깊이 파고들어보자.

스케줄링의 목표

운영체제의 CPU 스케줄러는 결국 “누구에게 CPU를 할당할거야 ?”를 풀어내야 한다. 그 누군가를 선택하는 기준은 당연히 하나가 아니며 여러 관점에서의 비용을 고려해야 한다.

이는 여러 요소가 고려되는 내용으로 Ready Queue에 올라간 프로세스들의 평균 대기시간, 사용자 입장에서의 평균 응답시간, 각 작업 별 완료 속도인 평균 반환시간, 단위 시간당 완료된 작업 수인 처리량, 공정성 등이 고려된다.

이들을 모두 고려함으로써 커널의 스케줄러는 모든 작업이 빠르게, 그리고 공정하게, 그리고 매끄럽게 진행되도록 돕는다.
CPU–I/O Burst 모델

프로세스에 의해 받은 요청을 처리하기 위해 운영체제는 오로지 CPU만을 사용하지는 않는다.

대부분의 경우 단일 계산에 의해 끝나는 요청이 아니기에 여러 I/O 대기 요청을 수반하게 된다. 이러한 I/O 작업은 CPU 외부 모든 장치를 포함하므로 디스크 접근, GPU 접근 등의 작업을 포함하며 사용자와의 터미널 상호작용까지 포함한다.

만일 운영체제가 하는 작업이 CPU를 이용하여 하는 계산이 주를 이룰 경우 이를 CPU burst 구간, 반대로 다른 장치를 이용하는 작업이 주를 이룰 경우 I/O burst 구간이라고 한다.

이에 따라 각 프로그램은 자신의 동작 특성 및 상황에 따라 CPU 계산이 주를 이루는 CPU-bound, 외부 장치가 주를 이루는 I/O-bound 로 성격이 나뉘게 된다.

예컨대, 대화형 어플의 경우 더욱 더 부드러운 사용자 경험을 위해 I/O-bound의 성격을 가지며 CPU 기반 AI 학습 사이트의 경우 CPU-bound의 성격을 가지게 된다.

7. 스케줄링 알고리즘 - Gantt 차트

그럼 이제 프로그램의 특성까지 알아보았으니 앞서 간략하게 설명하였던 스케줄러의 여러 알고리즘에 대해 알아보자.

Gantt 차트

Gantt 차트란 스케줄러가 각 프로세스에 어떻게 CPU를 할당하는지 나타내기 위해 표현되는 시각화 방법으로 각 프로세스의 도착시간과 burst time을 고려하여 시간 별 CPU 할당 프로세스를 표기한다.

평균 대기시간의 경우 자신이 도착한 이후 자신이 완료되기 전까지의 시간 중 “자신이 CPU를 점유한 시간은 제외”하고의 시간이며 평균 반환시간의 경우 “자신이 CPU를 점유한 시간 포함”이다. 또한, 처리량의 경우 (완료한 프로세스 수)/(총 걸린 시간)이다.
- Example
```
Pn - 해당 시간에 CPU를 할당받은 프로세스
    
| P1 | P2 |--P3--| 
0    2    4      9
```
선점형(Preemptive) vs 비선점형(Non-Preemptive)

스케줄링 알고리즘은 CPU 양보 방식에 따라 선점형과 비선점형으로 나뉜다.

비선점형이란 CPU를 할당받은 프로세스가 CPU를 내놓기 전까지 다른 프로세스는 그저 기다릴 뿐인 알고리즘으로 해당 종료 조건은 프로세스의 종료, I/O 요청 등이 있다.

선점형이란 반대로 어떤 프로세스가 진행중이던 간에 우선순위가 더 높은 프로세스가 CPU를 빼앗는 알고리즘을 말한다. 사용자의 응답속도가 높아진다는 장점이 있지만 컨텍스트 스위칭 오버헤드가 커진다는 단점이 존재한다.
스케줄링 알고리즘

각 알고리즘 이후 아래 조건에 맞는 Gantt 차트를 첨부해두었다.

프로세스 도착시간 Burst Time 우선순위(낮을수록 높음)
P1 0 7 3
P2 2 4 1
P3 4 1 2
- FCFS(First Come First Served) → 단순함, 안정성
  
  FCFS(First Come First Served)란 가장 단순한 구조로 먼저 Ready Queue에 들어온 순서대로 프로세스에게 CPU를 할당해주는 알고리즘이다.
  
  공정하고 단순하다는 장점이 있지만 그 작업 시간과 CPU-bound, I/O-bound 를 나누지 않는 성격 탓에 작업 시간이 오래 걸리는 CPU-bound 작업이 들어올 경우 다른 I/O-bound 작업들이 순서가 밀려 사용자의 체감 속도가 많이 느려질 수 있다는 치명적인 단점이 존재한다. 이를 Convoy Effect라고 한다.
```
|----P1----|--P2--|P3|
 0          7      11 12
 평균 대기시간 : (0+5+7)/3 = 4
 처리량 : 3/12 = 0.25
```
- SJF / SRTF (Shortest Job / Shortest Remaining Time First) → 평균 대기시간++
  
  위 단점을 보완하기 위해 별도의 식을 통해 각 프로세스의 CPU-burst 예상 시간을 계산, 짧은 순서대로 CPU를 할당하여 평균 대기시간을 최대한으로 줄이고자 하는 알고리즘이다.
  
  한 번 CPU를 할당받은 프로세스는 끝까지 마치는 비선점형 SJF(Shortest Job)와 재계산 시 우선순위에 따라 CPU를 다시 최적화하는 선점형 SRTF(Shortest Remaining Time First)로 나뉘게 된다.
  
  평균 대기시간이 최소화됨에 따라 사용자의 체감이 좋다는 장점이 있지만 한 번 밀린 프로세스가 계속 밀릴 수 있다는 단점이 존재한다.
```
|----P1----|P3|--P2--|
 0          7  8      12
 평균 대기시간 : (0+6+3)/3 = 3
 처리량 : 3/12 = 0.25
```
```
|-P1-|-P2-|P3|-P2-|---P1---|
 0    2    4  5    7        12
 평균 대기시간 : (5+1+0)/3 = 2
 처리량 : 3/12 = 0.25
```
- RR (Round Robin) → 공정성, 평균 응답시간++
  
  RR(Round Robin)이란 Ready Queue에 존재하는 모든 프로세스에 대해 컨텍스트 스위칭 시간의 10~100배에 해당하는 타임 퀀텀(q)만큼의 시간을 배정하고 CPU를 할당, 작업이 끝나지 않았더라도 주어진 시간이 끝나면 다음 프로세스에게 CPU를 넘겨주는 방식이다.
  
  프로세스가 도중에 바뀌는 선점형 스케줄링 알고리즘으로 타임 퀀텀에 의한 공정성 덕에 평균 응답시간이 최소화되어 체감 속도가 매우 빠르다는 장점이 존재하지만 그 평균 대기시간이 늘어날 수 있다는 단점이 존재한다.
  
  타임 퀀텀 q가 너무 크면 그만큼 평균 응답시간이 늘어나게 되고 너무 작으면 잦은 프로세스 전환으로 불필요한 시간 낭비, 오버헤드가 크게 발생하게 된다.
```
 타임 퀀텀, q=2
 |-P1-|-P2-|-P1-|P3|-P2-|--P1--|
 0    2    4    6  7    9      12
 평균 대기시간 : (5+3+2)/3 = 3
 처리량 : 3/12 = 0.25
```
- Priority Scheduling (+ Aging) → 우선순위
  
  Priority Scheduling (+ Aging)이란 위 여러 기준에 의거, 각 프로세스들에 우선순위를 매긴 후, 우선순위가 높은 프로세스부터 비선점형으로 작업하는 알고리즘이다. 단, 자신보다 우선순위가 높은 프로세스가 등장하게 되면 CPU를 빼앗기는 선점형의 특성도 가지고 있다.
  
  우선순위의 기준을 어떻게 매기느냐에 따라 프로그램의 특성이나 목적에 알맞은 스케줄링 방식을 구현할 수 있다는 장점이 존재한다.
  
  대기시간이 길어짐에 따른 우선순위 우대(Aging)를 통해 우선순위가 낮은 작업이 영원히 시행되지 않는 문제를 해결한다.
```
|-P1-|--P2--|P3|---P1---|
 0    2      6  7        12
 평균 대기시간 : (5+0+2)/3 = 2.33
 처리량 : 3/12 = 0.25
```
- MLFQ (Multi-Level Feedback Queue) → 평균 응답시간, 처리량++
  
  위 우선순위 큐 구조의 발전된 알고리즘이다.
  
  MLFQ(Multi-Level Feedback Queue)이란 높은 레벨로 갈수록 많은 타임 슬라이스를 배정받은 다단계 큐 구조를 이용하여 그 효율을 높였다. 가장 상위 레벨(lv.0)의 타임 슬라이스를 전부 사용한 프로세스는 하위 레벨(lv.1)로 강등당하는 식이다.
  
  RR과 동일한 이유로 공정성을 가지지만 I/O-bound 프로세스에 대한 추가 우대 조건(강등 면제)을 통해 평균 응답시간, 사용자의 체감을 더욱 줄인 알고리즘이다.
```
 타임 슬라이스 : Q0=2, Q1=4, Q2=8
 |P1(Q0)|P2(Q0)|P3(Q0)|P2(Q1)|P1(Q1)|P1(Q2)|
 0      2      4      5      7      11    12
 평균 대기시간 : (5+1+0)/3 = 2
 처리량 : 3/12 = 0.25
```
- CFS (Completely Fair Scheduler) → 공정성++
  
  정해진 타임 퀀텀을 가지고 별도의 기준없이 프로세스를 순서대로 돌리는 RR 알고리즘의 보완 버전이다.
  
  CFS(Completely Fair Scheduler)는 프로세스마다 자신이 사용한 가상의 런타임 vruntime을 할당, 힙 구조를 이용하여 최소의 런타임을 가진 프로세스부터 실행한다.

프로세스	도착시간	Burst Time	우선순위(낮을수록 높음)
P1	0	7	3
P2	2	4	1
P3	4	1	2

8. 문제 - 스케줄링 알고리즘 위주

문제 P1. (SRTF 스케줄링 표)
컨텍스트 스위칭 오버헤드 0으로 가정.
프로세스 도착/버스트:
```
P1: arrival=0,  burst=8
P2: arrival=1,  burst=4
P3: arrival=2,  burst=9
P4: arrival=3,  burst=5
```
Q1. SRTF로 Gantt 차트를 그려라.

A1. SRTF는 Shorest Remaining Time First로 가장 CPU 예상 요구 시간이 적은 순서대로 할당하는 선점형 알고리즘이다. 따라서 Gantt 차트는 아래와 같이 그려진다.
```
|P1|--P2--|--P4--|----P1----|-----P3-----| 
 0  1      5      10         17           26
```
Q2. 각 프로세스 대기시간/반환시간/평균 대기시간을 구하라.
A2.
```
P1 : 9 / 17
P2 : 0 / 4
P3 : 15 / 24
P4 : 2 / 7
평균 대기시간 : 6.5
```

문제 P2. (RR with q=3)
동일한 잡으로 Round Robin(q=3) 스케줄링을 수행하라.

Q1. Gantt 차트, 평균 대기/반환시간.
A1.

  
|--P1--|--P2--|--P3--|--P4--|--P1--|--P2--|--P3--|--P4--|--P1--|--P3--|
0      3      6      9      12     15     16     19     21     23     26
평균 대기시간 : (18+11+19+15)/4 = 15.75
평균 반환시간 : 15.75 + (8+4+9+5)/4 = 15.75 + 6.5 = 22.25

Q2. 컨텍스트 스위칭 오버헤드 = 1 단위 시간이라고 추가 가정하고, 총 소요에 반영하라.
A2.


|--P1--| |--P2--| |--P3--| |--P4--| |--P1--| |--P2--| |--P3--| |--P4--| |--P1--| |--P3--|
0      3 4      7 8      1112     1516     1920     2122     2526     2829     3132     35
평균 대기시간 : (23+16+24+20)/4 = 20.75
평균 반환시간 : 20.75 + 6.5 = 27.25

문제 P3. (MLFQ 시뮬 기초)
규칙:
1) Q0(q=2) > Q1(q=4) > Q2(FCFS), 우선순위는 Q0>Q1>Q2
2) 새 작업은 Q0 시작. 타임슬라이스 소진 시 강등, I/O로 일찍 양보 시 유지
3) 20단위마다 전원 승격(Q2→Q1→Q0)

잡(도착/버스트, I/O):
```
A: t=0,  CPU burst 12      (I/O 없음)
B: t=1,  CPU burst 1, I/O 4, CPU 3  (I/O 후 CPU 3)
C: t=2,  CPU burst 6
```
A1. 0~25 구간의 큐 이동과 실행 타임라인을 간단히 적어라.
```
CPU : |A(Q0)|B(Q0)|C(Q0)|A(Q1)|B(Q0)|A(Q1)|C(Q1)|B(Q1)|A(Q2)|
      0     2     3     5     7     9     11    15    16    22
I/O :             |-----B-----|
                  3           7
```

문제 P4. (주관식)

Q1. PCB에 반드시 들어가는 3가지 항목은?
A1. ~~PID~~, 레지스터 스냅샷, 스케줄링 정보, 상태(state)

Q2. 컨텍스트 스위칭 때 비싼 두 가지 하드웨어 요인은?
A2. 레지스터 변경, 캐시 오염(TLB flust/refill, 분기예측기 오염)

Q3. SJF vs SRTF의 차이는?
A3. 비선점형 / 선점형

Q4. Aging이 필요한 이유는?
A4. 우선순위가 낮은 경우 평생 밀려서 = 기아(Starvation)

Q5. MLFQ에서 “타임슬라이스를 다 쓰면 강등” 규칙이 의미하는 바는?
A5. ~~공정한 CPU 타임 배분~~ CPU-bound 자동 인식 후 우선순위 낮춤