[전공 기말고사 정리] 운영체제론 – 병행실행·교착상태·스케줄링·세마포어·시스템 보안

━━━━━━━━━━━━━━━━━━
Chapter 05. 비동기식 병행실행
━━━━━━━━━━━━━━━━━━

1. 비동기식 병행 실행이란?

여러 스레드(실행 흐름)가 동시에 실행되면서 서로 공유 데이터에 접근하는 상황입니다. 두 직원이 같은 엑셀 파일을 동시에 수정하려 할 때 충돌이 생기는 것과 같은 원리입니다.

핵심 용어 3가지

• 스레드(Thread): 프로그램 안에서 독립적으로 실행되는 실행 단위. 하나의 프로세스 안에 여러 개 존재 가능
• 임계 영역(Critical Section): 한 번에 하나의 스레드만 실행해야 하는 코드 구간(예: 공유 변수 수정)
• Race Condition(경쟁 조건): 동기화 없이 여러 스레드가 공유 자원에 동시 접근할 때 실행 순서에 따라 결과가 달라지는 현상
2. 동기화 없이 실행하면 생기는 문제

생산자가 숫자를 버퍼에 쓰고 소비자가 읽어서 합계를 구하는 상황에서, 동기화가 없으면 생산자가 값을 쓰기 전에 소비자가 읽거나 같은 값을 두 번 읽을 수 있습니다. 그 결과 합계가 매번 달라져(2, 4, 10, 13 등) 정확한 값인 10이 나오지 않습니다.

3. 소프트웨어 해결책 — 버전 1~4의 문제점
• 버전 1(고정 교대 실행): 빠른 스레드도 느린 스레드를 기다려야 함 → 고정 동기화 문제
• 버전 2(플래그 확인): 동시에 “상대방 없음”을 확인해 동시 진입 가능 → 상호배제 위반
• 버전 3(플래그 선설정): 두 스레드가 동시에 플래그=1이 되어 서로 무한 대기 → 교착 상태
• 버전 4(양보 반복): 동일 타이밍에 양보를 무한 반복할 수 있음 → 무기한 연기
4. 완전한 해결책 — 3가지 알고리즘
• 데커(Dekker): 가장 처음 제안된 완전한 해결책, 2개 스레드만 지원, favoredThread로 충돌 시 우선권 결정
• 페터슨(Peterson): 데커보다 간단하지만 동일한 효과, 2개 스레드만 지원, “상대방 먼저” 표시 + 조건 확인
• 베이커리(Bakery): N개 스레드 지원, FCFS 순서 보장, 번호표 뽑기 시스템과 같은 원리

완전한 해결책의 3가지 조건
① 상호 배제(Mutual Exclusion): 한 번에 하나의 스레드만 임계 영역 진입
② 교착 상태 없음(No Deadlock): 프로그램이 영원히 멈추지 않음
③ 무기한 연기 없음(No Starvation): 언젠가는 반드시 임계 영역에 진입 가능

5. 하드웨어 해결책

소프트웨어만으로는 한계가 있어 CPU 하드웨어 자체에서 원자적(Atomic)으로 실행되는 명령어를 제공합니다. 원자적이라는 것은 중간에 다른 스레드가 끼어들 수 없다는 뜻입니다.

• testAndSet(a,b): b의 값을 a에 복사하고 b를 1(잠금)로 설정, 두 동작이 분리 불가능하게 실행
• swap(a,b): a와 b의 값을 교환, key=1에서 시작해 occupied와 교환했을 때 0이면 진입 허가
6. 세마포어(Semaphore) — POSIX sem_t

세마포어는 공유 자원에 접근할 수 있는 스레드 수를 제어하는 카운터+신호등입니다.

• sem_init(&sem, 0, n): 세마포어 초기화(초기값 n), 자원 n개 사용 가능하다고 설정
• sem_wait(&sem): P 연산(값 -1), 값이 0이면 블로킹(대기), 0보다 크면 진입
• sem_post(&sem): V 연산(값 +1), 값 증가 + 대기 중인 스레드 깨움
• sem_destroy(&sem): 세마포어 해제, 프로그램 종료 전 반드시 호출
• 이진 세마포어(초기값 1): 한 번에 1개 스레드만 임계 영역 진입(로그 파일 쓰기, counter++ 보호 등)
• 카운팅 세마포어(초기값 n, n>1): 동시에 최대 n개 스레드 접근 허용(DB 연결 풀 3개 제한 등)

━━━━━━━━━━━━━━━━━━
Chapter 06. 병행 프로그래밍
━━━━━━━━━━━━━━━━━━

1. 병행 프로그래밍이란?

여러 스레드/프로세스가 동시에 실행되는 것처럼 보이도록 설계하는 프로그래밍 방식입니다. Ch05가 낮은 수준(플래그·세마포어 직접 조작)이라면, Ch06은 더 높은 수준의 안전한 동기화 도구를 사용합니다.

2. 모니터(Monitor)

모니터는 공유 데이터(변수)와 그 데이터를 사용하는 프로시저(함수)를 하나의 객체로 묶어 자동으로 상호 배제를 보장하는 동기화 도구입니다.

은행 창구에 비유하면, 창구(모니터) 안에는 직원 1명(스레드)만 고객을 응대할 수 있고, 다른 고객(스레드)은 밖에서 줄 서서 대기(자동 상호 배제)하며, 창구 규칙(프로시저)을 통해서만 업무(데이터 접근)가 가능합니다.

모니터의 구성 요소

• 공유 데이터(Shared Data): 모니터 내부에서만 접근 가능한 변수들
• 모니터 진입 루틴(monitorEntry): 외부 스레드가 모니터에 접근하는 유일한 통로
• 상태 변수(Status Variable): 자원 사용 여부를 나타내는 boolean 변수
• 조건 변수(Condition Variable): 특정 조건이 될 때까지 스레드를 대기시키는 변수
3. 조건 변수 — wait()와 signal()
• wait(condVar): 현재 스레드를 대기 상태로 만들고 모니터 잠금 해제 (자바의 wait()에 대응)
• signal(condVar): 대기 중인 스레드 하나를 깨워 실행 재개 (자바의 notify()에 대응)

모니터 종류

• 신호 후 종료(signal-and-exit): signal 후 즉시 모니터 퇴장, 깨어난 스레드가 즉시 실행
• 신호 후 계속(signal-and-continue): signal 후 현재 스레드가 계속 실행 (자바가 이 방식 사용)
4. 자바(Java) 모니터

자바는 synchronized 키워드로 모니터 기능을 언어 차원에서 직접 지원합니다.

• synchronized: 메소드에 붙이면 한 번에 하나의 스레드만 실행(자동 상호 배제)
• wait(): 현재 스레드 대기 + 잠금 해제(조건 변수의 wait 역할), 항상 while 안에서 사용
• notify(): 대기 스레드 1개를 깨움(signal 역할), 대기 종류가 1가지일 때 사용
• notifyAll(): 대기 중인 모든 스레드를 깨움, 여러 종류 스레드 대기 시 안전

wait()를 if가 아닌 while 안에서 쓰는 이유
notifyAll()로 여러 스레드가 깨어났을 때, 첫 번째 스레드가 자원을 사용하면 두 번째 스레드가 깨어났을 때 이미 자원이 없을 수 있습니다. if문을 쓰면 조건 확인 없이 진행되어 오류가 발생하지만, while문을 쓰면 조건을 재확인해 다시 wait()로 돌아가 안전합니다. 이를 “거짓 깨우기(spurious wakeup)” 방어라고 합니다.

5. 생산자/소비자 패턴

동기화가 없는 UnsynchronizedBuffer(Ch05)는 결과가 매번 다르게 나오는 Race Condition이 발생하지만, synchronized 메소드를 사용하는 SynchronizedBuffer(Ch06)는 wait()로 블록하고 notify()로 깨우는 방식으로 항상 올바른 결과(합계 10)를 보장합니다.

6. 원형 버퍼(Circular Buffer)

고정 크기 배열을 원처럼 순환해서 사용하는 자료구조입니다. 생산자가 소비자보다 몇 개 앞서 생산할 수 있어 성능이 향상됩니다.

핵심 수식: 다음 위치 = (현재 위치 + 1) % 배열 크기
예를 들어 배열 크기가 5일 때 0→1→2→3→4→0(처음으로 돌아감)→1→… 순으로 순환합니다.

• 버퍼가 꽉 참(occupiedSlots == 배열크기): 생산자는 wait(hasSpace)
• 버퍼가 비어있음(occupiedSlots == 0): 소비자는 wait(hasData)
7. 리더/라이터(Reader-Writer) 모니터

데이터베이스를 여러 스레드가 읽거나 쓸 때의 동기화 문제입니다.

• 리더(Reader): 데이터를 읽기만 함, 수정 없음. 라이터가 쓰는 중이거나 대기 중이면 진입 불가
• 라이터(Writer): 데이터를 수정함. 다른 리더/라이터가 있으면 진입 불가(배타적 접근)

━━━━━━━━━━━━━━━━━━
Chapter 07. 교착 상태와 무기한 연기
━━━━━━━━━━━━━━━━━━

1. 교착 상태(Deadlock)란?

두 개 이상의 프로세스가 서로 상대방이 가진 자원을 기다리며 영원히 진행하지 못하는 상태입니다. 4방향 교차로에서 차 4대가 서로 양보를 기다리며 아무도 못 지나가는 상황에 비유할 수 있습니다.

예: P1은 R1을 보유한 채 R2를 요청 중이고, P2는 R2를 보유한 채 R1을 요청 중이면, P1은 P2가 R2를 놓아줄 때까지, P2는 P1이 R1을 놓아줄 때까지 서로 기다리게 되어 영원히 해결되지 않는 교착 상태가 됩니다.

2. 교착 상태 vs 무기한 연기(Starvation)

교착 상태는 프로세스들이 서로 상대방 자원을 기다리는 순환 대기(Circular Wait)가 원인이며 관련 프로세스가 모두 멈춥니다. 해결 방법은 방지/회피/탐지/복구입니다.

무기한 연기는 특정 프로세스가 우선순위에서 계속 밀리는 스케줄링 정책의 편향이 원인이며, 시스템은 동작하지만 특정 프로세스만 실행되지 못합니다. 해결 방법은 에이징(Aging) 기법입니다.

에이징(Aging) 기법
대기 시간이 길수록 프로세스의 우선순위를 점진적으로 높여주는 방법입니다. 예를 들어 처음 우선순위 5에서 10초 대기 후 4, 20초 대기 후 3으로 점차 높아져 결국 가장 높은 우선순위를 달성하게 되며, 이를 통해 무기한 연기를 완전히 방지할 수 있습니다.

3. 교착 상태 발생의 4가지 필요조건(Coffman Conditions)

아래 4가지 조건이 동시에 성립해야만 교착 상태가 발생하며, 하나라도 깨면 교착 상태를 막을 수 있습니다.

① 상호 배제(Mutual Exclusion): 자원은 한 번에 하나의 프로세스만 배타적으로 사용 가능(예: 프린터는 1명만 사용 가능)
② 보유 후 대기(Hold and Wait): 자원을 보유한 채 다른 자원을 추가 요청하며 대기(예: R1 잡고 R2 기다리기)
③ 비선점(No Preemption): 프로세스가 보유한 자원을 강제로 빼앗을 수 없음(사용 중인 자원 강제 회수 불가)
④ 순환 대기(Circular Wait): 프로세스들이 원형 고리 형태로 서로의 자원을 대기(A→B→C→A 대기 사슬)

4. 교착 상태 해결책 4가지
• 방지(Prevention): 4가지 조건 중 하나를 원천 차단. 교착 상태를 원천적으로 막지만 자원 낭비, 성능 저하가 단점
• 회피(Avoidance): 자원 할당 전 안전 상태 검사(은행원 알고리즘). 안전한 상태를 유지할 수 있지만 모든 자원 필요량을 미리 알아야 함
• 탐지(Detection): 교착 상태 발생을 허용한 후 주기적으로 탐지. 자원 활용률은 높지만 탐지 오버헤드와 복구 비용 발생
• 복구(Recovery): 탐지 후 프로세스 종료 또는 자원 강제 반납. 유연하지만 작업 손실이 발생할 수 있음
5. 은행원 알고리즘(Banker’s Algorithm) — 회피의 핵심

자원을 할당하기 전에 시스템이 “안전 상태(Safe State)“를 유지할 수 있는지 미리 계산하는 방법입니다. 은행이 대출 가능 여부를 미리 계산하는 것과 같습니다.

• 안전 상태: 모든 프로세스가 유한 시간 내 완료를 보장(안전 순서가 존재) → 요청 허용
• 불안전 상태: 일부 프로세스가 완료를 보장받지 못함(안전 순서가 존재하지 않음) → 요청 거부

예시(총 자원 12개, 가용 자원 a=2인 경우)
P1은 최대 4 필요, 현재 1 대여로 추가 3 필요. P2는 최대 6 필요, 현재 4 대여로 추가 2 필요(a=2로 P2가 먼저 완료 가능). P3는 최대 8 필요, 현재 5 대여로 추가 3 필요.
→ 안전 순서 P2→P1→P3가 존재하므로 안전 상태입니다.
가용 자원이 a=1로 줄면 어떤 프로세스의 요구도 충족할 수 없어 불안전 상태가 됩니다.

6. 탐지 — 자원 할당 그래프 소거 알고리즘

그래프를 단계적으로 지워나가며 교착 상태 여부를 판단합니다.
① 모든 자원 요청을 충족할 수 있는 프로세스를 찾는다
② 해당 프로세스를 그래프에서 제거하고 보유 자원을 반납한다
③ 더 이상 제거할 프로세스가 없을 때까지 ①~②를 반복한다
④ 모든 프로세스가 소거되면 교착 상태 없음, 소거되지 않은 프로세스가 있으면 그 프로세스들이 교착 상태입니다

7. 복구 방법 3가지
• 프로세스 강제 종료: 교착 관련 프로세스를 강제 종료하고 자원을 반납. 진행 중이던 작업 손실이 단점
• 일시 정지/재시작: 프로세스를 일시 중단하고 안전 상태 회복 후 재개. 재시작 시 일부 작업 재처리가 필요
• 체크포인트/롤백: 주기적으로 상태를 저장해 교착 시 최근 체크포인트로 복원. 저장 오버헤드가 발생

━━━━━━━━━━━━━━━━━━
Chapter 08. 프로세서 스케줄링
━━━━━━━━━━━━━━━━━━

1. 프로세서 스케줄링이란?

CPU는 한 번에 하나의 프로세스만 실행할 수 있습니다. 여러 프로세스가 동시에 실행을 원할 때 어떤 순서와 방식으로 CPU를 할당할지 결정하는 것이 스케줄링입니다. 은행 창구(CPU)는 1개인데 손님(프로세스)이 여러 명일 때 어떤 순서로 처리할지 정하는 규칙에 비유할 수 있습니다.

2. 스케줄링 수준 — 3가지 레벨
• 고수준 스케줄링(High-Level): 시스템에 몇 개 프로세스를 올릴지 결정. 빈도 낮음. 다중 프로그래밍 정도 제어, 작업수락/거절
• 중간 수준 스케줄링(Mid-Level): 어떤 프로세스를 잠시 메모리에서 내릴지 결정. 빈도 중간. Swapping(메모리↔디스크)
• 저수준 스케줄링(Low-Level): 실제로 지금 CPU를 어떤 프로세스에 줄지 결정. 빈도 매우 높음(ms 단위). Dispatcher 동작으로 가장 중요
3. 선점형 vs 비선점형 스케줄링

CPU를 할당받은 프로세스를 중간에 뺏을 수 있는지 없는지의 차이입니다.

• 선점형(Preemptive): 실행 중 강제로 CPU를 빼앗을 수 있음. 응답 시간이 짧고, 문맥 전환 오버헤드가 발생. 대화식/실시간 시스템에 사용. 예: Round-Robin(RR), SRT
• 비선점형(Non-Preemptive): 자발적으로 반납할 때까지 계속 실행. 응답 시간이 길어질 수 있지만 오버헤드가 낮음. 배치 처리 시스템에 사용. 예: FIFO(선입선출), SPF

비유: 비선점형은 화장실에 들어간 사람이 볼일이 끝날 때까지 아무도 못 들어오는 것과 같고, 선점형은 긴급 상황(높은 우선순위) 발생 시 현재 사용자가 나와야 하는 것과 같습니다.

4. 우선순위 — 정적 vs 동적
• 정적 우선순위: 프로세스 생성 시 결정되어 이후 고정. 구현이 쉽고 오버헤드가 낮지만 상황 변화에 대응 불가능. 임베디드, 배치 시스템에 사용
• 동적 우선순위: 상황에 따라 변동. 구현이 복잡하고 오버헤드가 높지만 변화 대응이 가능. 대화식, 시분할 시스템에 사용
5. 성능 지표 — 시험에 자주 나오는 계산 공식
• 반환 시간(Turnaround Time) = 완료 시각 - 도착 시각 (작업 전체 소요 시간)
• 대기 시간(Waiting Time) = 반환 시간 - 실행 시간 (준비 큐에서 기다린 시간)
• 응답 시간(Response Time) = 첫 실행 시각 - 도착 시각 (처음 CPU를 받기까지 걸린 시간)
• 처리량(Throughput) = 완료 프로세스 수 ÷ 단위 시간 (단위 시간당 완료된 작업 수)
6. 프로세스 유형과 적합한 스케줄링
• CPU 중심(CPU-bound): CPU 연산 위주, 긴 burst time → SPF, SRT
• 입출력 중심(I/O-bound): I/O 요청 빈번, 짧은 CPU 사용 → 높은 우선순위 부여, Round-Robin
• 배치(Batch): 사용자 상호작용 없음, 대량 처리 → FIFO, SPF
• 대화식(Interactive): 빈번한 사용자 입력 필요 → Round-Robin, 다수준 피드백 큐

━━━━━━━━━━━━━━━━━━
세마포어 완전 정복
━━━━━━━━━━━━━━━━━━

1. 세마포어란?

세마포어는 여러 프로세스(스레드)가 공유 자원에 동시에 접근하는 것을 제어하는 동기화 도구입니다. 간단히 말해 “몇 명까지 들어올 수 있는지 알려주는 카운터 + 신호등”입니다.

2. 수영장 락커룸 비유로 이해하기

탈의실 3개(세마포어 초기값 3)라고 할 때, 손님 A 입장 시 탈의실 2개 남음(S=2), 손님 B 입장 시 1개 남음(S=1), 손님 C 입장 시 0개 남음(S=0), 손님 D는 S=0이므로 대기(줄을 섬), 손님 A가 퇴장하면 탈의실 1개가 생겨(S=1) 손님 D가 입장 가능해집니다.

• 입장 = wait() 또는 P() 연산 → 값을 -1
• 퇴장 = signal() 또는 V() 연산 → 값을 +1
• 대기줄 = 세마포어 큐(Queue)
3. 핵심 연산 2가지
• wait(): P(), down() 이라고도 함. 값을 -1하고 0 이하면 블로킹(대기 큐에 넣음). 자원 요청, 없으면 기다림
• signal(): V(), up() 이라고도 함. 값을 +1하고 대기자가 있으면 깨움. 자원 반납, 다음 사람 들어오게 함
4. 세마포어 2가지 종류
• 이진 세마포어(Binary Semaphore): 초기값 0 또는 1. 한 번에 1개 프로세스만 임계 구역 진입(뮤텍스와 거의 동일). 공유 변수 보호, 로그 파일 쓰기 보호에 사용
• 카운팅 세마포어(Counting Semaphore): 초기값 n(n≥1). n개의 동일한 자원 관리(수영장 탈의실 예시). DB 연결 풀 관리, 스레드 풀 제한에 사용
5. 임계 구역 보호 — 세마포어 사용 패턴

세마포어로 임계 구역을 감싸는 기본 패턴은 다음과 같습니다.

semaphore S = 1; (이진 세마포어, 초기값 1)
wait(S); → 잠금 획득(S: 1→0)
[임계 구역 — 공유_변수++ 같은 코드는 여기서 한 번에 하나의 스레드만 실행]
signal(S); → 잠금 해제(S: 0→1)

6. 순서 동기화 — A 작업 후 B 작업

프로세스 A의 작업이 반드시 먼저 끝나야 프로세스 B가 시작해야 할 때는 초기값 0인 세마포어를 사용합니다.

semaphore S = 0; (초기값 0이 핵심)
프로세스 A: 작업_A_실행() 후 signal(S) → “나 끝났어!” (S: 0→1)
프로세스 B: wait(S) → S=0이면 대기 중… A가 signal 하면 → 작업_B_실행() (A가 끝나야 시작)

7. 뮤텍스 vs 세마포어 비교

뮤텍스는 값이 0 또는 1만 가능하고 잠근 스레드만 해제할 수 있으며 단일 자원 보호에 사용됩니다.
세마포어는 값이 0 이상의 정수이고 아무나 signal()을 호출할 수 있으며, 이진/카운팅 세마포어로 다수 자원 관리와 순서 동기화에 사용됩니다.

8. 세마포어 사용 시 주의사항
• 교착 상태(Deadlock): 두 프로세스가 서로 상대방의 signal을 기다림(예: A는 S1을 잠그고 S2를 대기, B는 S2를 잠그고 S1을 대기)
• 기아(Starvation): 특정 프로세스가 영원히 자원을 못 얻음(큐 우선순위 편향 문제)
• wait/signal 누락: signal()을 빠뜨리면 다른 프로세스가 영원히 대기하게 됨(버그의 주요 원인)

MFA(다중 요소 인증): 두 가지 이상의 인증 유형을 조합합니다. 예: 비밀번호(지식) + OTP(소유) → 훨씬 강력한 보안

4. 접근통제(Access Control) — DAC · MAC · RBAC
• DAC(임의적 접근통제): 권한 결정자는 객체 소유자. 소유자가 자유롭게 권한 부여·취소. 예: 리눅스 chmod, Windows NTFS ACL
• MAC(강제적 접근통제): 권한 결정자는 시스템(관리자). 보안 등급 기반으로 강제 적용, 소유자도 변경 불가. 예: 군사 보안, SELinux, Bell-LaPadula
• RBAC(역할 기반 접근통제): 권한 결정자는 역할(Role) 정의. 역할에 권한을 부여하고 사용자에게 역할을 할당. 예: Active Directory 그룹 정책
5. Bell-LaPadula 보안 모델

1973년 미국 국방부 후원으로 개발된 최초의 공식 MAC 보안 모델입니다. 기밀성(Confidentiality) 보호에 초점을 맞추며, 높은 등급의 정보가 낮은 등급으로 흘러내리는 것을 방지합니다.

• ss-Property(단순 보안 속성): No Read Up(위를 못 읽음). 낮은 등급 사용자는 높은 등급 문서를 읽을 수 없음(예: 일반 직원은 기밀문서 읽기 불가)
• *-Property(스타 속성): No Write Down(아래에 못 씀). 높은 등급 사용자는 낮은 등급 문서에 쓸 수 없음(예: 기밀 정보를 공개 문서에 복사 불가)
6. 보안 커널과 TCB
• TCB(Trusted Computing Base): 시스템 내 모든 보호 메커니즘의 총체. 보안 정책 적용에 책임이 있는 구성 요소 집합
• 참조 모니터(Reference Monitor): 모든 접근을 중재하는 개념. 격리성·검증가능성·완전성의 3가지 특성 필요
• TPM(Trusted Platform Module): 하드웨어 칩. 부팅 무결성 검증, 디스크 암호화 키 보호(BitLocker와 연동)
7. 악성 소프트웨어(Malware) 종류
• 바이러스(Virus): 정상 파일에 코드 삽입, 실행 시 복제. 파일 손상, 시스템 오류
• 웜(Worm): 네트워크를 통해 스스로 전파, 숙주 불필요. 네트워크 마비, 시스템 과부하
• 트로이 목마(Trojan Horse): 정상 프로그램처럼 위장, 악성 기능 숨김. 백도어 설치, 정보 탈취
• 랜섬웨어(Ransomware): 파일을 암호화하고 복구 대가로 금전 요구. 데이터 손실, 금전 피해
• 스파이웨어(Spyware): 사용자 몰래 정보 수집·전송. 개인정보 유출, 크리덴셜 탈취
• 루트킷(Rootkit): OS 핵심부에 숨어 자신을 은폐. 탐지 어려움, 장기 잠복