프로세스·스레드·CPU 스케줄링

먼저 선형·계층·그래프·해시 구조 선택에서 큐의 순서를, 프로그램·프로세스·스레드에서 실행 단위를 확인한다. 계산에서는 대기·응답·반환시간의 서로 다른 시작점과 끝점을 사용한다.

한 개의 CPU를 많은 프로그램이 동시에 쓰는 것처럼 보이는 이유

음악을 들으며 문서를 저장하고 웹 요청도 처리할 수 있다. 이 절의 첫 모형은 동시 멀티스레딩(SMT)을 제외하고 한 논리 CPU에 한 실행흐름을 배정한다. SMT를 사용하는 실제 물리 코어는 여러 논리 CPU의 명령을 함께 처리할 수 있으므로 물리 코어와 스케줄링 단위를 동일시하지 않는다. 여러 실행흐름이 빠르게 번갈아 실행되고, 일부가 입출력을 기다리는 동안 다른 흐름이 CPU를 쓰기 때문에 사용자는 여러 일이 함께 진행된다고 느낀다.

이 질서를 만드는 주체가 운영체제다. 운영체제는 단순히 프로그램을 실행하는 도구가 아니라, 제한된 CPU·메모리·장치를 나누고 서로 침범하지 못하게 보호하며 실패를 격리하는 시스템 소프트웨어다. 그중 스케줄링은 누구에게 CPU를 언제, 얼마나 오래 줄 것인지 결정한다. 평균 대기시간만 줄이면 되는 문제가 아니라 응답성·공정성·처리량·마감시간과 전환비용을 함께 다루는 정책 문제다.

운영체제의 정확한 뜻

운영체제(Operating System, OS)는 응용 프로그램과 하드웨어 사이에서 CPU·메모리·입출력·파일 자원을 관리하고, 보호된 실행환경과 공통 서비스를 제공하는 시스템 소프트웨어다.

운영체제의 역할은 네 가지로 묶을 수 있다.

1. 추상화: 장치별 세부 동작을 파일·프로세스 같은 일관된 대상으로 보이게 한다.
2. 자원관리: 제한된 CPU 시간, 메모리 공간과 장치 사용순서를 배분한다.
3. 보호·격리: 한 프로그램의 오류나 권한 없는 접근이 다른 프로그램과 운영체제 핵심을 훼손하지 못하게 경계를 둔다.
4. 공통 서비스: 프로그램 시작·종료, 파일 접근, 통신과 오류보고에 공통 경로를 제공한다.

여기서 커널(kernel)은 운영체제 중 가장 높은 권한으로 자원관리와 보호를 수행하는 핵심 부분이다. 사용자 모드(user mode)는 응용 프로그램이 제한된 권한으로 실행되는 CPU 상태이고, 커널 모드(kernel mode)는 커널이 보호된 자원과 장치 제어 명령을 사용할 수 있는 CPU 상태다. 모드는 사용자의 로그인 권한과 다른 하드웨어 보호 개념이다.

전체에서 어디인가: 응용과 하드웨어 사이의 보호 경계

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

위의 세 응용은 사용자 모드에서 실행한다. 화살표는 보호된 서비스 요청의 방향이며 결과는 같은 서비스 경로로 반환된다. 경계를 넘는 것은 검사를 맡은 커널 코드이지 응용에 커널 권한을 주는 일이 아니다. 아래 하드웨어는 네 자원 종류의 집합이며 실행순서를 뜻하지 않는다.

응용이 보호된 자원을 필요로 하면 정해진 진입경로를 통해 커널에 요청한다. CPU가 커널 모드로 바뀐다는 것은 응용 자체가 커널 권한을 얻는다는 뜻이 아니다. 커널이 요청값과 권한을 검사하고 서비스를 수행한 뒤 결과를 반환한다. 구체적인 시스템 호출·인터럽트·입출력 경로는 이 장의 네 번째 절에서 다룬다.

이미 배운 기반을 짧게 연결한다

앞에서 CPU는 명령을 실행하고, 프로세스는 독립 주소공간과 자원을 가진 실행 중 프로그램이며, 스레드는 그 프로세스 자원을 공유하는 실행흐름이라고 배웠다. 메모리 계층은 속도·용량이 다른 저장층을 결합하므로 실행흐름을 바꿀 때 저장·복원할 상태와 캐시 영향이 생긴다. 이제 운영체제가 실행가능 흐름에 CPU를 배분하는 원리와 그 선택의 비용을 연결한다.

운영체제 스케줄링의 정확한 뜻

운영체제 스케줄링(OS scheduling)은 실행할 수 있는 프로세스나 스레드에 CPU 시간을 배분하는 정책과 이를 실제로 전환하는 메커니즘이다.

실행가능(runnable)은 필요한 메모리와 조건을 갖추고 CPU만 받으면 진행할 수 있는 상태다. 스케줄러(scheduler)는 실행가능 집합에서 다음 실행흐름을 고르는 운영체제 구성요소이고, 디스패치(dispatch)는 선택한 흐름의 상태를 CPU에 복원하여 실제 실행을 시작시키는 동작이다. 선점(preemption)은 현재 흐름이 자발적으로 CPU를 내놓기 전에 운영체제가 실행을 중단하고 다른 흐름에 CPU를 주는 것이다. 타이머(timer)는 정한 시간이 지나면 커널이 실행권을 다시 판단할 수 있도록 사건을 발생시키는 시간측정 메커니즘이다.

정책은 어떤 흐름을 고를까를 답하고, 메커니즘은 타이머·상태저장·큐 조작으로 어떻게 바꿀까를 답한다. 좋은 정책도 전환이 너무 잦으면 실제 CPU 시간을 잃고, 빠른 메커니즘도 잘못된 정책을 공정하게 만들지는 못한다.

프로그램·프로세스·스레드를 구분한다

프로그램(program)은 저장장치에 놓인 명령과 데이터의 정적인 묶음이다. 프로그램을 실행하면 운영체제가 주소공간, 열린 자원과 실행상태를 마련하여 프로세스를 만든다. 같은 프로그램 파일을 두 번 실행하면 코드가 같아도 서로 다른 프로세스가 될 수 있다.

프로세스 안에는 하나 이상의 스레드가 있다. 같은 프로세스의 스레드는 코드·전역 데이터·열린 파일 같은 프로세스 자원을 공유하지만, 각자 다음에 실행할 명령 위치, 계산 중인 레지스터 값과 호출 스택을 가진다. 실행문맥(context)은 중단한 실행을 이어가기 위해 보존해야 하는 이런 CPU·실행 상태다.

커널은 관리 정보를 별도 자료구조에 둔다. 프로세스 제어 블록(Process Control Block, PCB)은 프로세스 식별자·상태·주소공간·자원 정보를, 스레드 제어 블록(Thread Control Block, TCB)은 스레드의 실행문맥·상태·스케줄링 정보를 나타내는 논리적 관리기록이다. 실제 필드와 분할 방식은 운영체제마다 다르므로 답안에서는 보편적 역할과 특정 구현을 구분한다.

상태 전이와 문맥교환: 멈춘 지점부터 다시 실행한다

운영체제의 상태 이름은 구현마다 세분될 수 있지만 기본 흐름은 다음과 같다.

• 생성(new): 실행에 필요한 관리정보를 만드는 중이다.
• 실행가능(ready/runnable): CPU만 받으면 실행할 수 있다.
• 실행(running): 현재 CPU에서 명령을 수행한다.
• 대기(waiting/blocked): 입출력 완료나 동기화 조건처럼 CPU만으로 해결할 수 없는 사건을 기다린다.
• 종료(terminated): 실행은 끝났고 운영체제가 결과와 자원을 정리한다.

사건 완료는 실행가능으로 돌아오는 조건이다 · 상태 따라가기

준비 프로세스는 CPU 배정을 받아 실행한다. 모든 단계에서 프로세스 상태·사건·스케줄러의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

각 상자는 운영체제의 개념적 상태다. 생성·종료는 명시적인 상태이므로 별도의 시작·종료 의사상태를 추가하지 않았다. 사건 완료 뒤에도 디스패치가 있어야 실행된다. 선점에는 시간할당량 만료가 포함된다. 상태명·세분화는 실제 구현마다 다를 수 있다.

이 예의 조건

• 각 상자는 운영체제의 개념적 상태다. 생성·종료는 명시적인 상태이므로 별도의 시작·종료 의사상태를 추가하지 않았다. 사건 완료 뒤에도 디스패치가 있어야 실행된다. 선점에는 시간할당량 만료가 포함된다. 상태명·세분화는 실제 구현마다 다를 수 있다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상생성	원 설명원그림의 대상
대상실행가능	원 설명원그림의 대상
대상실행	원 설명원그림의 대상
대상대기	원 설명원그림의 대상
대상종료	원 설명원그림의 대상

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결생성 → 실행가능	원 라벨·방향승인 / 정방향 / 실선
연결실행가능 → 실행	원 라벨·방향디스패치 / 정방향 / 실선
연결실행 → 실행가능	원 라벨·방향선점·만료 / 정방향 / 실선
연결실행 → 대기	원 라벨·방향입출력·조건 / 정방향 / 실선
연결실행 → 종료	원 라벨·방향완료 / 정방향 / 실선
연결대기 → 실행가능	원 라벨·방향사건 완료 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
준비·배정 준비 프로세스는 CPU 배정을 받아 실행한다.	값·보충 정보 프로세스 상태: 준비→실행 사건·스케줄러: CPU 배정	변화·이유 실행 가능과 현재 실행을 구별한다.
대기 필요 실행 도중 기다릴 사건이 생기면 대기 상태로 간다.	값·보충 정보 프로세스 상태: 실행→대기 사건·스케줄러: I/O·잠금 대기	변화·이유 CPU를 점유해 실행하는 상태가 아니다.
사건 완료 사건이 끝나면 프로세스는 준비로 돌아간다.	값·보충 정보 프로세스 상태: 대기→준비 사건·스케줄러: 사건 완료·CPU 미배정	변화·이유 사건 완료만으로 실행이라고 표시하지 않는다.
다시 CPU 배정 스케줄러가 준비 상태에 CPU를 배정한 뒤 실행을 재개한다.	값·보충 정보 프로세스 상태: 준비→실행 사건·스케줄러: CPU 재배정	변화·이유 준비와 다음 실행 사이의 별도의 배정 전환을 생략하지 않는다.
실행에서 두 대안 재배정된 실행을 공통 시작점으로 완료이면 종료, 선점이면 준비로 갈라진다.	값·보충 정보 프로세스 상태: 실행→종료 / 준비 사건·스케줄러: 완료 / 선점	변화·이유 준비 다음 자동 종료가 아니며 두 대안의 서로 다른 사건을 표시한다.

사건 완료는 실행가능으로 돌아오는 조건이다 · 상태 따라가기

준비 프로세스는 CPU 배정을 받아 실행한다. 모든 단계에서 프로세스 상태·사건·스케줄러의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

각 상자는 운영체제의 개념적 상태다. 생성·종료는 명시적인 상태이므로 별도의 시작·종료 의사상태를 추가하지 않았다. 사건 완료 뒤에도 디스패치가 있어야 실행된다. 선점에는 시간할당량 만료가 포함된다. 상태명·세분화는 실제 구현마다 다를 수 있다.

이 예의 조건

• 각 상자는 운영체제의 개념적 상태다. 생성·종료는 명시적인 상태이므로 별도의 시작·종료 의사상태를 추가하지 않았다. 사건 완료 뒤에도 디스패치가 있어야 실행된다. 선점에는 시간할당량 만료가 포함된다. 상태명·세분화는 실제 구현마다 다를 수 있다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

관계도의 보충 설명

원그림의 모든 대상과 설명

대상	원 설명
대상생성	원 설명원그림의 대상
대상실행가능	원 설명원그림의 대상
대상실행	원 설명원그림의 대상
대상대기	원 설명원그림의 대상
대상종료	원 설명원그림의 대상

원그림의 모든 관계와 조건

연결	원 라벨·방향
연결생성 → 실행가능	원 라벨·방향승인 / 정방향 / 실선
연결실행가능 → 실행	원 라벨·방향디스패치 / 정방향 / 실선
연결실행 → 실행가능	원 라벨·방향선점·만료 / 정방향 / 실선
연결실행 → 대기	원 라벨·방향입출력·조건 / 정방향 / 실선
연결실행 → 종료	원 라벨·방향완료 / 정방향 / 실선
연결대기 → 실행가능	원 라벨·방향사건 완료 / 정방향 / 실선

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
준비·배정 준비 프로세스는 CPU 배정을 받아 실행한다.	값·보충 정보 프로세스 상태: 준비→실행 사건·스케줄러: CPU 배정	변화·이유 실행 가능과 현재 실행을 구별한다.
대기 필요 실행 도중 기다릴 사건이 생기면 대기 상태로 간다.	값·보충 정보 프로세스 상태: 실행→대기 사건·스케줄러: I/O·잠금 대기	변화·이유 CPU를 점유해 실행하는 상태가 아니다.
사건 완료 사건이 끝나면 프로세스는 준비로 돌아간다.	값·보충 정보 프로세스 상태: 대기→준비 사건·스케줄러: 사건 완료·CPU 미배정	변화·이유 사건 완료만으로 실행이라고 표시하지 않는다.
다시 CPU 배정 스케줄러가 준비 상태에 CPU를 배정한 뒤 실행을 재개한다.	값·보충 정보 프로세스 상태: 준비→실행 사건·스케줄러: CPU 재배정	변화·이유 준비와 다음 실행 사이의 별도의 배정 전환을 생략하지 않는다.
실행에서 두 대안 재배정된 실행을 공통 시작점으로 완료이면 종료, 선점이면 준비로 갈라진다.	값·보충 정보 프로세스 상태: 실행→종료 / 준비 사건·스케줄러: 완료 / 선점	변화·이유 준비 다음 자동 종료가 아니며 두 대안의 서로 다른 사건을 표시한다.

선점은 실행 중인 흐름을 실행가능 상태로 돌려보낸다. 입출력·조건 대기는 실행에서 대기로, 해당 사건 완료는 대기에서 실행가능으로 이동시킨다. 사건이 끝났다는 이유만으로 바로 CPU를 받는 것은 아니며 다시 디스패치되어야 한다.

문맥교환(context switch)은 실행을 이어가는 데 필요한 문맥을 보존하고 다른 실행흐름의 문맥으로 CPU 실행대상을 바꾸는 개념이다. 전환 원인 → 실행상태 관리와 다음 흐름 선택 → 필요한 문맥·실행환경 전환 → 실행 재개는 책임을 읽기 위한 개념모형이며 모든 운영체제의 커널 호출순서가 아니다. POSIX의 정책·우선순위 인터페이스만으로 저장할 레지스터 목록이나 실제 전환비용을 확정하지 않는다.

이때 모드 전환(mode switch)은 같은 실행흐름이 사용자 모드와 커널 모드 사이를 오가는 것, 문맥교환은 다른 실행흐름으로 CPU 실행대상을 바꾸는 것이다. 예를 들어 스레드 A의 시스템 호출을 커널이 즉시 처리하고 A로 돌아오면, A의 사용자 코드 → A를 위한 커널 코드 → A의 사용자 코드라는 모드 전환만으로 끝날 수 있다. 호출 중 대기·선점이 없다고 가정한 사례이며, 시스템 호출마다 다른 스레드가 실행된다고 해석하지 않는다.

반대로 A가 디스크 입출력 완료를 기다려 대기 상태가 되면 커널은 실행가능 스레드 B를 선택할 수 있다. 이때 A에서 B로 문맥교환하고, 입출력이 끝난 A는 실행가능 큐로 돌아온 뒤 다시 선택될 때 이어서 실행한다. 첫 상태도에서 실행 → 대기 → 실행가능을 따라간 다음, 실행가능 → 실행의 디스패치를 확인하면 “커널에 들어갔다”와 “다른 흐름을 실행했다”를 구분할 수 있다.

고정 판본의 구현 사례: Linux v6.6 commit ffc253263a1375a65fa6c9f62a893e9767fbebfa의 kernel/sched/core.c에 있는 context_switch()는 주소공간 관련 처리를 나눈 뒤 switch_to()를 호출한다. 같은 판본의 x86-64 arch/x86/entry/entry_64.S에 있는 __switch_to_asm()은 호출규약상 보존 대상인 일부 레지스터를 저장하고, 이전 태스크의 스택 포인터를 기록한 뒤 다음 태스크의 스택 포인터와 해당 레지스터들을 복원하여 __switch_to로 이어진다. 모든 레지스터를 한 번에 저장한다거나 모든 전환이 주소공간 전체를 바꾼다는 뜻은 아니다. 두 코드 지점의 역할을 개념모형과 대조하되 다른 버전·아키텍처의 필수 구현순서로 일반화하지 않는다. 2026-09-30에 고정 원문을 읽었으며 최신 Linux 판본이라는 주장이나 실제 성능 측정은 아니다.

구현 근거: Linux v6.6 context_switch, x86-64 __switch_to_asm. 원문 코드·주석을 옮기지 않고 지정한 판본의 동작을 한국어로 재서술했다.

해당 CPU가 저장·복원과 스케줄러 작업에 쓴 시간은 그 CPU의 사용자 업무 실행시간과 구분한다. 추가 지연을 분석할 때에는 캐시·주소변환 상태와 실제 메모리 접근을 별도 관찰항목으로 둔다. 위 두 코드만 읽었다고 캐시가 반드시 비워진다거나 특정 지연이 발생했다고 확인한 것은 아니다. 다만 모든 교환이 주소공간 전체를 바꾸는 것은 아니다. 같은 프로세스의 스레드 전환과 다른 프로세스 전환, 실제 하드웨어·커널 최적화에 따라 비용이 달라진다.

비용을 줄이려면 전환 횟수를 무조건 최소화하지 않는다. 시간할당량을 지나치게 늘리면 상호작용 요청의 응답이 늦어진다. 전환 원인·빈도·직접/간접 시간을 계측하고, 작업 특성에 맞는 시간할당량, CPU 친화도와 일괄처리를 조정하되 응답성과 공정성 목표를 함께 검증한다.

먼저 무엇을 좋게 만들지 수치로 정한다

CPU 버스트(CPU burst)는 실행흐름이 다음 입출력·조건 대기나 종료까지 필요로 하는 한 덩어리의 CPU 계산이다. 시간할당량은 이번 차례에 연속으로 허용하는 CPU 시간이므로 버스트 길이와 다르다. 예를 들어 입출력 없이 6ms 계산해야 하는 작업을 RR의 q=2ms로 나누어 실행해도, 2ms마다 버스트가 완료되는 것은 아니다. 같은 버스트의 남은 계산을 다음 차례에 계속하며, CPU를 받지 못한 대기시간은 그 6ms에 포함하지 않는다. 다음 기호는 하나의 작업이 도착해 끝날 때까지를 측정한다.

• 도착시각 A: 실행가능 집합에 들어온 시각
• 최초 실행시각 S: 처음 CPU를 받은 시각
• 완료시각 C: 실행을 마친 시각
• 총 CPU 실행시간 B: 모든 CPU 버스트의 합
• 반환시간(turnaround time) C-A: 도착부터 완료까지 걸린 전체 시간
• 대기시간(waiting time): 실행가능하지만 CPU를 받지 못한 시간의 합. 입출력·조건 대기가 없는 단일 CPU 버스트 문제에서는 C-A-B로 계산할 수 있지만, 일반 프로세스에서는 대기상태 시간을 별도로 빼야 한다.
• 응답시간(response time) S-A: 도착부터 첫 실행까지의 시간

처리량(throughput)은 단위시간에 완료한 작업 수, CPU 이용률(utilization)은 관측시간 중 CPU가 유휴상태가 아니었던 비율이다. 이용률에는 문맥교환 같은 관리작업도 포함될 수 있으므로 높다고 유용한 처리량까지 높다는 뜻은 아니다. 공정성(fairness)은 특정 흐름이 합리적인 기회 없이 계속 밀리지 않는 성질이고, 마감시간(deadline)은 결과를 내야 하는 시점이다. 평균만 쓰면 일부 작업의 극단적 지연을 숨길 수 있으므로 최악값이나 상위 지연분포도 함께 본다.

한 지표를 개선하면 다른 지표가 악화될 수 있다. 짧은 작업 우선은 평균 대기를 줄일 수 있지만 긴 작업을 굶길 수 있고, 매우 짧은 시간할당량은 첫 응답을 앞당길 수 있지만 문맥교환 비용을 늘린다. 따라서 알고리즘 이름보다 업무 목표와 부하 전제를 먼저 쓴다.

FCFS·SJF·SRTF: 도착순서와 짧은 작업의 교환

선입선처리(First-Come, First-Served, FCFS)는 먼저 실행가능해진 작업부터 비선점으로 실행한다. 구현과 설명이 단순하고 도착순서를 보존하지만, 긴 CPU 버스트 하나 뒤에 짧은 작업들이 기다리는 호위효과(convoy effect)가 생길 수 있다.

최단작업우선(Shortest Job First, SJF)은 준비된 작업 중 다음 CPU 버스트가 가장 짧다고 예측된 작업을 비선점으로 고른다. 모든 버스트 길이를 정확히 알고 동시에 도착한 이상화된 조건에서는 평균 대기시간을 최소화하지만, 실제 다음 버스트는 알 수 없어 과거 측정으로 예측해야 한다. 긴 작업은 짧은 작업이 계속 들어오면 기아에 빠질 수 있다.

최단잔여시간우선(Shortest Remaining Time First, SRTF)은 SJF의 선점형이다. 새 작업이 도착했을 때 현재 작업의 남은 예측시간보다 짧으면 선점한다. 짧은 작업의 응답·완료는 빨라질 수 있지만 예측오차, 잦은 선점과 긴 작업 기아가 커질 수 있다. SRT라고 줄여 부르기도 하지만 이 절에서는 알고리즘 이름을 분명히 하기 위해 SRTF를 쓴다.

RR·우선순위·MLFQ: 응답성과 정책을 실행순서로 만든다

라운드로빈(Round Robin, RR)은 실행가능 큐를 순환하며 각 흐름에 최대 시간할당량(time quantum)만큼 CPU를 주는 선점형 방식이다. 시간이 끝나기 전에 대기하거나 종료하면 다음 흐름으로 넘어간다. 할당량이 너무 크면 FCFS에 가까워져 응답이 늦고, 너무 작으면 문맥교환 비율이 커진다.

우선순위 스케줄링(priority scheduling)은 가장 높은 우선순위의 실행가능 흐름을 고른다. 선점형과 비선점형 모두 가능하다. 우선순위가 낮은 흐름이 계속 밀리는 기아(starvation)는 대기시간이 길수록 우선순위를 점차 높이는 에이징(aging)으로 완화할 수 있다. 우선순위 숫자가 클수록 높은지 낮은지는 시스템마다 다르므로 답안에서 방향을 정한다. 외부 요청이 우선순위를 정할 수 있다면 누가 어느 범위까지 올릴 수 있는지와 임시 우선순위의 만료규칙도 권한계약에 넣는다.

다단계 피드백 큐(Multilevel Feedback Queue, MLFQ)는 서로 다른 우선순위와 시간할당량을 가진 여러 큐 사이에서 관찰된 실행행동에 따라 흐름을 이동시키는 방식이다. 짧게 CPU를 쓰고 자주 대기하는 상호작용 흐름은 높은 큐에서 빠르게 응답하게 하고, 할당량을 반복 소진하는 계산 흐름은 낮은 큐로 내려 보낼 수 있다. 주기적으로 모든 흐름을 위로 올리거나 에이징을 적용해 기아를 막는다.

MLFQ는 미래 버스트를 모르는 환경에서 짧거나 상호작용적인 흐름을 우대하려는 근사정책이지, 작업의 중요도나 정확한 길이를 자동으로 알아내는 알고리즘은 아니다. 정책게임(policy gaming)은 작업이 유리한 등급을 얻으려고 정책의 관찰기준에 맞춰 행동을 꾸미는 현상이다. 큐 수·할당량·승강 조건이 부하와 맞지 않으면 정책게임, 빈번한 이동과 예측오류가 생긴다.

정책게임을 CPU 사용시간으로 확인해 보자. 높은 큐의 한 차례 시간할당량을 q=2ms로 정하고, “매번 2ms를 끝까지 썼을 때만 강등”하는 규칙을 두었다고 하자. 계산 위주 작업이 매번 1.9ms만 실행한 뒤 짧게 입출력을 요청하면, 많은 CPU를 사용해도 어느 차례에서도 2ms를 소진하지 않아 높은 큐에 남을 수 있다. 짧은 대기를 반복한다는 관찰만으로 실제로 CPU를 적게 쓰는 작업이라고 판단한 것이 문제다.

보완하는 한 방법은 한 차례의 q와 해당 큐에서 사용할 누적 CPU 예산을 구별하는 것이다. 자체 교육 정책으로 높은 큐의 예산을 4ms로 정하고, 대기 후 돌아와도 이미 사용한 CPU 시간을 유지한다고 하자. 첫 두 차례에 1.9+1.9=3.8ms를 사용한 작업은 남은 예산이 0.2ms다. 다음 차례에서 0.2ms를 더 쓰면 누적 4ms가 되어 낮은 큐로 이동한다. 입출력 대기시간은 CPU 사용예산에서 차감하지 않으며, 승격 시 예산을 언제 새로 부여할지도 정책에 명시한다. 이는 MLFQ의 가능한 회계 규칙이며 모든 운영체제의 고정 설정은 아니다.

이 예산은 한 작업의 등급을 정하는 기준이고, 앞서 말한 주기적 승격·에이징은 낮은 큐 작업의 실행기회를 회복하는 별도 기준이다. 두 장치를 함께 써도 유입량과 승격 후 순서를 제한하지 않으면 최대대기시간 상한을 자동으로 얻지는 못한다.

작은 예제로 지표가 어떻게 달라지는지 계산한다

세 작업 A, B, C가 모두 시각 0에 도착하고 CPU 실행시간이 각각 6, 2, 1ms라고 하자. 입출력 대기 없이 각 작업이 주어진 CPU 실행시간만 필요하고, 논리 CPU 하나를 공유하는 자체 교육 예제다. 아래 시각과 시간할당량, 대기·응답시간의 단위는 모두 ms다. 문맥교환 시간은 0으로 단순화하고 동률은 이름순으로 처리한다.

같은 9ms를 서로 다르게 배분한다 · 상태 따라가기

A 6ms·B 2ms·C 1ms가 모두 0에 도착하며 CPU 하나·전환비용 0이다. 모든 단계에서 FCFS·SJF/SRTF·RR·q2의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

넓은 화면과 모바일에서 같은 관계를 각각의 배치로 읽을 수 있습니다.

모든 작업은 시각 0에 도착하며 논리 CPU 하나, 입출력 없음, 전환비용 0이다. 막대 길이는 실행시간에 비례한다. RR의 A는 세 구간의 합이 6ms이고 마지막 7–9ms에도 계속 A를 실행한다. 첫 시작과 최종 완료는 서로 다른 시각이다.

이 예의 조건

• 모든 작업은 시각 0에 도착하며 논리 CPU 하나, 입출력 없음, 전환비용 0이다. 막대 길이는 실행시간에 비례한다. RR의 A는 세 구간의 합이 6ms이고 마지막 7–9ms에도 계속 A를 실행한다. 첫 시작과 최종 완료는 서로 다른 시각이다.
• 0부터 9ms까지 1ms를 32px로 표시한다. FCFS는 A 0–6, B 6–8, C 8–9ms, SJF와 SRTF는 C 0–1, B 1–3, A 3–9ms, RR q=2는 A 0–2, B 2–4, C 4–5, A 5–7과 7–9ms다. 작업은 모두 0에 도착하고 논리 CPU 하나, 입출력 없음, 전환비용 0이다. 각 막대의 시작과 끝에서 첫 응답과 최종 완료를 구분한다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
같은 작업 입력 A 6ms·B 2ms·C 1ms가 모두 0에 도착하며 CPU 하나·전환비용 0이다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A B C RR·q2: RR:A B C	변화·이유 작업 조건을 같게 고정해야 정책을 비교할 수 있다.
0~2ms FCFS는 A, 짧은 작업 우선은 C 뒤 B, RR은 A의 첫 2ms를 실행한다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A / SJF:C→B RR·q2: A 2ms·남은 4	변화·이유 각 정책이 선택한 작업과 남은 길이가 다르다.
2~5ms RR은 B를 2~4에 끝내고 C를 4~5에 끝낸다. SJF는 B 뒤 A를 실행한다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A / SJF:A RR·q2: B 완료 4·C 완료 5	변화·이유 첫 시작 시각과 마지막 완료를 같게 세지 않는다.
5~9ms RR은 A를 5~7·7~9에 실행해 전체 6ms를 완성한다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A→B→C RR·q2: A 완료 9·전체 6ms	변화·이유 뒤 대기자가 없어도 A의 남은 실행시간을 빠뜨리지 않는다.

같은 9ms를 서로 다르게 배분한다 · 상태 따라가기

A 6ms·B 2ms·C 1ms가 모두 0에 도착하며 CPU 하나·전환비용 0이다. 모든 단계에서 FCFS·SJF/SRTF·RR·q2의 위치를 유지하며 값과 허용 조건을 함께 확인합니다.

넓은 화면과 모바일에서 같은 관계를 각각의 배치로 읽을 수 있습니다.

모든 작업은 시각 0에 도착하며 논리 CPU 하나, 입출력 없음, 전환비용 0이다. 막대 길이는 실행시간에 비례한다. RR의 A는 세 구간의 합이 6ms이고 마지막 7–9ms에도 계속 A를 실행한다. 첫 시작과 최종 완료는 서로 다른 시각이다.

이 예의 조건

• 모든 작업은 시각 0에 도착하며 논리 CPU 하나, 입출력 없음, 전환비용 0이다. 막대 길이는 실행시간에 비례한다. RR의 A는 세 구간의 합이 6ms이고 마지막 7–9ms에도 계속 A를 실행한다. 첫 시작과 최종 완료는 서로 다른 시각이다.
• 0부터 9ms까지 1ms를 32px로 표시한다. FCFS는 A 0–6, B 6–8, C 8–9ms, SJF와 SRTF는 C 0–1, B 1–3, A 3–9ms, RR q=2는 A 0–2, B 2–4, C 4–5, A 5–7과 7–9ms다. 작업은 모두 0에 도착하고 논리 CPU 하나, 입출력 없음, 전환비용 0이다. 각 막대의 시작과 끝에서 첫 응답과 최종 완료를 구분한다.
• 이 원문의 교육용 사례·조건 안에서 상태를 대조합니다. 실제 구축·실험 결과나 원문에 없는 성능 보장을 추가하지 않습니다.

예의 값과 변화

관찰·상황	값·보충 정보	변화·이유
같은 작업 입력 A 6ms·B 2ms·C 1ms가 모두 0에 도착하며 CPU 하나·전환비용 0이다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A B C RR·q2: RR:A B C	변화·이유 작업 조건을 같게 고정해야 정책을 비교할 수 있다.
0~2ms FCFS는 A, 짧은 작업 우선은 C 뒤 B, RR은 A의 첫 2ms를 실행한다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A / SJF:C→B RR·q2: A 2ms·남은 4	변화·이유 각 정책이 선택한 작업과 남은 길이가 다르다.
2~5ms RR은 B를 2~4에 끝내고 C를 4~5에 끝낸다. SJF는 B 뒤 A를 실행한다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A / SJF:A RR·q2: B 완료 4·C 완료 5	변화·이유 첫 시작 시각과 마지막 완료를 같게 세지 않는다.
5~9ms RR은 A를 5~7·7~9에 실행해 전체 6ms를 완성한다.	값·보충 정보 FCFS·SJF/SRTF: FCFS:A→B→C RR·q2: A 완료 9·전체 6ms	변화·이유 뒤 대기자가 없어도 A의 남은 실행시간을 빠뜨리지 않는다.

표의 숫자를 RR 행에서 직접 만들어 보자. 완료시각은 A=9, B=4, C=5이므로 대기는 각각 9−0−6=3, 4−0−2=2, 5−0−1=4이고 평균은 (3+2+4)/3=3ms다. 최초 실행시각은 0,2,4이므로 평균 첫 응답은 (0+2+4)/3=2ms다. A는 시각 0에 즉시 한 번 실행해도 이후 B·C 때문에 기다리므로 첫 응답 0과 총대기 3이 같지 않다. 화살표가 아니라 시간축에서 최초 시작과 최종 완료를 각각 읽어 계산한다.

이제 RR 할당량만 1ms로 줄이면 B의 완료시각과 첫 응답은 얼마인가? 큐는 A→B→C 순서로 시작하여 [0,1) A, [1,2) B, [2,3) C, [3,4) A, [4,5) B, 이후 A만 남아 [5,9)를 실행한다. B는 시각 5에 완료하고 시각 1에 처음 실행하므로 반환 5ms·대기 5−2=3ms·첫 응답 1ms다. 할당량을 줄였다고 B의 완료도 반드시 빨라지지는 않는다. 첫 응답과 완료를 혼동했다면 위 표를 만드는 두 계산으로 돌아간다. 실제 전환비용이 양수인 조건에서는 이 시간축에 그 비용도 더해야 한다.

모두 동시에 도착했으므로 SJF와 SRTF 결과가 같다. 도착시각이 다르면 선점 여부가 결과를 바꾼다. 이번에는 작업 A의 도착이 0ms·CPU 실행시간이 8ms이고, 작업 B의 도착이 1ms·CPU 실행시간이 2ms라고 하자. 두 실행시간을 정확히 알고, 논리 CPU 하나·입출력 없음·문맥교환 비용 0이라는 전제를 유지한다.

• SJF: 시각 0에는 A만 있으므로 [0,8) A → [8,10) B다. 짧은 B가 시각 1에 도착해도 비선점이므로 실행 중인 A를 바꾸지 않는다.
• SRTF: 시각 1의 A 잔여시간은 8−1=7ms다. B의 2ms가 더 짧으므로 [0,1) A → [1,3) B → [3,10) A로 실행한다. A는 첫 1ms와 재개 후 7ms를 합해 필요한 8ms를 받는다.

단위는 모두 ms다. SRTF에서는 A의 완료가 8에서 10으로 늦어지고 B의 완료가 10에서 3으로 빨라진다. 평균 대기는 SJF의 (0+7)/2=3.5ms에서 SRTF의 (2+0)/2=1ms로 줄지만, 모든 작업의 완료가 빨라지는 것은 아니다. B의 반환시간도 완료시각 3이 아니라 도착 1을 뺀 3−1=2ms다.

이 표가 SJF를 항상 선택하라는 뜻은 아니다. 실제 버스트를 미리 알 수 없고 긴 작업 기아가 있으며, RR의 문맥교환 비용도 0이 아니다. 계산문제에서는 도착·선점·동률·교환비용 전제를 먼저 적어야 한다.

같은 세 작업으로 직접 계산한다

앞의 자체 교육 사례와 같이 A·B·C가 모두 시각 0에 도착하고 실행시간은 6·2·1ms다. 논리 CPU 하나, 입출력 없음, 문맥교환 비용 0, 초기 큐 A→B→C를 그대로 두고 RR 할당량만 3ms로 바꾼다. 시간축을 그리고 각 작업의 완료·대기·첫 응답을 계산하라. 이어서 “할당량을 줄이면 모든 작업의 완료가 빨라진다”는 주장과 앞의 q=2 결과를 비교하라. 이 문제는 기출 원문이 아닌 자체 조건 변경 연습이다.

계산 결과와 잘못된 추론 교정 보기

시간축은 [0,3) A → [3,5) B → [5,6) C → [6,9) A다. B·C는 할당량보다 먼저 끝나므로 각각 2·1ms만 사용한다.

작업	최초 실행 S	완료 C	대기 C−A−B	첫 응답 S−A
A	0	9	3	0
B	3	5	3	3
C	5	6	5	5

평균 대기는 11/3≈3.67ms, 평균 첫 응답은 8/3≈2.67ms다. q=2에서는 B가 4, C가 5에 끝나지만 A의 완료는 9로 같다. 앞의 q=1에서는 B의 첫 응답은 1로 빠르지만 완료는 5로 늦었다. 첫 실행 기회와 최종 완료를 같은 사건으로 읽은 것이 잘못된 추론이다. 원래 시간축과 지표 풀이에서 각 구간의 실행량을 먼저 합하고 두 시각을 따로 표시하면 교정할 수 있다. 전환비용이 양수인 실제 조건에는 이 계산값을 그대로 적용하지 않는다.

멀티코어에서는 배분과 이동비용을 함께 본다

멀티코어(multicore)는 한 프로세서 안에 명령을 실행할 수 있는 CPU 코어가 둘 이상인 구조다. 실행가능 흐름이 여러 개면 서로 다른 코어에서 실제로 동시에 실행할 수 있다. 그러나 모든 일을 코어 수만큼 빠르게 만들지는 못한다. 직렬 구간, 공유자료 경합과 메모리 대역폭이 병목이 될 수 있다.

스케줄러는 다음 선택을 추가로 한다.

• 부하균형(load balancing): 놀고 있는 코어가 없도록 실행가능 흐름을 분산한다.
• CPU 친화도(CPU affinity): 가능하면 같은 흐름을 같은 코어에 두어 캐시에 남아 있는 데이터와 코어별 상태를 재사용한다.
• 코어별 실행큐: 하나의 전역 큐 경합을 줄이지만 코어 사이 부하 불균형이 생길 수 있다.
• 작업 훔치기(work stealing): 한 코어의 큐가 비면 다른 코어의 대기 작업 일부를 가져온다.

친화도를 강하게 고정하면 캐시는 유리해도 한 코어만 과부하가 될 수 있고, 매번 이동시키면 균형은 좋아도 캐시 재사용을 잃는다. 멀티코어 답안은 코어 수만 쓰지 말고 실행큐 구조, 부하균형, 친화도와 공유자원 경합을 함께 적는다.

실시간은 평균속도보다 마감 보장이 먼저다

실시간 시스템(real-time system)은 계산결과뿐 아니라 정해진 시간 안에 결과를 내는 것이 정확성의 일부인 시스템이다. 경성 실시간(hard real-time)은 마감 위반을 허용할 수 없는 경우, 연성 실시간(soft real-time)은 위반이 품질 저하를 만들지만 제한적으로 감수할 수 있는 경우다.

실시간 분석에는 작업의 최악 실행시간(Worst-Case Execution Time, WCET), 도착주기, 마감시간과 선점·차단시간의 상한이 필요하다. Rate-Monotonic Scheduling(RMS)은 독립적인 주기 작업에서 주기가 짧을수록 높은 고정 우선순위를 주는 정책이고, 최조기 마감 우선(Earliest Deadline First, EDF)은 준비된 작업 중 절대 마감이 가장 가까운 작업에 동적으로 높은 우선순위를 주는 정책이다.

알고리즘 이름만으로 마감을 보장할 수 없다. 적용하는 작업모형의 전제 아래 이용률 또는 응답시간 분석으로 스케줄 가능성을 확인하고, 인터럽트·문맥교환·공유자원 차단과 WCET 측정오차를 포함해야 한다. 평균 CPU 이용률이 낮아도 짧은 구간에 작업이 몰리면 마감을 놓칠 수 있다.

CPU 스케줄링 기법을 같은 축으로 비교한다

SJF가 평균대기 최적, EDF가 좋다 같은 문장은 전제와 비용을 생략하면 불완전하다. 선점 여부, 버스트 정보, 도착모형, 전환비용과 마감 보장 분석을 함께 적는다.

선택은 일곱 질문으로 좁힌다

1. 스케줄링 단위는 프로세스인가, 스레드인가, 독립 작업인가.
2. 부하는 계산 중심인가, 짧게 실행하고 자주 기다리는 상호작용 중심인가.
3. 첫 응답·평균대기·처리량·공정성·마감 중 어떤 목표가 우선인가.
4. 다음 버스트, 우선순위, 주기·WCET·마감을 얼마나 믿을 수 있는가.
5. 선점과 문맥교환의 직접·캐시 비용을 어느 정도 감당할 수 있는가.
6. 기아·우선순위 오용·과부하 때 어떤 보호규칙을 둘 것인가.
7. 단일 코어의 정책을 멀티코어 큐·친화도·부하균형과 어떻게 결합할 것인가.

선택 뒤에는 실제 부하에서 응답시간 분포, 대기시간, 전환 횟수·시간, 처리량과 마감 위반을 함께 측정한다. 요청이 처리능력을 지속해서 넘을 때는 입장제어(admission control)로 새 작업의 수락·지연·거절 규칙을 적용하여 실행가능 큐가 무한히 늘지 않게 한다. 전제가 변하면 시간할당량이나 우선순위 숫자만 조정할 것이 아니라 정책 자체를 재평가한다.

어디서 실패하는가

운영체제의 핵심 학습 논점

운영체제를 설명할 때는 정의나 스케줄링 이름뿐 아니라 자원·상태·전환·선택 기준을 연결해야 한다. 다음 여섯 가지를 점검하자.

1. 응용–커널–하드웨어 경계와 자원관리·보호·공통 서비스의 역할을 설명한다.
2. 프로그램·프로세스·스레드, 실행문맥과 상태 전이를 구분한다.
3. 문맥교환의 절차와 직접·간접 오버헤드, 응답성과의 교환관계를 설명한다.
4. FCFS·SJF·SRTF·RR·우선순위·MLFQ의 원리와 전제·지표·기아를 비교한다.
5. 멀티코어 부하균형·친화도와 실시간 마감·WCET 분석의 기초를 연결한다.
6. 동기화·가상메모리·시스템 인터페이스는 이어지는 세 절과 함께 운영체제 전체를 구성한다.

이어지는 동기화·가상메모리·시스템 프로그래밍 절에서는 같은 실행흐름이 공유상태와 메모리, 장치 인터페이스를 사용하는 과정을 살펴본다.

문맥교환과 스케줄링을 답안으로 연결한다

문맥교환을 설명할 때는 전환 원인, 현재 문맥의 보존, 다음 흐름의 선택과 필요한 환경의 복원을 답안 항목으로 정리한다. 이는 역할을 연결한 개념모형이며 모든 커널의 실제 호출순서를 고정한 절차는 아니다. 직접 비용과 캐시·TLB 같은 간접 비용을 나누어 계측·할당량·친화도 조치와 연결한다.

CPU·디스크 스케줄링을 함께 설명할 때는 선택 기준의 단위부터 구별한다. 이 절의 SJF·SRTF는 CPU 버스트와 선점을, 회전식 디스크 스케줄링은 큐·탐색·회전·전송과 공정성을 다룬다. 종합 답안에서는 두 기준을 같은 비교 축으로 옮겨 볼 수 있다.

이 연결은 교재의 학습 안내다. 해당 주제의 실제 기출 여부와 출제경향은 공식 원문을 따로 확인해야 하며, 여기의 답안을 공식 채점 기준으로 해석하지 않는다.

시험에서는 어떻게 묻는가: 10점

다음은 이 절의 학습목표를 확인하기 위한 자체 제작 문제다.

FCFS, SJF, SRTF, RR CPU 스케줄링의 작동원리와 선점 여부를 비교하고, 응답성·평균 대기시간·문맥교환·기아 관점의 선택기준을 설명하시오.

알고리즘 이름만 나열하면 부족하다. 준비된 작업을 고르는 기준, 새 작업 도착 시 현재 실행을 뺏는지, 어떤 지표를 개선하고 어떤 실패 위험을 감수하는지 연결해야 한다.

답안 목차·풀이·교정 근거 보기

10점 답안 목차

1. 정의와 평가기준
   • 실행가능 작업에 CPU 배분, 응답·대기·반환·처리량·공정성
2. 알고리즘 원리와 선점
   • FCFS 도착순서, SJF 짧은 예측버스트
   • SRTF 짧은 잔여시간 선점, RR 순환·시간할당량
3. 비교와 실패조건
   • 호위효과, 예측오차·기아, 할당량과 문맥교환
4. 선택·검증
   • 부하·목표·전환비용, 지연분포와 최장대기 계측

10점 답안 도식

실행가능 집합에서 고르는 기준	방식	선점	함께 검증할 비용·실패
도착순서	FCFS	비선점	긴 작업 뒤의 호위효과
최소 예측 버스트	SJF	비선점	예측오차·긴 작업 기아
최소 잔여 예측시간	SRTF	선점	선점비용·예측오차·기아
순환순서와 시간할당량	RR	선점	첫 응답과 문맥교환 비용의 교환

모든 방식은 응답·대기·반환시간과 처리량·공정성을 함께 검증한다. 실제 시간축과 전체 비교표의 전제를 답안에도 유지한다.

10점 모범답안

CPU 스케줄링은 실행가능 프로세스나 스레드 중 다음 실행대상을 선택하고 CPU 시간을 배분하는 정책과 메커니즘이다. 평가는 첫 실행까지의 응답시간, 실행가능 큐의 대기시간, 도착부터 완료까지 반환시간, 처리량과 기아 없는 공정성을 함께 사용한다.

FCFS는 도착순서대로 비선점 실행하여 단순하지만 긴 작업 뒤 짧은 작업이 기다리는 호위효과가 있다. SJF는 준비된 작업 중 다음 예측 CPU 버스트가 가장 짧은 작업을 비선점 선택한다. 길이를 정확히 아는 이상조건에서는 평균 대기를 줄이지만 실제 예측오차와 긴 작업 기아가 있다. SRTF는 남은 예측시간이 더 짧은 새 작업이 오면 현재 작업을 선점하므로 짧은 작업 응답을 개선할 수 있지만 선점·예측 비용과 기아가 커진다. RR은 각 흐름에 시간할당량을 주고 실행가능 큐를 순환한다. 할당량이 크면 FCFS에 가까워지고 너무 작으면 문맥교환 비율이 증가한다.

따라서 배치 부하에서 예측이 유효하면 SJF 계열, 대화형 응답과 기회분배가 중요하면 RR을 검토하되 하나의 평균값만으로 결정하지 않는다. 실제 도착·버스트 분포에서 응답·대기 분포, 최장대기, 처리량과 문맥교환 시간 비율을 측정하고, 긴 작업 기아에는 에이징이나 최대대기 규칙을 둔다.

시험에서는 어떻게 묻는가: 25점

다음은 본문만으로 풀 수 있게 만든 자체 제작 설계 문제다.

상호작용 요청과 장시간 분석 작업이 혼재하는 멀티코어 서비스의 CPU 스케줄링 방안을 설계하시오. 프로세스·스레드 상태와 문맥교환, 정책·지표, RR·우선순위·MLFQ의 조합, 기아·과부하·코어 이동 실패 및 검증방안을 설명하시오.

요구어가 설계이므로 MLFQ 정의만 쓰면 부족하다. 부하를 분류하고 상태·큐·선점 흐름을 그린 뒤, 응답성과 처리량, 공정성과 전환·이동비용을 함께 통제해야 한다.

답안 목차·풀이·교정 근거 보기

25점 답안 목차

1. 목표·경계·부하
   • 스레드 단위, 상호작용/분석 혼합, 응답·처리량·공정성 목표
2. 상태·문맥교환 메커니즘
   • 실행가능–실행–대기 전이, 저장–선택–복원, 직접/캐시 비용
3. 정책과 멀티코어 구조
   • 우선순위별 RR·MLFQ, 시간할당량, 에이징·주기적 승격
   • 코어별 큐, 친화도, 부하균형·작업 훔치기
4. 지표·교환관계
   • 응답·대기·반환·처리량, 전환률·이동률, 평균과 상위지연
5. 실패와 통제
   • 기아, 과도한 전환·이동, 과부하, 상태/큐 불일치
6. 검증과 재조정
   • 대표·급증·최악 부하, 불변조건, 정책 전제 변화

25점 답안 도식

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

이 그림은 큐 이동 정책이고 CPU 코어와 고정 대응하지 않는다. 높은 큐는 짧은 q로 응답을, 낮은 큐는 긴 q로 분석 처리를 돕는다. 할당량을 반복 소진하면 내려가며 에이징·주기적 전체 승격은 올라가는 별도 조건이다. 유입·추월 한도를 정하지 않은 에이징만으로 최대대기가 보장되지는 않는다.

상자 안의 대상과 화살표의 조건을 함께 읽으세요. 좁은 화면에서는 같은 관계를 세로로 재배치한 도식을 보여 줍니다.

CPU0·CPU1은 코어별 실행큐를 보여 주는 두 대표이며 실제 코어 수를 한정하지 않는다. 흐름은 가능한 기존 코어의 친화도를 유지하되 큐 불균형이 크면 다른 큐로 이동하거나 작업을 훔친다. 우선순위 큐와 특정 코어를 고정 연결하지 않는다.

입출력·조건 대기, 사건 완료와 선점은 앞의 상태 전이도에 그대로 적용한다. 전환에서는 문맥 저장·다음 흐름 선택·필요한 환경 복원 후 실행을 재개하며, 검증은 응답·대기·처리량과 최장대기·전환률·코어 이동률을 함께 본다.

25점 모범답안

대상은 한 서비스 프로세스의 요청처리 스레드와 별도 분석 프로세스의 계산 스레드이며, 커널이 스레드 단위로 CPU를 배분한다고 가정한다. 상호작용 요청은 첫 응답과 상위 응답시간, 분석은 처리량과 완료시간을 우선하되 모든 실행가능 흐름에 최대대기 목표를 둔다. 실제 상한을 보장하려면 유입량·동시 실행가능 작업 수·시간할당량·승격 후 순서·우선 예외의 한도까지 제한해야 하며 에이징이라는 이름만으로 상한이 생기지는 않는다. 실제 중요도를 나타내는 정적 우선순위와 관찰된 CPU 사용행동을 나타내는 피드백을 구분한다.

스레드는 실행가능·실행·대기 상태를 오간다. 입출력이나 조건을 기다리면 대기로 이동하고 사건이 끝나면 실행가능 큐로 돌아온다. 타이머의 시간할당량 만료나 더 높은 우선순위 흐름 도착 시 현재 실행문맥을 저장하고, 큐·상태를 갱신해 다음 흐름을 선택한 뒤 문맥을 복원한다. 문맥교환에는 저장·복원·스케줄러의 직접시간과 캐시 재사용 손실이 있으므로 횟수와 시간을 모두 계측한다.

정책은 우선순위별 큐 안에서 RR을 사용하고 큐 사이에는 MLFQ 피드백을 적용한다. 짧게 실행한 뒤 자주 대기하는 흐름은 짧은 시간할당량의 높은 큐에서 빠르게 응답하게 한다. 할당량을 반복 소진하는 계산 흐름은 더 긴 할당량의 낮은 큐로 이동시켜 전환비용을 줄인다. 낮은 큐도 실행기회를 잃지 않도록 대기시간 기반 에이징과 주기적 전체 승격을 두고, 외부에서 부여한 긴급 우선순위는 권한·상한·만료시간을 검증한다. 정책게임 통제를 위해 차례별 시간할당량과 큐별 누적 CPU 예산을 따로 정하고, 짧은 입출력 대기만으로 누적 사용량을 초기화하지 않는다. 예산 소진 시 강등하고 승격 시 예산 재부여 규칙을 적용한다.

멀티코어에는 코어별 실행큐를 두어 전역 큐 경합을 줄이고, 가능하면 이전 코어에서 다시 실행해 캐시 친화도를 유지한다. 다만 큐 길이와 예상 작업량의 불균형이 임계값을 넘으면 빈 코어가 다른 큐의 작업을 훔치게 한다. 친화도 고정은 불균형을, 과도한 이동은 캐시 손실을 만들므로 코어별 큐 길이·이동률·실행시간으로 균형을 조정한다.

실패통제는 네 가지다. 첫째 낮은 우선순위의 최장대기와 승격 이력을 검사해 기아를 막는다. 둘째 시간할당량별 응답개선과 문맥교환 시간 비율을 함께 측정해 과도한 선점을 막는다. 셋째 급증부하에서 큐 길이 상한과 입장제어를 두어 모든 요청의 지연이 무한히 늘지 않게 한다. 넷째 실행 중인 스레드는 논리 CPU당 최대 하나, 대기 스레드는 실행가능 큐에 없음, 실행가능 스레드는 정확히 한 큐에 존재라는 불변조건을 검사한다.

검증은 짧은 요청만, 긴 분석만, 혼합·급증·한 코어 장애에 가까운 가용코어 감소를 포함한다. 평균뿐 아니라 응답·대기 상위분포, 처리량, 최장대기, 전환·이동률과 CPU 이용률을 비교한다. 부하분류나 목표가 바뀌면 숫자만 미세조정하지 말고 큐 구조와 정책의 전제를 다시 평가한다.

예를 들어 논리 CPU 하나, 전환비용 0, 동시 실행가능 흐름 최대 3개, 높은 큐 q=2ms, 낮은 큐 q=4ms, 전체 승격 주기 8ms의 교육 모형을 정하자. 승격 시 오래 기다린 흐름부터 높은 큐에 넣고 이후 도착은 뒤에 넣으며, 승격 큐 앞을 무한히 추월하는 긴급 예외는 허용하지 않는다. 낮은 큐의 L이 시각 0부터 기다리는 동안 높은 큐의 H1·H2·H3·H4가 각각 [0,2), [2,4), [4,6), [6,8)에 실행·완료하고 다음 H가 들어오는 부하라면, 시각 8의 승격에서 L을 먼저 넣어 [8,10)에 실행시킨다. L의 첫 대기는 8ms이며, 실제 trace에서 승격과 실행기회를 확인할 수 있다.

이 제한 모형에서 막 실행가능해진 흐름은 다음 승격까지 최대 8ms, 그때 앞선 최대 두 흐름의 할당량 합 4ms를 더한 12ms 이내에 첫 CPU 기회를 얻는다. 전환·인터럽트·비선점 커널 구간이 있으면 그 상한을 더해야 하고, 유입 제한이나 승격 후 순서가 깨지면 이 수치는 보장되지 않는다. 이는 I/O 대기나 전체 작업 완료시간의 상한도 아니다.

근거와 현행성

프로세스·스레드 스케줄링의 인터페이스 경계와 runnable·정책·우선순위 개념은 IEEE와 The Open Group의 이식형 운영체제 인터페이스(Portable Operating System Interface, POSIX) 1-2024, Issue 8 XSH Chapter 2 및 관련 설계근거를 대조했다. 이는 이식 가능한 응용–운영체제 인터페이스의 규범이며 모든 운영체제의 내부 스케줄러 구현을 규정하는 자료로 일반화하지 않는다.

현행 구현 사례는 Linux 커널 Earliest Eligible Virtual Deadline First (EEVDF) 스케줄러 문서를 기준 확인일 2026-09-01에 별도 동결해 대조했다. Linux 문서는 rolling 자료이며 이 절의 FCFS·SJF·RR·MLFQ 일반이론 전체를 Linux가 그대로 구현한다는 근거로 쓰지 않았다. 본문의 상태도·비교표·계산예제·문제·답안 도식은 원문을 복제하거나 번역하지 않고 교재용으로 독자 구성했다.

모드 전환과 문맥교환의 구분은 저자들이 공개한 Operating Systems: Three Easy Pieces 1.10의 Limited Direct Execution §6.2–6.3, 비선점 SJF와 선점형 최단잔여시간의 차이는 Scheduling: Introduction §7.4–7.5, §7.8, MLFQ의 누적 CPU 회계는 MLFQ §8.4와 2026-10-09에 대조했다. 추가한 수치·도착시각 변경 연습과 풀이도 교재가 자체 구성했다.

실제 운영체제의 정책·필드·성능은 해당 버전의 공식 문서를 별도로 확인해야 한다. 교육용 스케줄링 계산을 특정 Linux 버전의 실행 결과로 일반화하지 않는다.

POSIX 자료는 응용 인터페이스의 정책·우선순위 경계를, Linux 문서는 자원별 구현 사례를 뒷받침한다. 문맥 저장·복원의 구체적인 예는 앞의 고정 Linux v6.6 코드와 대조한다. 이 구현 사례의 레지스터·주소공간 처리와 일반 개념모형을 구분하고, 다른 버전·아키텍처의 필수 순서나 전환 성능으로 일반화하지 않는다.

30초 정리

1. 운영체제는 응용과 하드웨어 사이에서 자원을 추상화·배분·보호하고 공통 서비스를 제공한다.
2. 프로세스는 자원·보호의 실행 단위이고 스레드는 그 자원을 공유하며 CPU가 이어서 실행할 흐름이다.
3. 문맥교환은 실행문맥을 저장·선택·복원하는 절차이며 직접시간과 캐시 손실을 지불한다.
4. FCFS·SJF·SRTF·RR·우선순위·MLFQ는 목표·부하·선점·기아·전환비용을 같은 축에서 비교한다.
5. 멀티코어는 친화도와 부하균형, 실시간은 WCET와 마감의 최악조건 분석을 추가해야 한다.

다음 절에서는 여러 실행흐름이 같은 상태를 바꿀 때 생기는 경쟁조건을 막으면서도 교착·기아에 빠지지 않도록 동기화하는 원리를 살펴본다.

추가 연습 — 도착시각과 선점 판단

앞의 두 작업 사례에서 A는 도착 0ms·CPU 실행시간 8ms, B는 CPU 실행시간 2ms다. 논리 CPU 하나·입출력 없음·문맥교환 비용 0이고 실제 실행시간을 정확히 안다는 조건을 유지한다.

조건 변경 연습: B가 시각 6에 도착한다면 SRTF의 실행순서와 B의 대기·첫 응답은 어떻게 되는가? 나머지 조건은 같고, 잔여시간이 같으면 현재 실행 중인 작업을 유지한다.

도착시각과 잔여시간을 대조한 풀이 보기

시각 6에 A는 8−6=2ms가 남아 B의 2ms와 같다. 더 짧은 작업이 아니고 동률 규칙도 현재 실행을 유지하므로 [0,8) A → [8,10) B다. B의 반환시간은 10−6=4ms, 대기는 4−2=2ms, 첫 응답은 8−6=2ms다. 새 작업이 왔다는 사실만으로 선점하지 않고 그때의 잔여시간과 동률 규칙을 확인한다.