시스템 & 인프라/PintOS & CS

[PintOS/운영체제] Project 1 Threads 개념 정리: 스케줄링·동기화·MLFQS

kugorang 2024. 3. 17. 23:56
728x90

TL;DR (세 줄 요약)

  1. PintOS Project 1 Threads 과제를 하려면 프로세스와 스레드, CPU 스케줄링, 동기화, 경쟁 상태, 교착 상태, 문맥 교환, MLFQS를 설명할 수 있어야 합니다.
  2. CPU 코어 하나는 한 번에 작업 하나만 실행합니다. 그래서 운영체제는 스케줄러로 실행 순서를 정하고, 락과 세마포어로 공유 데이터에 접근하는 순서를 지키게 하고, 작업을 바꿀 때 문맥을 저장하고 복원합니다.
  3. 각 개념을 정의, 원인, 대표 방법 순서로 정리하면 Alarm Clock, Priority Scheduling, MLFQS 구현이 무엇을 요구하는지 알 수 있습니다.

이 글은 크래프톤 정글에서 KAIST PintOS를 팀 프로젝트로 구현하면서 정리한 기록입니다. 정글에서 제공한 가이드라인의 공부 키워드를 제 말로 다시 적었습니다. 구현 코드는 싣지 않고, 정의와 동작만 설명합니다.

초록색 배경에 모니터 모양 아이콘이 있고 그 아래에 KAIST PINTOS와 KRAFTON JUNGLE 글자가 적힌 그림
그림. DALL·E 3로 만든 KAIST PintOS와 Krafton Jungle 글자 그림

1. PintOS Project 1 Threads는 어떤 과제인가요?

PintOS는 운영체제 수업에서 쓰는 교육용 운영체제입니다. 운영체제는 프로그램이 CPU와 메모리 같은 컴퓨터 자원을 쓸 수 있게 관리하는 소프트웨어입니다. Project 1 Threads는 PintOS의 스레드 부분을 고치는 과제이고, 세 부분으로 나뉩니다.

부분하는 일
Alarm Clock스레드를 정해진 시간 동안 재우는 기능을 다시 구현합니다. 기다리는 동안 CPU를 계속 쓰지 않게 만듭니다.
Priority Scheduling우선순위가 높은 스레드가 먼저 실행되게 만듭니다.
Advanced Scheduler (MLFQS)스레드의 실행 이력을 보고 우선순위를 자동으로 계산하는 스케줄러를 만듭니다.

아래에서 이 과제에 필요한 개념을 하나씩 설명합니다.

2. 프로세스와 스레드는 무엇이 다른가요?

프로세스는 무엇인가요?

실행 중인 프로그램을 프로세스라고 부릅니다. 프로세스는 운영체제가 관리하는 작업의 단위입니다. 프로세스는 자기만의 주소 공간을 가집니다. 주소 공간은 그 프로세스가 쓸 수 있는 메모리 영역 전체입니다. 주소 공간에는 다음 네 가지가 들어 있습니다.

  • 코드: 실행할 명령어입니다.
  • 데이터: 전역 변수입니다.
  • 힙: 실행 중에 필요할 때 할당받는 공간입니다.
  • 스택: 함수 호출 정보와 지역 변수를 담는 공간입니다.

프로세스는 다른 프로세스의 메모리에 직접 접근할 수 없습니다. 자료를 주고받으려면 IPC를 써야 합니다. IPC(Inter-Process Communication)는 프로세스 사이에 데이터를 주고받는 방법이고, 파이프, 메시지 큐, 공유 메모리가 대표적입니다.

스레드는 무엇인가요?

스레드는 프로세스 안에서 실행되는 흐름의 단위입니다. 모든 프로세스에는 스레드가 최소 하나 있고, 이것을 메인 스레드라고 부릅니다.

항목프로세스스레드
주소 공간프로세스마다 따로 가집니다.같은 프로세스의 스레드끼리 코드, 데이터, 힙을 공유합니다.
따로 가지는 것주소 공간 전체스택과 레지스터 상태
생성, 종료, 전환 비용큽니다.주소 공간을 새로 만들지 않으므로 프로세스보다 작습니다.

레지스터는 CPU 안에 있는 작은 저장 칸입니다. CPU는 계산 중인 값과 다음에 실행할 명령어의 위치를 레지스터에 담아 둡니다.

함께 알아야 하는 용어는 무엇인가요?

  • 문맥 교환: CPU가 다른 작업으로 넘어갈 때 지금 작업의 상태를 저장하고 새 작업의 상태를 복원하는 일입니다. 저장하는 상태는 레지스터, 프로그램 카운터(다음에 실행할 명령어의 위치), 스택 포인터(스택의 현재 위치)입니다.
  • 동시성과 병렬성: 동시성은 시간을 나눠 가며 여러 작업을 번갈아 진행하는 것입니다. 병렬성은 실제로 같은 순간에 여러 코어에서 작업이 실행되는 것입니다. CPU 코어가 하나면 동시성만 가능합니다.
  • 동기화: 여러 스레드가 공유 자원을 쓸 때, 정해진 순서로 한 번에 정해진 수만 쓰도록 보장하는 기법입니다. 뮤텍스와 세마포어가 대표적입니다.

3. CPU 스케줄링에는 어떤 방식이 있나요?

CPU 스케줄링은 실행할 준비가 된 작업 중 무엇을 얼마나 오래 실행할지 정하는 일입니다. 방식마다 장점과 단점이 있습니다.

방식동작장점단점
FCFS (First-Come, First-Served)먼저 온 작업을 먼저 끝냅니다.구현이 가장 쉽습니다.긴 작업 하나가 뒤에 온 짧은 작업들을 오래 기다리게 합니다. 이것을 호위 효과라고 부릅니다.
SJF (Shortest Job First)실행 시간이 짧은 작업부터 합니다.평균 대기 시간이 줄어듭니다.실행 시간을 미리 알아야 합니다. 긴 작업이 계속 밀릴 수 있습니다. 이것을 기아 상태라고 부릅니다.
RR (Round Robin)작업마다 같은 길이의 시간(타임 퀀텀)을 주고, 시간이 끝나면 다음 작업으로 넘깁니다.응답이 빠릅니다.퀀텀이 너무 짧으면 문맥 교환이 잦아집니다. 너무 길면 FCFS와 같아집니다.
Priority우선순위가 높은 작업부터 합니다.중요한 작업을 먼저 처리합니다.우선순위가 낮은 작업이 계속 밀릴 수 있습니다. 오래 기다린 작업의 우선순위를 올려 주는 에이징(aging)으로 보완합니다.
Multilevel Queue작업을 여러 큐로 나누고 큐마다 다른 방식을 씁니다. 예를 들어 대화형 작업은 RR, 배치 작업은 SJF를 씁니다.작업 종류에 맞는 방식을 쓸 수 있습니다.큐 사이의 우선순위를 어떻게 정하느냐에 따라 공정성이 달라집니다.
SRTF (Shortest Remaining Time First)SJF의 선점형 버전입니다. 새 작업이 도착했을 때 그 작업의 남은 시간이 더 짧으면, 실행 중인 작업을 멈추고 새 작업을 실행합니다.평균 대기 시간이 가장 짧습니다.문맥 교환이 잦습니다. 기아 상태가 생길 수 있습니다.

선점형은 운영체제가 실행 중인 작업을 중간에 멈추고 CPU를 다른 작업에 줄 수 있는 방식입니다. 큐는 먼저 넣은 것이 먼저 나오는 자료구조이고, 여기서는 작업이 차례를 기다리는 줄을 뜻합니다. 대화형 작업은 사용자의 입력에 바로 반응해야 하는 작업이고, 배치 작업은 사용자와 주고받는 일 없이 한꺼번에 처리하는 작업입니다.

상용 운영체제는 무엇을 쓰나요?

  • Windows: 선점형 멀티태스킹과 우선순위 기반 스케줄링을 씁니다. 화면에 보이는 작업이 빨리 반응하도록 우선순위를 실행 중에 조정합니다.
  • macOS: Mach를 바탕으로 만든 XNU 커널에서 우선순위와 QoS(Quality of Service) 등급을 씁니다. QoS 등급은 작업이 얼마나 급한지를 나타내는 표시입니다. 사용자 인터페이스와 멀티미디어 작업의 반응을 우선합니다.
  • Linux: 커널 2.6.23부터 CFS(Completely Fair Scheduler)를 썼습니다. CFS는 각 작업이 지금까지 받은 실행 시간을 기록하고, 실행 시간을 적게 받은 작업에 CPU를 먼저 줍니다. 커널 6.6부터는 EEVDF(Earliest Eligible Virtual Deadline First) 스케줄러가 CFS를 대신합니다.

4. 뮤텍스와 세마포어는 무엇이 다른가요?

뮤텍스는 무엇인가요?

뮤텍스(Mutex)는 상호 배제(Mutual Exclusion)를 줄인 말입니다. 한 번에 스레드 하나만 공유 자원을 쓸 수 있게 합니다. 스레드는 자원을 쓰기 전에 잠그고(lock), 다 쓰면 풉니다(unlock). 잠근 스레드만 풀 수 있습니다.

세마포어는 무엇인가요?

세마포어(Semaphore)는 정수 값을 하나 가진 동기화 도구입니다. 이 값은 자원을 동시에 쓸 수 있는 스레드의 수입니다.

  • 자원을 쓰기 전에 값을 1 줄입니다. 이것을 P 연산이라고 부릅니다.
  • 자원을 다 쓰면 값을 1 늘립니다. 이것을 V 연산이라고 부릅니다.
  • 값이 0이면 값이 다시 늘어날 때까지 기다립니다.

값이 1인 세마포어는 뮤텍스처럼 동작합니다.

둘의 차이는 무엇인가요?

항목뮤텍스세마포어
동시에 허용하는 수1개정한 수만큼
소유권잠근 스레드만 풀 수 있습니다.다른 스레드가 값을 올릴 수 있습니다.
쓰는 곳한 번에 하나만 들어가야 하는 구간정해진 개수의 자원(연결 슬롯, 버퍼 칸)을 나눠 쓸 때

5. 경쟁 상태(Race Condition)는 무엇이고 어떻게 막나요?

경쟁 상태는 둘 이상의 스레드가 같은 데이터에 동시에 접근하고, 접근하는 순서에 따라 결과가 달라지는 문제입니다.

예를 들어 두 스레드가 같은 변수를 읽고, 각자 1을 더해서 저장한다고 가정합니다. 변수의 값이 0일 때 두 스레드가 모두 0을 읽으면, 둘 다 1을 저장합니다. 두 번 더했는데 결과는 1입니다. 같은 코드를 실행해도 실행할 때마다 결과가 달라질 수 있습니다. 그래서 문제를 다시 일으켜 보기도 어렵고 원인을 찾기도 어렵습니다.

어떤 도구로 막나요?

도구하는 일
락공유 데이터를 쓰는 구간에 들어가기 전에 잠그고, 나올 때 풉니다.
뮤텍스소유권이 있는 락입니다.
세마포어동시에 들어갈 수 있는 개수를 정해 제한합니다.
모니터락과 조건 변수를 하나로 묶은 것입니다. 한 번에 스레드 하나만 메서드를 실행하게 합니다.
원자적 연산중간에 끊기지 않는 연산입니다. 읽기와 쓰기를 한 번에 처리합니다.
조건 변수조건이 만족될 때까지 스레드를 기다리게 하고, 조건이 만족되면 기다리는 스레드를 깨웁니다. 뮤텍스와 함께 씁니다.

PintOS에서는 스레드 스케줄링, 파일 시스템, 메모리 할당처럼 여러 스레드가 함께 쓰는 곳에 이 도구들을 써서 경쟁 상태를 막습니다.

상용 운영체제에는 어떤 동기화 도구가 있나요?

  • Windows: CriticalSection, Mutex, Semaphore, Event를 씁니다. CriticalSection은 같은 프로세스 안에서만 쓸 수 있고 Mutex보다 가볍습니다. Mutex는 프로세스 사이에서도 쓸 수 있습니다.
  • Linux: Mutex, Semaphore, Spinlock, Barrier를 씁니다. Spinlock은 잠금이 풀릴 때까지 CPU를 쓰면서 계속 확인하는 락입니다. 기다리는 시간이 아주 짧을 때 씁니다.
  • macOS: Mutex, Semaphore, 조건 변수, Dispatch Queue(GCD)를 씁니다. GCD(Grand Central Dispatch)는 스레드 관리와 작업 분배를 대신 처리합니다.

6. 교착 상태(Deadlock)는 언제 생기고 어떻게 해결하나요?

교착 상태는 둘 이상의 스레드가 서로가 가진 자원을 기다리느라 아무도 진행하지 못하는 상태입니다.

예를 들어 스레드 A가 자원 1을 가진 채 자원 2를 기다립니다. 스레드 B는 자원 2를 가진 채 자원 1을 기다립니다. 이때 두 스레드 모두 다음 단계로 넘어가지 못합니다.

어떤 조건에서 생기나요?

다음 네 조건이 모두 성립할 때 교착 상태가 생길 수 있습니다.

  1. 상호 배제: 자원은 한 번에 스레드 하나만 쓸 수 있습니다.
  2. 보유 대기: 스레드가 자원 하나를 가진 채 다른 자원을 기다립니다.
  3. 비선점: 다른 스레드가 가진 자원을 강제로 빼앗을 수 없습니다.
  4. 순환 대기: A는 B의 자원을 기다리고 B는 A의 자원을 기다리는 식으로, 기다림이 고리 모양으로 이어집니다.

어떻게 해결하나요?

방법내용
예방네 조건 중 하나를 없앱니다. 예를 들어 필요한 자원을 모두 한 번에 잡게 하거나, 정해진 순서로만 잡게 합니다.
회피자원을 줄 때 교착 상태가 생길 수 있는지 계산하고, 안전한 경우에만 줍니다. 은행원 알고리즘이 이 방법입니다.
탐지와 회복주기적으로 교착 상태를 찾습니다. 찾으면 해당 스레드를 중단하거나 자원을 회수합니다.

7. 문맥 교환에는 왜 비용이 드나요?

CPU 코어 하나는 한 번에 작업 하나만 실행합니다. 여러 작업이 동시에 실행되는 것처럼 보이는 이유는 아주 짧은 간격으로 작업을 바꾸기 때문입니다. 작업을 바꿀 때 현재 작업의 문맥을 메모리에 저장하고, 다음 작업의 문맥을 CPU에 올립니다.

어떤 비용이 드나요?

  • 문맥을 저장하고 복원하는 데 시간이 듭니다.
  • 캐시 미스가 늘어납니다. CPU 캐시는 자주 쓰는 데이터를 CPU 가까이에 두는 작고 빠른 메모리입니다. 새 작업의 코드와 데이터는 캐시에 없어서 더 느린 메모리에서 가져와야 합니다. 이것을 캐시 미스라고 부릅니다.

그래서 작업을 너무 자주 바꾸면 같은 시간에 처리하는 일의 양이 줄어듭니다. 타임 슬라이스(작업 하나에 주는 시간) 조정, 우선순위 조정, 대기 중인 스레드 관리로 전환 횟수를 줄입니다.

프로세스 전환과 스레드 전환은 무엇이 다른가요?

프로세스는 주소 공간이 서로 다릅니다. 그래서 프로세스를 바꿀 때는 페이지 테이블까지 바꿔야 해서 비용이 큽니다. 페이지 테이블은 프로그램이 쓰는 주소를 실제 메모리 위치로 바꿔 주는 표입니다. 같은 프로세스의 스레드는 같은 주소 공간을 씁니다. 그래서 스택과 레지스터만 바꾸면 되고 비용이 상대적으로 작습니다.

우선순위 역전은 무엇인가요?

우선순위가 낮은 스레드가 락을 잡고 있는 동안, 우선순위가 높은 스레드가 그 락을 기다리는 상황이 있습니다. 이때 우선순위가 높은 작업이 낮은 작업 때문에 밀립니다. 이것을 우선순위 역전이라고 부릅니다.

해결 방법은 우선순위 상속입니다. 락을 잡은 낮은 우선순위 스레드의 우선순위를 잠시 올려 줍니다. 그러면 그 스레드가 먼저 실행되어 락을 빨리 풉니다. PintOS 과제에서는 이것을 우선순위 기부(priority donation)라고 부릅니다.

8. MLFQS는 어떻게 동작하나요?

MLFQS(Multi-Level Feedback Queue Scheduler)는 여러 단계의 큐를 두고, 실행 이력에 따라 스레드의 우선순위를 계속 바꾸는 스케줄러입니다.

  • 우선순위가 높은 큐에 있는 스레드부터 실행합니다.
  • CPU를 많이 쓴 스레드는 우선순위가 내려가 낮은 큐로 갑니다.
  • 오래 기다린 스레드나 I/O(입출력) 때문에 대기한 스레드는 우선순위가 올라갑니다.
  • 일정한 주기마다 모든 스레드의 우선순위를 다시 계산합니다.

PintOS의 advanced scheduler가 이 방식입니다. 계산에 쓰는 값은 다음과 같습니다. tick은 타이머가 일정한 간격으로 보내는 신호 한 번이고, PintOS가 시간을 세는 단위입니다.

값뜻계산
nice스레드가 다른 스레드에게 CPU를 얼마나 양보하는지 나타냅니다.-20에서 20까지입니다. 값이 클수록 더 많이 양보합니다.
recent_cpu스레드가 최근에 CPU를 얼마나 썼는지 나타냅니다.실행 중인 스레드의 값을 tick마다 1씩 늘립니다. 1초마다 모든 스레드의 값을 load_avg를 써서 줄이고 nice를 더합니다.
load_avg최근 1분 동안 실행 중이거나 실행을 기다린 스레드 수의 평균을 어림한 값입니다.1초마다 다시 계산합니다.
priority스레드의 우선순위입니다.PRI_MAX - (recent_cpu / 4) - (nice * 2)

PRI_MAX는 가장 높은 우선순위 값입니다. recent_cpu가 크거나 nice가 크면 우선순위가 낮아집니다.

4BSD 스케줄러와 nice는 무엇인가요?

4BSD 스케줄러는 UNIX 계열 운영체제인 4.4BSD에서 쓰인 스케줄러입니다. PintOS의 advanced scheduler는 이 스케줄러를 본떠 만듭니다. 사용자와 상호작용하는 작업은 CPU를 자주 양보합니다. 4BSD 스케줄러는 이런 작업의 우선순위를 올리고, CPU를 오래 쓰는 작업의 우선순위를 내립니다.

nice는 이 기본 우선순위를 사용자가 조정하는 값입니다. 값을 올리면 우선순위가 낮아지고, 내리면 높아집니다. 기본값은 0입니다. UNIX 계열 운영체제의 nice 범위는 보통 -20에서 19까지이고, PintOS 과제의 nice 범위는 -20에서 20까지입니다.

여기까지가 PintOS Threads 과제를 위해 정리한 키워드입니다. 개념의 동작 원리를 설명할 수 있어야 Alarm Clock, Priority Scheduling, MLFQS를 실제로 구현할 수 있었습니다. 과제 소개는 KAIST PintOS Project 1 소개 문서에서 볼 수 있습니다.

자주 묻는 질문 (FAQ)

Q1. 프로세스와 스레드는 무엇이 다른가요?

프로세스는 자기 주소 공간을 가진 실행 단위입니다. 스레드는 프로세스 안에서 실행되는 흐름입니다. 같은 프로세스의 스레드는 코드, 데이터, 힙을 공유하고, 스택과 레지스터만 따로 가집니다. 그래서 스레드는 프로세스보다 생성과 전환 비용이 작습니다.

Q2. 뮤텍스와 세마포어는 언제 각각 쓰나요?

한 번에 스레드 하나만 들어가야 하는 구간에는 뮤텍스를 씁니다. 정해진 개수의 자원을 여러 스레드가 나눠 써야 할 때는 값이 1보다 큰 세마포어를 씁니다. 세마포어의 값이 1이면 뮤텍스처럼 동작합니다.

Q3. MLFQS의 priority는 어떻게 계산하나요?

priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)로 계산합니다. recent_cpu가 크면 우선순위가 낮아집니다. nice가 크면 다른 스레드에게 양보한다는 뜻이므로 우선순위가 더 낮아집니다. 계산한 값은 PRI_MIN과 PRI_MAX 사이로 제한합니다.

수정 안내

이 글은 2026년 11월 21일에 다시 썼습니다. Linux 스케줄러 설명에 커널 6.6부터 EEVDF가 CFS를 대신한다는 내용을 더했습니다. Windows CriticalSection을 "가장 빠르다"고 적은 표현은 근거를 확인할 수 없어 "Mutex보다 가볍다"로 고쳤습니다. "CPU는 한 번에 하나만 실행한다"는 설명은 "CPU 코어 하나는"으로 고쳤습니다. nice 범위가 -20~20과 -20~19로 다르게 적혀 있던 부분은 각각 PintOS 과제와 UNIX 계열 운영체제의 값임을 밝혔습니다. recent_cpu를 1초마다 다시 계산할 때 nice를 더한다는 내용을 보충했습니다.

참고 자료

같은 주제의 다른 글: [CS:APP/C언어] Malloc Lab 사전 지식: 힙, 가용 리스트, 병합, 파편화, [게임 인프라] 게임 운영체제(OS) 비교: 콘솔, PC, 모바일은 무엇이 다른가

728x90
728x90