[CS기초] 9주차 개념정리

9주차 개념 정리

아래의 내용을 코드 블럭 우측 상단의 Copy 버튼을 눌러 복사한 뒤, 퀴즈 로봇(신명훈 학우 제작)의 프롬프트에 붙여넣기하면 핵심 개념들에 대한 퀴즈를 풀어볼 수 있습니다.

 

□ Process
	• 실행 중인 프로그램
	• 운영체제로부터 독립된 메모리 영역을 할당받아 실행됨
	• 각 프로세스는 고유한 코드, 데이터, 힙, 스택 영역을 가짐
	• 프로세스 간 통신은 파이프, 소켓 등 IPC(Inter-Process Communication)가 필요
	• 컨텍스트 스위칭 시 오버헤드가 큼

■ PCB(Process Control Block)
운영체제가 각 프로세스를 관리하기 위해 유지하는 메타데이터를 담은 자료구조
▶ 메타데이터 종류
	• PID
	• 프로세스 상태
	• 레지스터 값(Program Counter, Stack Pointer 등)
	• 메모리 정보
	• I/O 정보
	• 기타 프로세스 실행에 필요한 모든 정보

■ 프로세스 상태 전이
	• new → ready → running → waiting/blocked → ready → running → … → terminated
	• ready → running 주체: 스케줄러
	• running → blocked 주체: I/O 등

■ 문맥 교환 (Context Switching)
운영체제가 현재 실행중인 프로세스의 상태를 PCB에 저장하고, 
다른 프로세스의 PCB에 저장된 상태를 복원하여 CPU 제어권을 넘기는 과정
※ 스레드 간에도 TCB를 통해 문맥교환 가능 (자원을 공유하므로 프로세스 간 전환보다 비용이 적게 듦)

▶ 문맥 교환 과정
	1. 커널 모드 진입
	2. 현재 프로세스의 PCB 저장 (백업)
	3. 새로운 프로세스의 PCB 불러오기
	4. 사용자 모드로 전환하여 계속 실행
	
▶ 문맥 교환 비용
	• 레지스터, PC, 스택 등 저장/복원
	• 커널 모드/사용자 모드 전환
	• TLB(Translation Lookaside Buffer) 무효화
	• CPU 캐시 무효화 (Cache Flush)
		○ 특정 프로세스의 메모리 접근에 최적화되어 있으므로, 다른 프로세스 전환 시 캐시 히트율 급감
────────────────────────────────────────────────────────────────────────────────────────────────────
□ Thread
	• 프로세스 내부의 실행 단위
	• 하나의 프로세스가 여러 개의 스레드를 가질 수 있음
	• 스레드 간 코드, 데이터, 힙 영역을 공유하고, 스택만 별도로 가짐
	• 스레드 간 통신은 메모리를 서로 공유하기 때문에 간단하고 빠름
	• 컨텍스트 스위칭 비용이 적음
	• 단, 자원 공유에 따른 동기화가 필요하고, 한 스레드에 문제가 생기면 전체 스레드에 영향이 갈 수 있음

■ 사용자 수준 스레드 vs 커널 수준 스레드
▶ 사용자 수준 스레드(User-Level Threads)
	• 커널이 하나의 프로세스만 인식하며, 스레드 관리를 사용자 라이브러리가 수행
	• 가볍지만 병렬성과 블로킹 처리에 제약이 있음
		○ 한 스레드 블로킹 시 전체 스레드가 전부 멈출 수 있음
	• pthreads, GNU Portable Threads 등

▶ 커널 수준 스레드(Kernel-Level Threads)
	• 커널이 각 스레드를 독립적인 실행 단위로 직접 인식하고 관리
	• 진정한 병렬성과 블로킹 분리가 가능하지만 문맥 전환 비용이 큼
		○ 전환 시 커널/사용자 모드 변경 필요
	• Linux의 clone(), Windows의 CreateThread() 등
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 프로세스 vs 스레드 비교
	• 주소 공간: 프로세스 독립, 스레드는 공유
	• 상호 침범 위험: 프로세스는 메모리 보호, 스레드는 동기화 실패 시 데이터 손상
	• IPC 필요성: 프로세스 간 파이프/소켓, 스레드는 전역 변수 활용
	• 문맥 교환 비용: 프로세스 >> 스레드
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 동시성 문제(Bugs) 관련 개념
▶ Race Condition (경쟁 상태)
	• 둘 이상의 프로세스/스레드가 공유 자원에 동시에 접근하여,
      누가 먼저 실행되는지에 따라 결과가 예측 불가능한 상태
▶ Critical Section (임계 구역)
	• 동시 접근 시 일관성이 깨질 위험이 있는 코드 영역
▶ Starvation과 Livelock
	• Starvation: 특정 프로세스의 우선순위가 낮아 자원을 계속 할당받지 못하는 상태
	• Livelock: 특정 프로세스가 계속 양보만 하여 작업을 못하고 있는 상태
▶ Priority Inversion (우선순위 역전)
	• 낮은 우선순위의 스레드가 자원을 잡고 있어 높은 우선순위의 스레드가 대기하고 있는 상태
────────────────────────────────────────────────────────────────────────────────────────────────────
□ 동기화 기법
■ Spinlock
락이 해제될 때까지 CPU를 양보하지 않고 반복적으로 대기(spin)하는 방식의 락 객체
	• 짧은 임계 구역에서 빠른 락 획득이 필요한 상황에 적합
	• busy-wait 방식으로 문맥 전환이 없어 빠르지만, CPU를 자원을 계속 낭비할 수 있음
	• 짧은 임계 구역에 적합
■ Mutexlock
한 번에 하나의 스레드만 임계 구역에 진입할 수 있도록 보장하는 락 객체
	• 락을 획득하지 못한 스레드는 sleep 상태로 전환되어 CPU 자원 절약 가능
	• blocking 방식으로 문맥 전환이 발생, spinlock보다 느릴 수 있지만 CPU 낭비가 없음
	• 긴 임계 구역이나 병렬 처리에서의 자원 보호에 효과적
■ Semaphore
공유 자원의 접근 개수를 제어하는 동기화 도구
	• 카운터 값을 기준으로 여러 스레드의 접근을 제어하거나 대기/신호(sync) 기능을 수행
	• 0/1 값 기반으로 임계 구역 보호에도 사용 가능
		○ 다만 lock처럼 소유권 개념이 있는 상호배제가 아님
		○ 누구든지 재접근 및 해당 자원의 up/down을 수행할 수 있음
■ Condition Variable
'특정 조건'이 만족될 때까지 스레드를 sleep 상태로 대기시켰다가,
다른 스레드의 신호(signal)로 깨어나게 하여 스레드 간 동기화를 수행하는 도구
	• 공유 자원의 상태 변화 조건을 기다릴 때 사용
	• 단독으로 쓰이지 않고 반드시 lock(주로 뮤텍스)와 함께 사용됨
────────────────────────────────────────────────────────────────────────────────────────────────────
□ Deadlock
둘 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 영원히 대기하고 있는 상태
▶ Deadlock의 4가지 필수 조건
	• 상호배제
	• 점유 및 대기
	• 비선점
	• 환형 대기

▶ Deadlock 예방, 회피, 탐지/복구 방법
	• 예방: 4가지 조건 중 하나를 제거
		○ 자원을 모두 한꺼번에 요청하게 하기 (점유 및 대기 제거)
		○ 자원을 선점 가능하게 하기 (비선점 제거)
		○ 자원에 정해진 순서로만 요청하게 하기 (환형 대기 제거)
	• 회피: Banker의 Algorithm (안전/불안전 상태 검사)
	• 탐지: Wait-For Graph / 회복: 선점, 롤백, 강제 종료 등
────────────────────────────────────────────────────────────────────────────────────────────────────
□ CPU 스케줄링 알고리즘
어떤 프로세스에 얼마나 CPU를 할당할지에 대한 순서를 결정하는 운영체제의 핵심 메커니즘

■ 스케줄링 성능 기준
	• Waiting Time: CPU를 기다리는 시간
	• Turnaround Time: 프로세스 요청이 처리되는 총 시간
	• Response Time: 요청 후 첫 반응까지 걸리는 시간
	• Throughput: 단위 시간당 처리된 작업 수

■ 주요 CPU 스케줄링 알고리즘
▶ FCFS(First Come First Serve)
	• 도착한 순서대로 처리
	• 간단하지만 Convoy Effect 발생 가능
▶ SJF (Shortest Job First)
	• CPU burst가 짧은 순서대로 처리
	• 이론상 평균 대기 시간이 가장 적지만, 현실적으로 예측이 어려움
▶ Priority Scheduling
	• 우선순위가 높은 프로세스를 먼저 실행
	• Starvation 발생 가능 (Aging 기법 필요)
▶ Round Robin
	• 순서에 따라 Time Slice만큼 CPU를 할당
	• 공정성 확보 및 응답시간 향상 가능
	• CPU 활용에 대해 비효율 발생 가능
▶ Multilevel Queue
	• 프로세스 성격에 따라 큐를 분리하고, 각 큐마다 맞춤형 스케줄링 정책을 사용
	• 큐 간 우선순위(상위 큐/하위 큐)가 존재하며, 큐 간 이동이 없어 유연성이 부족
▶ MLFQ (Multilevel Feedback Queue)
	• 프로세스 실행 패턴에 따라 우선순위를 동적으로 조절해 여러 큐 사이를 이동시키는 기법
	• 복잡하지만 유연하고 효율적
────────────────────────────────────────────────────────────────────────────────────────────────────
□ MLFQS (Multi Level Feedback Queue Scheduling)
프로세스의 특성을 파악해 동적으로 우선순위를 조절하는 4.4BSD 스케줄러 기반의 다단계 큐 방식
	• 4.4BSD는 UNIX 기반의 대표적인 연구용 운영체제
		○ 네트워킹, 가상 메모리, 스레드, 스케줄링 등 현대 OS 설계에 큰 영향을 끼친 고전 시스템
		○ 4.4BSD의 설계 철학과 스케줄링 원리를 교육용으로 단순화해 구현한 소형 운영체제 커널이 Pintos이다

■ 핵심 아이디어
	• 짧게 CPU를 쓰는 I/O 중심 프로세스는 높은 우선순위를 유지
	• CPU를 오래 쓰는 계산 중심 프로세스는 낮은 우선순위로 강등시켜 점진적으로 실행
	• 이를 통해 응답성 보장 + Starvation 방지를 실현

■ 핵심 특징
	• 여러 개의 우선순위 큐를 가지며, 높은 우선순위 큐부터 CPU 할당
	• 프로세스가 상하 큐로 이동 가능 (Feedback)
	• 오랜 시간 CPU를 사용하지 않으면 우선순위 상승
	• 반대로 너무 오랫동안 CPU를 사용하면 우선순위 강등
	• 상위 큐는 Round Robin, 하위 큐는 FCFS를 혼합해서 사용
	• CPU burst가 짧은 프로세스는 빠르게 응답하게 하고, 긴 프로세스는 점진적 실행이 목표

■ 주요 구성 요소
	• nice: 프로세스의 우선순위에 영향을 주는 사용자 조정값
		○ 낮을수록 우선순위가 높아짐
	• recent_cpu: 각 프로세스의 CPU 사용량 추적값.
		○ 많이 사용하면 우선순위를 낮춤
	• load_avg: 시스템의 전체 부하를 나타내는 값
		○ recent_cpu에 영향을 줌 (부하가 높아지면 recent_cpu도 상승)