KAIST PintOS - Project 01: Threads

들어가며

DALL·E3가 제작한 Krafton Jungle의 KAIST PintOS 로고

현재 크래프톤 정글에서 KAIST PintOS를 구현하기 위해 개념 공부 및 팀 프로젝트를 진행하고 있다.

이 글에서는 크래프톤 정글에서 제공하는 가이드라인에 적힌 공부 키워드를 바탕으로 내가 이해하기 쉽도록 정리한 내용을 하나의 포스팅에 모아 다시 정리하는 것을 목표로 한다.

Process, Thread

Process (프로세스)

• 프로세스는 실행 중인 프로그램을 말함
• 운영 체제가 관리하는 작업의 단위로, 코드, 데이터, 힙(동적 할당 공간), 스택(함수 호출 시 매개변수, 지역 변수 등을 저장하는 공간) 등을 포함한 자신만의 독립된 메모리 공간을 가짐
• 프로세스는 최소 하나 이상의 스레드를 가지고 있음
• 각 프로세스는 별도의 주소 공간에서 실행되어 다른 프로세스와 자원을 공유하지 않음
• 프로세스 간 통신을 위해서는 Inter-Process Communication(IPC) 기법을 사용해야 함

Thread (스레드)

• 스레드는 프로세스 내에서 실행되는 흐름의 단위
• 모든 프로세스는 최소 하나의 스레드, 즉 메인 스레드를 가지고 있음
• 스레드는 프로세스 내에서 코드, 데이터, 힙 영역을 공유하지만, 스택과 레지스터 상태 등은 독립적으로 가짐
• 스레드는 프로세스의 자원을 이용해 실행되므로 프로세스보다 생성, 종료, 문맥 교환의 비용이 적음
• 다중 스레드를 사용하면 병렬 실행을 통해 작업 처리 효율을 높일 수 있음

연관 키워드

• Context Switching (문맥 교환): CPU가 이전의 프로세스 또는 스레드에서 다음 작업으로 전환할 때, 상태 정보를 저장하고 복원하는 과정
• IPC (Inter-Process Communication): 프로세스들이 데이터를 주고받는 방법. 파이프, 메시지 큐, 공유 메모리 등이 있음
• Concurrency (동시성): 여러 작업이 시간을 나누어 CPU 자원을 사용하는 것을 말함. 동시성은 병렬성(Parallelism)과는 다른 개념(병렬성은 여러 작업이 실제로 동시에 실행되는 것을 의미).
• Synchronization (동기화): 다중 스레드 환경에서 스레드들이 안전하게 자원을 공유할 수 있도록 제어하는 기법으로 뮤텍스, 세마포어 등이 있음

비유적 설명

프로세스는 회사

• 회사(프로세스): 각 회사는 자신만의 건물(메모리 공간)을 가지고 있음. 이 건물 안에서는 여러 가지 일(작업)이 일어남. 회사마다 다른 건물에 있기 때문에, 한 회사의 일이 다른 회사에 직접적인 영향을 주지 않음. 만약 두 회사가 정보를 주고받고 싶다면, 전화나 이메일처럼 특별한 방법을 사용해야 함
• 회사 건물(프로세스의 메모리 공간): 회사 건물 안에는 사무실, 회의실, 창고 등 여러 공간이 있음. 이것처럼 프로세스 안에도 코드, 데이터, 힙, 스택 등 다양한 영역이 있음

스레드는 회사에서 일하는 사람들

• 직원(스레드): 회사 안에서 일하는 각각의 사람들. 모든 회사에는 최소한 한 명의 직원(메인 스레드)이 있음. 이 직원들은 회사의 자원(메모리 공간)을 공유해서 사용하지만, 각자의 업무 일정표(스택)는 따로 가지고 있음
• 팀워크(스레드의 협업): 여러 직원이 함께 일할 때 더 많은 일을 빠르게 할 수 있음. 그러나 서로 잘 협력해야 하고, 같은 자료를 쓸 때는 차례를 지켜야 해서 서로 방해하지 않도록 주의해야 함

요약

• 프로세스는 독립된 회사처럼 각자의 공간에서 일하는 큰 틀
• 스레드는 그 회사 안에서 일하는 직원들로, 함께 일해서 회사의 목표를 달성

CPU Scheduling 알고리즘

CPU 스케줄링

• 운영 체제가 프로세스와 스레드에 CPU 시간을 어떻게 배분할지 결정하는 과정
• 다양한 스케줄링 알고리즘이 있으며, 각각의 알고리즘은 특정 상황에서 장단점을 가지고 있음

1. FCFS (First Come, First Served)

• 설명: 가장 간단한 스케줄링 알고리즘. 먼저 온 프로세스를 먼저 처리. 줄을 서서 기다리는 사람들처럼, 먼저 온 순서대로 서비스를 받게 됨
• 장점: 구현이 매우 쉬움
• 단점: "호위 효과(Convoy effect)"가 발생할 수 있음. 이는 긴 작업 때문에 짧은 작업들이 오랫동안 대기해야 하는 현상을 말함

2. SJF (Shortest Job First)

• 설명: 실행 시간이 가장 짧은 프로세스를 먼저 처리. 모든 작업의 실행 시간을 미리 알고 있어야 효과적으로 작동
• 장점: 평균 대기 시간을 줄일 수 있음
• 단점: 실행 시간이 긴 프로세스가 계속해서 대기 상태에 놓일 수 있는 "기아 상태(Starvation)" 문제가 발생할 수 있음

3. RR (Round Robin)

• 설명: 각 프로세스에 동일한 시간(타임 퀀텀)만큼 CPU를 할당하고, 할당 시간이 끝나면 다음 프로세스에게 넘어감. 모든 프로세스가 공평하게 CPU 시간을 할당 받을 수 있음
• 장점: 응답 시간이 빨라지고, 모든 프로세스가 공정하게 처리
• 단점: 타임 퀀텀의 크기에 따라 시스템의 성능이 크게 달라질 수 있음. 너무 짧으면 문맥 교환 오버헤드가 커지고, 너무 길면 FCFS와 비슷해짐

4. Priority Scheduling

• 설명: 각 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 처리
• 장점: 중요한 작업을 먼저 처리할 수 있음
• 단점: 낮은 우선순위의 프로세스가 기아 상태에 빠질 수 있음

5. Multilevel Queue Scheduling

• 설명: 프로세스를 여러 큐에 분류하고, 각 큐에 다른 스케줄링 알고리즘을 적용. 예를 들어, 하나의 큐는 RR을 사용하고 다른 큐는 SJF를 사용할 수 있음
• 장점: 다양한 종류의 프로세스를 효율적으로 관리할 수 있음
• 단점: 큐 사이의 우선순위를 어떻게 설정 하느냐에 따라 공정성 문제가 발생할 수 있음

6. SRTF (Shortest Remaining Time First)

• 설명: SJF(Shortest Job First)의 선점형(preemptive) 버전. 현재 실행 중이거나 대기 중인 프로세스 중에서 남은 실행 시간이 가장 짧은 프로세스에 CPU를 할당. 새로운 프로세스가 도착하면 현재 실행 중인 프로세스의 남은 실행 시간과 새 프로세스의 전체 실행 시간을 비교하여, 새 프로세스의 실행 시간이 더 짧다면 즉시 현재 실행 중인 프로세스를 중단하고 새 프로세스에게 CPU를 넘겨줌. 이 과정은 모든 프로세스가 완료될 때까지 반복
• 장점: 평균 대기 시간과 평균 응답 시간을 SJF보다 더 줄일 수 있고, 짧은 작업이 빠르게 처리되어 사용자에게 빠른 피드백을 제공할 수 있음
• 단점: 실행 시간을 미리 알아야 하며, 이는 실제 환경에서 어려울 수 있음. 빈번한 문맥 교환(context switching)으로 인해 오버헤드가 증가할 수 있고 기아 상태(starvation)가 발생할 수 있음. 즉, 실행 시간이 긴 프로세스는 계속해서 실행 기회를 얻지 못할 수 있음
• 기타: SRTF는 SJF의 변형으로, SJF에 대한 이해가 선행되어야 함. SRTF는 특히 평균 대기 시간을 최소화하는 측면에서 중요한 알고리즘. 실시간 시스템(real-time systems)이나 요구 사항이 엄격한 시스템에서 유용하게 사용될 수 있으며, 스케줄링 알고리즘을 공부하는 데 있어 중요한 개념

비유적 설명

CPU 스케줄링은 컴퓨터가 할 일을 어떤 순서로 할지 결정하는 방법

1. 줄 서기(FCFS, First Come First Served)

• 설명: 놀이 공원에서 놀이기구를 타기 위해 줄을 선 것처럼, 먼저 온 순서대로 일을 처리하는 방법
• 예시: 첫 번째로 온 친구가 놀이기구를 타고, 다음으로 온 친구가 그 다음으로 타는 것

2. 가장 짧은 일 먼저(SJF, Shortest Job First)

• 설명: 할 일 중에서 가장 시간이 적게 걸리는 일을 먼저 하는 방법
• 예시: 숙제를 할 때, 10분짜리 수학 숙제부터 시작해서 30분짜리 과학 숙제를 나중에 하는 것

3. 번갈아 가며(RR, Round Robin)

• 설명: 친구들과 게임을 할 때, 각자 정해진 시간 동안만 게임을 하고 다음 친구에게 차례를 넘기는 방식
• 예시: 각자 5분씩 번갈아 가며 게임을 하는 것처럼, 컴퓨터도 일을 조금씩 번갈아 가며 처리

4. 가장 중요한 일 먼저(Priority Scheduling)

• 설명: 할 일 중에서 가장 중요한 일부터 먼저 하는 방법
• 예시: 숙제 중에서 내일 제출해야 하는 숙제를 먼저 하고, 다음 주에 제출하는 숙제는 나중에 하는 것

5. 가장 짧게 남은 일 먼저(SRTF, Shortest Remaining Time First)

• 설명: 시작한 일 중에서 가장 빨리 끝낼 수 있는 일을 먼저 끝내는 방법
• 예시: 숙제를 하다가, 5분만 더 하면 끝날 수 있는 숙제가 있다면, 그 숙제를 먼저 끝내고 다른 숙제를 하는 것

6. 각자가 각자의 규칙대로(Multilevel Queue Scheduling)

• 설명: 여러 줄을 만들어서 각자의 특성에 맞게 차례를 기다리고 일을 처
• 예시: 놀이 공원에서 빠른 패스를 가진 아이들은 빠른 패스 줄에서, 일반 티켓을 가진 아이들은 일반 줄에서, 아이들만 탈 수 있는 놀이기구는 아이들만의 줄에서 기다리게 됨. 각 줄은 자기들만의 규칙으로 움직임

상용 운영체제의 CPU 스케줄링 알고리즘

Windows, macOS, 그리고 Linux는 각기 다른 CPU 스케줄링 알고리즘을 사용. 이 세 운영 체제의 스케줄링 알고리즘을 이해하기 위해서는 각 운영 체제의 설계 철학과 목표를 알아야 함

Windows

• Windows는 주로 Preemptive Multitasking을 사용
  • 이는 운영 체제가 언제든지 현재 실행 중인 프로세스를 중단 시키고 다른 프로세스에게 CPU를 넘겨줄 수 있음을 의미
• Windows의 스케줄러는 Priority-based 알고리즘을 사용
  • 이는 각 프로세스에 우선순위를 할당하고 높은 우선순위를 가진 작업부터 먼저 처리
• Windows는 동적 우선순위 조정을 통해 사용자 인터페이스의 반응성을 높이는 데 중점을 둠
• 즉, 백그라운드 작업보다 사용자와 상호 작용하는 작업에 더 높은 우선순위를 부여해 반응성 유지

macOS

• macOS는 Mach kernel을 기반으로 하며, 이는 Fair-Share Scheduling을 사용
• 하지만 최신 버전의 macOS는 Preemptive Multitasking에 기반한 Priority-based Scheduling을 사용
• macOS는 특히 애플리케이션의 성능과 반응성에 중점을 두는데, 이는 사용자 경험을 최적화 하기 위함
• macOS는 다양한 우선순위와 QoS(Quality of Service) 태그를 사용하여 작업을 스케줄링하며, 시스템 자원을 효율적으로 관리
  • 이를 통해 멀티미디어 작업과 사용자 인터페이스 작업이 원활하게 실행될 수 있도록 함

Linux

• Linux는 Completely Fair Scheduler (CFS)를 사용
• CFS는 이름에서 알 수 있듯이 모든 프로세스에게 공정한 CPU 시간을 할당하려고 함
• 각 프로세스가 실행 필요 시간을 기반으로 CPU 사용 시간을 할당 받으며, 이를 통해 시스템 반응성과 처리량을 최적화
• Linux 스케줄러는 시간 분할(time slice)을 프로세스 간에 공평하게 분배하여, 모든 작업이 적절한 시간 내에 실행될 수 있도록 함
• CFS는 매우 동적인 스케줄링 방식으로, 실시간 작업과 일반 작업 사이의 균형을 잘 맞추기 위해 설계

요약

• Windows는 사용자의 반응성을 중요시하며, 우선순위 기반 스케줄링을 사용해 이를 달성
• macOS는 사용자 경험을 최우선으로 하며, 우선순위 및 QoS를 통해 작업을 관리
• Linux는 모든 프로세스에 공정한 CPU 시간을 할당하고자 하는 CFS를 사용

Semaphore와 Mutex

주요 차이

• 뮤텍스는 한 번에 하나의 스레드만 자원에 접근할 수 있도록 함
• 세마포어는 동시에 여러 스레드가 접근할 수 있도록 할 수 있는 유연성을 제공

용도

• 뮤텍스는 상호 배제를 명확하게 보장해야 할 때 사용
• 세마포어는 한정된 수의 자원을 여러 스레드가 사용해야 할 때 유용

Mutex (뮤텍스)

기본 개념

뮤텍스는 상호 배제(Mutual Exclusion)의 줄임말로, 동시에 하나의 스레드만이 특정 자원을 사용할 수 있도록 하는 동기화 메커니즘

사용법

• 어떤 스레드가 공유 자원에 접근하려면 먼저 뮤텍스를 "잠그고"(lock) 자원을 사용한 후에 "풀어주어야"(unlock) 함
• 이렇게 함으로써 다른 스레드가 동시에 같은 자원에 접근하는 것을 방지

Semaphore (세마포어)

기본 개념

• 세마포어는 뮤텍스와 유사하지만, 동시에 여러 스레드가 특정 자원에 접근할 수 있도록 허용하는 정수형 변수
• 세마포어의 값은 동시에 자원에 접근할 수 있는 스레드의 최대 수를 나타냄

사용법

• 스레드가 자원을 사용하려면 세마포어를 "감소"(P 연산)시키고, 자원 사용이 끝나면 "증가"(V 연산)시킴
• 세마포어의 값이 0이면, 모든 자원이 사용 중이라는 의미이며, 다른 스레드는 자원이 해제될 때까지 기다려야 함

---

쉬운 설명

• 뮤텍스는 "한 번에 하나만"이라는 규칙을 지키게 해줌
• 세마포어는 "동시에 여러 개까지는 괜찮아"라는 규칙을 만들어 줌
• 이런 방식으로, 여러 사람이 함께 놀이를 할 때 규칙을 정해서 서로 싸우지 않도록 도와줌

뮤텍스(Mutex)

• 뮤텍스는 '화장실 열쇠'. 학교에는 화장실이 하나 있고, 열쇠도 딱 하나라고 가정
• 화장실을 사용하고 싶은 학생이 열쇠를 가지고 있으면, 그 학생만 화장실을 사용할 수 있음
• 다른 친구들은 그 친구가 화장실을 다 사용하고 열쇠를 돌려줄 때까지 기다려야 함
• 이처럼 뮤텍스는 한 번에 한 사람(혹은 스레드)만이 '화장실'(자원)을 사용할 수 있도록 '열쇠'(접근 권한)를 제어

세마포어(Semaphore)

• 세마포어는 '놀이공원 놀이기구 탑승 티켓'이라고 생각
• 놀이공원에 가면 놀이기구는 많지만 한 놀이기구에 동시에 탈 수 있는 자리는 제한되어 있음
• 예를 들어 5명만 탈 수 있다고 할 때, 놀이기구를 타고 싶은 사람들은 티켓을 받아야 하고, 티켓이 있어야만 탈 수 있음
• 티켓이 5장 있으면 동시에 5명까지 탈 수 있고, 누군가 놀이기구를 타고 내리면 그 티켓을 다음 대기자에게 줄 수 있음
• 이렇게 세마포어는 한 번에 여러 사람(스레드)이 '놀이기구'(자원)를 사용할 수 있도록 '티켓'(접근 권한)의 수를 관리

차이점 이해

뮤텍스

딱 한 명만 사용할 수 있는 '화장실'이 있을 때, 그 한 명이 사용할 수 있게 해주는 '화장실 열쇠'

세마포어

한 번에 여러 명이 사용할 수 있는 '놀이공원 놀이기구'가 있을 때, 그 여러 명이 사용할 수 있게 해주는 '탑승 티켓'

Race Condition

개요

• 두 개 이상의 프로세스나 스레드가 데이터의 동일한 부분에 동시에 접근하려고 할 때, 그 순서에 따라 실행 결과가 달라지는 문제
• 특히 운영 체제에서는 여러 스레드가 공유 자원에 접근할 때 이 문제가 자주 발생

Race Condition이란 무엇일까?

일반 설명

• 여러 프로그램(스레드나 프로세스)이 동시에 같은 데이터나 자원에 접근하려고 할 때 발생
• 이때, 어떤 프로그램이 먼저 데이터를 사용하느냐에 따라 최종 결과가 달라질 수 있음
• 문제는 이 과정이 항상 예측 가능하거나 일관되지 않고, 이렇게 되면 예상치 못한 결과나 오류 발생 가능

쉬운 설명

• 나와 친구가 같은 과자 봉지를 동시에 집으려고 함
• 둘 다 같은 과자를 잡으려고 손을 뻗지만, 누가 먼저 과자를 잡을지는 두 사람의 움직임에 달려 있음
• 이런 상황에서, 과자를 먼저 잡는 사람은 운이 좋거나 더 빠른 반응을 보인 사람

왜 Race Condition이 문제가 될까?

• 컴퓨터 프로그램은 정확하고 예측 가능한 결과를 내야 함
• 하지만 Race Condition 때문에, 같은 코드를 실행해도 다른 결과가 나올 수 있음
• 이는 프로그램의 신뢰성을 떨어뜨리고 버그를 찾기 어렵게 만듦

Race Condition을 알아야 하는 이유

• 데이터 일관성과 정확성: 공유 데이터에 대한 접근을 제대로 제어하지 않으면, 데이터의 일관성이 깨지고 잘못된 정보에 기반한 연산이 수행될 수 있음
• 디버깅의 어려움: Race Condition은 재현하기 어렵고, 때로는 특정 환경이나 조건에서만 발생하기 때문에 문제를 찾아내고 해결하기가 매우 어려울 수 있음
• 시스템의 안정성: Race Condition으로 인해 시스템이 예상치 못한 방식으로 동작할 수 있으며, 이는 시스템의 안정성을 저하시킬 수 있음

Race Condition 예방 방법

아래 도구들을 사용하면 프로그램에서 Race Condition을 방지하고, 데이터의 일관성과 안정성을 유지할 수 있음

1. 락(Lock) 사용: 공유 데이터에 접근하기 전에 락을 걸어 다른 스레드가 동시 접근하지 못하게 함. 모든 스레드가 공유 데이터를 사용할 때마다 이 락을 사용해야 함
2. 세마포어(Semaphore) 활용: 세마포어는 락과 비슷하지만, 한 번에 여러 스레드가 접근할 수 있는 '허용 개수'를 설정할 수 있음
3. 뮤텍스(Mutex) 이용: 뮤텍스는 락과 매우 유사하지만, 락을 건 스레드만이 그 락을 해제할 수 있다는 차이점이 있음
4. 모니터(Monitors): 모니터는 락과 조건 변수를 함께 사용하여 공유 데이터에 대한 접근을 관리하는 더 높은 수준의 동기화 메커니즘
5. 원자적 연산(Atomic Operations): 원자적 연산은 중단될 수 없는 연산으로, 이를 통해 공유 데이터의 수정을 안전하게 수행할 수 있음
6. 조건 변수(Condition Variable) 사용: 특정 조건이 만족될 때까지 스레드가 기다리게 하거나 조건이 만족될 때 스레드를 깨우는 방법으로 사용

조건 변수를 사용하여 Race Condition을 예방하는 방법

상황을 간단하게 만들기 위해, 한 개의 사과를 두고 두 명의 친구가 사과를 가져가려고 가정

1. 사과 바구니 확인: 첫 번째 친구가 사과 바구니를 확인. 만약 바구니에 사과가 없다면, 사과가 바구니에 들어올 때까지 기다려야 함
2. 조건 변수 사용: 첫 번째 친구는 "사과가 바구니에 들어오면 깨워주세요"라고 말하며 기다림. 이때 조건 변수를 사용하여 기다림. 이 조건 변수는 사과가 바구니에 들어왔는지를 체크하는 조건과 연결되어 있음
3. 사과 추가: 두 번째 친구가 바구니에 사과를 하나 넣음
4. 조건 충족 알림: 사과를 바구니에 넣은 후, 두 번째 친구는 "사과가 바구니에 들어왔어요!"라고 말하며 조건 변수를 통해 첫 번째 친구를 깨움
5. 사과 가져가기: 첫 번째 친구는 깨어나서 바구니에서 사과를 가져감

• 여기서 중요한 점은 첫 번째 친구가 사과가 바구니에 들어올 때까지 기다린다는 것
• 이렇게 조건 변수를 사용하면, 사과 바구니를 확인하는 동안 다른 친구가 사과를 가져가는 등의 Race Condition을 방지
• 조건 변수는 친구들이 서로 사과를 가져가는 순서를 조절하여, 누구도 빈 바구니를 만나지 않게 하고, 모두가 원하는 사과를 가져갈 수 있도록 도와줌

PintOS에서의 적용

• PintOS 프로젝트에서는 이러한 동기화 기법들을 구현하고 사용하여, Race Condition을 효과적으로 예방할 수 있음
• 예를 들어, 스레드 스케줄링, 파일 시스템 접근, 메모리 할당 등 다양한 시스템의 구성 요소에서 Race Condition이 발생할 수 있음
• 이를 위해 PintOS 내에서 락, 세마포어, 모니터 등을 적절히 사용해야 함

현대 상용 운영체제들의 동기화 메커니즘

Windows

Windows 운영체제는 주로 CriticalSection 객체, Mutexes, Semaphores, 그리고 Event 객체와 같은 동기화 기본 요소를 사용

• CriticalSection은 같은 프로세스 내의 스레드들 사이에서 사용되며, 가장 빠른 동기화 방법 중 하나. 하지만 프로세스 간에는 사용할 수 없음
• Mutexes는 프로세스 간 동기화에 사용될 수 있으며, 소유권 개념이 있어 어떤 스레드가 뮤텍스를 소유하고 있을 때만 해당 뮤텍스를 해제할 수 있음
• Semaphores와 Event 객체는 스레드 간의 특정 조건을 기반으로 동기화 제공

Linux

Linux 운영체제는 Mutexes, Semaphores, Spinlocks, 그리고 Barriers와 같은 동기화 기법 사용

• Mutexes는 상호 배제를 보장하며, 주로 사용자 공간의 동기화에 사용
• Spinlocks는 커널 내부에서 사용되며, 대기하는 동안 CPU 사이클을 소모하면서 계속 확인하는 방식으로 동작. Spinlocks는 대기 시간이 매우 짧을 것으로 예상되는 경우에 유용
• Semaphores는 스레드 또는 프로세스 간 동기화에 사용되며, 특히 리소스 카운팅에 유용
• Barriers는 여러 스레드가 특정 지점에서 동시에 계속 진행하기 전에 모두 도달할 때까지 기다리게 하는 동기화 방법

macOS

macOS(및 일반적으로 UNIX와 UNIX-라이크 시스템)는 Mutexes, Semaphores, Condition Variables 및 Dispatch Queues(특히 Grand Central Dispatch에서 사용)와 같은 동기화 기법 사용

• Grand Central Dispatch(GCD)는 작업 기반 병렬 처리와 함께 스레드 풀 관리를 추상화하며, Race Condition을 방지하는 고수준 API 제공
• GCD는 효율적인 스레드 사용과 작업 분산을 위해 설계

각기 다른 동기화 기법 선택의 이유

• 성능: 특정 동기화 메커니즘이 다른 메커니즘보다 더 빠르게 작동할 수 있음. 예를 들어, Spinlocks는 대기 시간이 짧은 경우에 유용
• 용도: 특정 동기화 기법은 특정 상황(예: 프로세스 간 동기화, 커널 내 동기화 등)에 더 적합할 수 있음
• 추상화 수준: 고수준 동기화 기법(예: GCD)은 개발자가 복잡한 동기화 로직을 직접 관리하지 않아도 되게 해주며, 코드의 가독성과 유지 보수성 향상

필수 연관 키워드

1. 동기화(Synchronization)
   • Race Condition을 방지하기 위해 동기화 기법 사용
   • 동기화는 코드의 특정 부분을 한 번에 하나의 스레드만 실행할 수 있도록 보장함으로써, 데이터 일관성과 정확성 유지
2. 뮤텍스(Mutex)
   • Mutual Exclusion(상호 배제)의 약자
   • 공유 자원에 대한 접근을 스레드간에 상호 배제하기 위해 사용
   • 뮤텍스는 한 번에 하나의 스레드만 자원을 사용할 수 있도록 함
3. 세마포어(Semaphore)
   • 뮤텍스와 유사한 동기화 기법
   • 한 번에 여러 스레드가 자원을 사용할 수 있는 개수를 제한할 수 있음. 이는 카운터를 사용하여 관리
4. 모니터(Monitor)
   • 동기화를 위해 사용되는 고급 추상화 기법 중 하나
   • 모니터 내의 모든 메소드는 자동적으로 상호 배제되어, 한 시점에 하나의 스레드만이 모니터 내의 메소드를 실행
5. 조건 변수(Condition Variables)
   • 스레드가 특정 조건이 충족될 때까지 대기하게 하거나, 조건이 충족될 때 스레드를 깨우는 데 사용
   • 이는 보통 뮤텍스와 함께 사용되어 공유 데이터에 대한 조건적 접근을 관리
6. 우선순위 역전(Priority Inversion)
   • 낮은 우선순위 스레드가 높은 우선순위 스레드가 필요로 하는 자원을 점유하고 있을 때 발생하는 문제
   • Race Condition을 해결하는 과정에서 발생할 수 있으며, 우선순위 상속(Priority Inheritance) 같은 기법으로 해결 가능

Deadlock

개요

• 컴퓨터 시스템에서 두 개 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 무한히 대기하는 상태
• 이 상황에서는 어떤 프로세스도 다음 단계로 진행할 수 없어, 마치 교착 상태에 빠진 것처럼 보임

예시

• 두 친구가 퍼즐을 맞추고 있음. 친구 A는 가위를 가지고 있고, 친구 B는 풀을 가진 상태
• 친구 A가 퍼즐을 완성하기 위해 풀이 필요하고, 친구 B는 가위가 필요
• 하지만, 둘 다 자신이 가진 것을 내어주지 않고 상대방이 먼저 자신에게 필요한 것을 줄 때까지 기다림
• 결과적으로, 아무도 퍼즐을 완성할 수 없는 상태가 되어 버림

발생 조건

데드락이 발생하기 위해서는 다음 네 가지 조건이 모두 충족되어야 함

1. 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 사용할 수 있음
2. 보유 대기(Hold and Wait): 프로세스가 최소한 하나의 자원을 보유한 상태로, 다른 프로세스가 보유한 자원을 추가로 얻기 위해 대기
3. 비선점(No Preemption): 프로세스가 자원을 스스로 내어놓기 전까지, 다른 프로세스가 그 자원을 빼앗을 수 없음
4. 순환 대기(Circular Wait): 프로세스의 집합에서 P1은 P2가 가진 자원을 기다리고, P2는 P3가 가진 자원을 기다리며, 이런 식으로 순환적으로 대기. 마지막 프로세스는 P1이 가진 자원을 기다림

데드락 해결 방법

데드락을 해결하고 예방하기 위한 몇 가지 방법이 있음

• 데드락 예방(Deadlock Prevention): 네 가지 데드락 조건 중 하나 이상이 발생하지 않도록 시스템을 설계
• 데드락 회피(Deadlock Avoidance): 자원 할당 시 데드락의 가능성을 고려하여, 안전한 상태에서만 자원을 할당
• 데드락 탐지 및 회복(Deadlock Detection and Recovery): 시스템이 데드락을 탐지하고, 데드락을 해결하기 위해 프로세스를 중단시키거나 자원을 선점
• 자원 할당 그래프(Resource Allocation Graph): 자원 할당 상태를 그래프로 표현하여 데드락의 가능성 분석

Context Switching

개요

• 문맥 교환은 컴퓨터에서 여러 프로그램이나 작업(스레드)이 동시에 실행되는 것처럼 보이게 하는 기술
• 실제로 컴퓨터의 CPU는 한 번에 하나의 작업만 처리 가능
• 그래서, 여러 작업을 빠르게 번갈아 가며 처리함으로써 모든 작업이 동시에 실행되는 것처럼 만듦

문맥 교환이 필요한 이유는?

• 컴퓨터를 사용하면서 우리는 동시에 많은 일을 함
• 예를 들어, 음악을 들으면서 인터넷을 검색하고, 문서를 작성할 수 있음
• 컴퓨터가 이렇게 여러 작업을 동시에 처리할 수 있는 것은 문맥 교환 덕분

문맥 교환은 어떻게 일어나나?

1. 중단: 현재 실행 중인 작업이 중단. 이때, 작업의 현재 상태(문맥)를 저장. 문맥에는 CPU의 레지스터 값, 프로그램 카운터, 스택 포인터 등이 포함
2. 저장: 중단된 작업의 문맥은 안전하게 메모리에 저장
3. 전환: CPU는 다음에 실행할 작업을 결정하고, 그 작업의 문맥을 불러옴
4. 재개: 새로운 작업이 CPU에서 실행을 시작. 이전에 중단된 작업은 나중에 CPU가 다시 그 작업으로 돌아올 때까지 대기

문맥 교환의 비용

• 문맥 교환은 유용하지만, 시간이 걸리는 작업
• 현재 작업의 상태를 저장하고, 새로운 작업의 상태를 불러오는 데에는 시간이 필요하기 때문
• 따라서, 너무 많은 문맥 교환이 발생하면 시스템의 전반적인 성능에 영향을 줄 수 있음

프로세스와 스레드에서의 문맥 교환(Context Switching)

공통점

• 문맥 교환이란 컴퓨터가 현재 하고 있는 일을 잠시 멈추고, 다른 일을 시작하는 것
• 이때 컴퓨터는 멈춘 일의 상태를 모두 기억해뒀다가, 다시 그 일을 할 때 이어서 할 수 있어야 함
• 이 과정은 프로세스(작업)에서도 일어나고, 스레드(작업의 작은 단위)에서도 일어남
  • 기억하기: 현재 하고 있는 일의 정보를 모두 저장
  • 바꾸기: 다른 일로 전환
  • 이어하기: 전에 하던 일을 다시 시작할 때, 기억해둔 정보를 바탕으로 그 상태에서 이어서 함

차이점

1. 프로세스 문맥 교환
   • 프로세스는 각각 독립된 메모리 공간을 가지고 있음
   • 프로세스는 각자의 집을 가지고 있는 사람들과 같음
   • 프로세스에서 문맥 교환을 할 때는, 한 사람의 집에서 다른 사람의 집으로 이동하는 것과 같아서, 더 많은 정보(예: 메모리 공간의 상태)를 저장하고 복원해야 함. 그래서 시간이 더 오래 걸림
2. 스레드 문맥 교환
   • 스레드는 같은 프로세스 내에서 작동하며, 메모리 공간을 공유
   • 스레드는 한 집에 사는 가족 구성원들처럼 서로 정보를 공유
   • 스레드에서 문맥 교환을 할 때는, 같은 집 안에서 다른 방으로 이동하는 것처럼, 더 적은 정보(예: 스레드의 실행 상태)만 저장하고 복원하면 됨. 그래서 프로세스 문맥 교환보다 더 빨리 처리할 수 있음

결론

• 공통점: 둘 다 일을 잠시 멈추고 다른 일을 시작하는 과정에서, 현재 하고 있는 일의 정보를 저장했다가 나중에 그 정보를 바탕으로 일을 이어갈 수 있게 해주는 기술
• 차이점: 프로세스 문맥 교환은 '다른 집으로 이사 가는 것'과 같이 더 많은 정보를 처리해야 하고, 스레드 문맥 교환은 '같은 집 안에서 방을 옮기는 것'과 같이 더 적은 정보만 처리하면 돼서 더 빠르게 처리할 수 있음

PintOS와 Context Switching

문맥 교환의 필요성

• 멀티태스킹: 현대의 운영 체제는 여러 프로세스와 스레드가 동시에 실행될 수 있도록 설계. 문맥 교환은 이러한 병렬성을 가능하게 함
• 자원 활용 최적화: 특정 작업이 I/O 작업을 기다리는 동안 CPU를 유휴 상태로 두지 않고, 다른 작업을 실행하여 자원 활용도를 높임

문맥 교환의 비용

• 오버헤드: 문맥 교환 과정에서 현재 실행 중인 스레드의 상태를 저장하고, 다음 스레드의 상태를 불러오는 작업은 시간이 소요. 이 오버헤드는 CPU의 유휴 시간을 증가시키고, 시스템의 성능을 저하시킬 수 있음
• 캐시 미스: 문맥 교환이 발생하면 새로운 스레드의 데이터와 명령어가 CPU 캐시에 없을 가능성이 높아짐. 이로 인해 캐시 미스가 발생하고, 데이터를 메모리에서 다시 가져와야 하는 비용이 발생

문맥 교환 최적화 방법

• 스레드 우선순위: 스레드에 우선순위를 부여하여, 중요한 작업을 먼저 실행하고 덜 중요한 작업의 문맥 교환을 줄임
• 시간 할당량(타임 슬라이스): 스레드가 CPU를 점유하는 시간을 제한하여, 과도한 문맥 교환을 방지하고 공정성을 보장
• 스레드 상태 관리: I/O 작업이나 다른 대기 상태에 있는 스레드를 효율적으로 관리하여, 불필요한 문맥 교환을 최소화

PintOS에서의 문맥 교환

• PintOS 프로젝트에서는 이러한 문맥 교환의 원리를 이해하고, 스레드 스케줄링과 동기화 메커니즘을 설계할 때 고려해야 함
• PintOS는 교육용 운영 체제이기 때문에, 실제로 문맥 교환과 관련된 코드를 직접 구현하고 실험해볼 수 있음
• 이 과정에서 문맥 교환의 비용을 직접 관찰하고, 다양한 스케줄링 알고리즘과 동기화 기법이 시스템 성능에 미치는 영향을 학습할 수 있음음

핵심 연관 개념

이러한 개념들을 이해하는 것은 컴퓨터에서 여러 프로세스와 스레드가 어떻게 동시에 실행될 수 있는지, 그리고 왜 때때로 실행 순서를 바꿔야 하는지를 이해하는 데 도움이 됨. 문맥 교환은 이 모든 과정의 중심에 있으며, 운영 체제의 효율적인 작업 관리를 가능하게 함

1. 프로세스(Process)와 스레드(Thread)

• 프로세스는 실행 중인 프로그램. 자신만의 메모리 공간(코드, 데이터, 스택 등)을 가지고 있음
• 스레드는 프로세스 내에서 실행되는 실행 단위. 스레드들은 프로세스의 자원을 공유하지만, 각자의 스택을 가지고 있어서 독립적인 실행 흐름을 가질 수 있음

2. 문맥(Context)

• 문맥은 특정 시점에서 프로세스 또는 스레드의 상태 정보를 의미
• CPU 레지스터의 값, 프로그램 카운터, 스택 포인터 등이 여기에 포함

3. 문맥 교환(Context Switching)

• 문맥 교환은 CPU가 현재 실행 중인 프로세스나 스레드에서 다른 프로세스나 스레드로 전환하는 과정
• 이때 현재 실행 중인 작업의 문맥을 저장하고, 새로운 작업의 문맥을 CPU에 로드

4. 스케줄러(Scheduler)

• 스케줄러는 어떤 프로세스나 스레드를 다음에 실행할지 결정하는 시스템의 일부
• 스케줄러는 작업의 우선순위, 실행 시간 등을 고려하여 효율적인 실행 순서를 결정

5. 인터럽트(Interrupt)

• 인터럽트는 프로세스의 실행을 잠시 중단시키고, 운영 체제가 긴급하게 처리해야 할 작업(예: 입력/출력 처리)을 알리는 신호
• 인터럽트 처리가 끝나면, 중단되었던 프로세스의 실행을 다시 계속할 수 있음

6. 동기화(Synchronization)

• 동기화는 여러 스레드가 공유 자원에 접근할 때 발생할 수 있는 문제를 해결하기 위해 필요한 기법
• 동기화를 통해 데이터의 일관성과 정확성을 유지할 수 있음

7. 우선순위 역전(Priority Inversion)

• 우선순위 역전은 낮은 우선순위의 작업이 높은 우선순위의 작업을 차단하는 현상
• 이 문제를 해결하기 위해 우선순위 상속(Priority Inheritance) 같은 기법이 사용될 수 있음

Multi-Level Feedback Queue Scheduler (MLFQS)

개요

• MLFQS는 운영 체제에서 사용하는 다양한 유형의 프로세스를 효율적으로 관리할 수 있는 강력하고 고급 스케줄링 알고리즘 중 하나
• 이 알고리즘은 다양한 우선순위를 가진 여러 큐를 사용하여 프로세스를 관리하고, 프로세스의 실행 특성에 따라 동적으로 우선순위를 조정하여 효율적으로 CPU 시간을 분배
• MLFQS는 시스템의 공정성과 효율성을 높이기 위해 설계되었으며, 시스템의 전반적인 성능에 영향을 미치는 중요한 요소

MLFQS의 핵심 개념

• 여러 레벨의 큐: MLFQS는 다양한 우선순위 레벨을 가진 여러 개의 큐를 사용. 각 큐는 특정 우선순위를 가진 프로세스들을 담고 있으며, 우선순위가 높은 큐의 프로세스가 먼저 CPU를 할당 받음
• 동적 우선순위 조정: 프로세스가 시스템에서 실행되면서, 그 특성(예: CPU 사용량, 대기 시간)에 따라 우선순위가 동적으로 조정. 이를 통해, CPU를 많이 사용하는 프로세스의 우선순위를 낮추고 I/O 작업 등으로 대기하는 프로세스 우선순위를 높여 공정성 유지
• 우선순위 상속: 프로세스가 다른 프로세스를 기다릴 때(예: 락을 기다림), 대기 중인 프로세스의 우선순위를 기다리고 있는 프로세스에게 "상속"하여, 우선순위가 높은 프로세스가 낮은 프로세스 때문에 오랫동안 대기하는 것을 방지

MLFQS의 작동 원리

1. 시작: 모든 프로세스는 가장 낮은 우선순위를 가진 큐에서 시작
2. CPU 실행: 프로세스가 CPU 시간을 사용하면, 사용량에 따라 우선순위가 조정되어 다른 큐로 이동할 수 있음. 일반적으로 CPU를 많이 사용할수록 우선순위가 낮아짐
3. 대기 상태: 프로세스가 I/O 요청 등으로 대기 상태가 되면, 그 대기 시간이 길어질수록 우선순위가 점점 높아져 다시 빠르게 CPU를 할당 받을 수 있음
4. 우선순위 조정: 시스템은 정기적으로 프로세스의 실행 패턴을 분석하여 우선순위를 조정. 이는 프로세스가 오랫동안 실행되면서 변할 수 있는 실행 특성을 반영하기 위함

MLFQS의 장점

• 공정성: 모든 프로세스가 공평하게 CPU 시간을 할당 받을 수 있도록 함
• 응답성: I/O 작업이 많은 프로세스나 사용자 상호작용이 필요한 프로세스에 빠른 응답 제공
• 자원 활용 최적화: 프로세스의 실행 특성에 따라 우선순위를 조정함으로써, CPU와 같은 시스템 자원 활용도 높임

4BSD 스케줄러

• 4BSD(Berkeley Software Distribution) 스케줄러는 UNIX 시스템에서 사용되는 스케줄링 알고리즘
• 스케줄러의 주요 목표는 시스템의 반응성과 효율성을 최적화하는 것
• 4BSD 스케줄러는 CPU 사용 패턴(예: CPU 집중적인 작업 vs I/O 집중적인 작업)에 따라 프로세스의 우선순위를 동적으로 조정
• 인터랙티브 프로세스 우선순위 향상: 사용자와의 상호작용이 필요한 프로세스(예: 텍스트 편집기, 그래픽 인터페이스)는 빠른 반응 시간이 중요. 4BSD 스케줄러는 이러한 프로세스가 자주 CPU를 양보하는 경향을 감지하고, 그들의 우선순위를 높여 반응성 개선
• 백그라운드 작업 우선순위 감소: CPU 사용량이 매우 높은 프로세스(예: 컴파일러, 대규모 계산 프로그램)는 시스템의 전반적인 반응성에 영향을 줄 수 있음. 이러한 프로세스의 우선순위는 시간이 지남에 따라 점차 감소하여, 인터랙티브 프로세스에게 CPU 사용 기회를 더 많이 제공

nice

• UNIX 및 UNIX 계열 운영 체제에서 프로세스의 우선순위를 조정하는 데 사용되는 값
• nice 값은 사용자가 프로세스의 기본 우선순위를 조정할 수 있게 해주며, 이 값은 프로세스의 우선순위에 직접적인 영향을 미침
• nice 값의 범위: 일반적으로 nice 값은 -20에서 19 사이. 낮은 값(예: -20)은 높은 우선순위를 의미하고, 높은 값(예: 19)은 낮은 우선순위를 의미. 기본 값은 0
• nice 값의 사용: 사용자는 nice 명령어를 사용하여 실행 중이거나 새로 시작하는 프로세스의 nice 값을 설정할 수 있음. nice 값을 높이면(양수 방향으로), 프로세스는 더 낮은 우선순위를 갖게 되어 CPU 접근이 더 적게 됨. 반대로, nice 값을 낮추면(음수 방향으로), 프로세스의 우선순위가 높아져 CPU를 더 많이 사용할 수 있게 됨
• nice 값은 시스템의 부하가 높을 때 특정 프로세스의 우선순위를 조정하거나, 백그라운드 작업을 실행할 때 유용하게 사용
• 예를 들어, 시스템의 자원을 많이 사용하는 대규모 계산 작업을 백그라운드에서 실행할 때, nice 값을 높여 다른 사용자 또는 인터랙티브 작업에 더 많은 CPU 시간을 할당할 수 있음

쉬운 설명

MLFQS

• MLFQS는 컴퓨터가 여러 프로그램을 효율적이고 공평하게 처리할 수 있도록 돕는 똑똑한 방법
• 모든 프로그램이 필요한 만큼의 컴퓨터 시간을 얻을 수 있도록, 운영체제는 이러한 규칙을 사용해 줄을 관리
• 놀이 공원에 갔다고 가정할 때, 놀이 공원에는 여러 종류의 놀이기구가 있고 각 놀이기구 앞에는 줄을 서서 기다리는 사람들이 있음
• 놀이 공원 관리자는 모든 사람들이 공평하게 놀이기구를 즐길 수 있도록, 특별한 줄서기 규칙을 만들었음

1. 여러 줄로 나누기: 사람들이 기다리는 줄을 여러 개로 나눔. 각 줄은 놀이기구를 타고 싶어하는 사람들의 "급함"에 따라 다름. 맨 앞 줄은 가장 급한 사람들, 맨 뒷줄은 급하지 않은 사람들이 서게 됨
2. 줄 이동하기: 누군가 놀이기구를 타고 나와서 다시 줄을 서려고 하면, 관리자는 그 사람이 얼마나 자주 놀이기구를 탔는지, 그리고 얼마나 오래 기다렸는지를 보고, 어느 줄에 서야 할지를 결정. 자주 탄 사람은 뒷줄로, 오래 기다린 사람은 앞줄로 갈 수 있음
3. 공정하게 기회 주기: 모든 사람이 놀이기구를 공평하게 즐길 수 있도록, 관리자는 줄의 순서를 주의 깊게 관찰하며, 필요하면 사람들을 다른 줄로 옮겨 줌

• 이렇게 놀이공원에서의 줄서기 규칙은 MLFQS와 비슷
• 컴퓨터에서 실행되는 프로그램들(또는 스레드들)도 여러 줄에 나눠져서 기다리고 있고, 운영체제는 그 프로그램들이 컴퓨터 자원(놀이기구)을 사용할 차례를 기다리게 함
• 프로그램들이 "급함"은 그 프로그램의 우선순위로 나타냄
• 프로그램이 CPU(컴퓨터의 놀이기구)를 사용하고 나면, 운영체제는 그 프로그램을 어느 줄에 다시 서게 할지 결정
• 이때, 프로그램이 얼마나 CPU 시간을 많이 사용했는지, 또는 얼마나 오래 기다렸는지 등을 고려
• 이렇게 해서, 모든 프로그램이 공평하게 CPU 시간을 얻을 수 있도록, 운영체제는 계속해서 프로그램들의 줄을 조정

4BSD 스케줄러

• 4BSD 스케줄러도 MLFQS와 비슷하나, 특히 시스템이 얼마나 "바쁜지"를 고려
• 만약 놀이공원에서 놀이기구가 매우 바쁘다면, 줄에서 기다리는 사람들을 더 빨리 처리하려고 할 것임
• 4BSD에서는 시스템이 바쁠수록 프로그램들이 CPU를 더 자주 사용할 수 있도록 조정해 줌
• 이것은 프로그램이 사용자에게 더 빠른 반응을 줄 수 있도록 해줌

nice

• nice는 프로그램이 "얼마나 친절한지"를 나타내는 숫자
• 줄에서 기다리는 동안 누군가가 다른 사람을 앞으로 보내주는 것처럼, nice 값이 높은 프로그램은 다른 프로그램에게 CPU 시간을 더 양보
• 반대로, nice 값이 낮은 프로그램은 더 적극적으로 CPU 시간을 사용하려고 함
• nice 값은 프로그램이 다른 프로그램보다 더 많이 또는 더 적게 CPU 시간을 사용하게 하고 싶을 때 조정 가능

마치며

여기까지가 KAIST의 교육용 운영체제인 PintOS 프로젝트를 구현하기 위해 알아야 하는 공부 키워드였다.

 

개인적으로는 위의 개념의 동작 원리와 누군가 나에게 저러한 키워드들을 물어봤을 때 틀림 없이 대답해야 하는 정도가 되어야 원활한 프로젝트 작업이 될 수 있었다고 생각한다.

 

혹시 이 글을 보고 KAIST PintOS가 궁금해지신 분이나, Threads의 Alarm Clock, Priority Scheduling, Advanced Scheduler인 MLFQS를 직접 구현해보고 싶은 분이라면 https://casys-kaist.github.io/pintos-kaist/project1/introduction.html 를 참고하면 좋을 듯 하다.