os_algorithm

운영체제 수업에서 다룬 핵심 알고리즘을 C++로 직접 구현한 저장소입니다. CPU 스케줄링, 교착상태 회피, 페이지 교체, 메모리 배치 네 가지 주제를 다룹니다.

모든 프로그램은 표준 입력으로 데이터를 받아 표준 출력으로 결과를 내보내는 콘솔 프로그램이며, 외부 라이브러리 의존성이 없습니다.

빌드 및 실행

g++ -std=c++17 -O2 -o fcfs fcfs.cpp
./fcfs < input.txt

Windows(MinGW)에서는 다음과 같이 실행합니다.

g++ -std=c++17 -O2 -o fcfs.exe fcfs.cpp
fcfs.exe < input.txt

구현 목록

파일	주제	내용
fcfs.cpp	CPU 스케줄링	FCFS (비선점)
sjf.cpp	CPU 스케줄링	SJF (비선점)
srtf.cpp	CPU 스케줄링	SRTF (선점)
bankers.cpp	교착상태	은행원 알고리즘 + 대기 큐
page.cpp	가상 메모리	FIFO / LRU / OPT 페이지 교체
memory_allocation.cpp	메모리 배치	First / Best / Worst Fit

---

1. CPU 스케줄링 — fcfs.cpp, sjf.cpp, srtf.cpp

세 프로그램은 입출력 형식이 동일해 같은 입력으로 결과를 비교할 수 있습니다.

입력

n
pid arrival burst
... (n줄)

출력 — 전체 프로세스의 대기시간 합

알고리즘별 차이

• FCFS: 도착 순서대로 처리합니다. 도착시각이 같으면 pid가 작은 쪽을 먼저 실행합니다. 구현이 가장 단순하지만, 긴 작업이 앞에 오면 뒤의 짧은 작업들이 모두 밀리는 호위 효과(convoy effect) 가 발생합니다.
• SJF: 현재 시각까지 도착한 프로세스 중 실행시간이 가장 짧은 것을 고릅니다. 한 번 실행하면 끝날 때까지 선점하지 않습니다. 동률일 때는 실행시간 → 도착시각 → pid 순으로 비교합니다. 평균 대기시간이 최소가 되지만 긴 작업이 계속 밀리는 기아(starvation) 가 생길 수 있습니다.
• SRTF: SJF의 선점형 버전입니다. 1 시간 단위로 진행하면서 매 시점 남은 실행시간이 가장 짧은 프로세스를 고르므로, 더 짧은 작업이 도착하면 실행 중인 프로세스를 밀어냅니다. 대기시간은 완료시각에서 도착시각과 실행시간을 빼서 계산합니다.

입력 예시

3
0 0 8
1 1 4
2 2 2

2. 교착상태 회피 — bankers.cpp

자원을 할당하기 전에 안전 상태(safe state) 인지 먼저 검사하고, 안전하지 않으면 할당을 보류하는 은행원 알고리즘입니다.

입력

n m                  프로세스 수, 자원 종류 수
total[m]             자원별 전체 개수
maxNeed[n][m]        프로세스별 최대 요구량
allocation[n][m]     프로세스별 현재 할당량

이후 명령을 순서대로 처리합니다.

명령	형식	동작
요청	request pid r1 ... rm	안전하면 할당, 아니면 대기 큐로 보냄
반납	release pid r1 ... rm	자원을 회수하고 대기 큐를 재검사
종료	quit	프로그램 종료

출력 — 각 명령 처리 후의 available 벡터

동작 방식

• need = maxNeed - allocation, available = total - Σallocation 으로 시작합니다.
• 요청이 need를 넘거나 음수면 잘못된 요청으로 보고 무시합니다.
• 요청을 가상으로 반영한 뒤 안전성 검사를 통과하면 확정하고, 실패하면 되돌린 후 대기 큐에 넣습니다.
• 자원이 반납되면 대기 큐를 앞에서부터 다시 검사해 할당 가능한 요청을 처리합니다.

3. 페이지 교체 — page.cpp

하나의 참조 문자열에 대해 FIFO / LRU / OPT 세 알고리즘을 한 번에 시뮬레이션하고 결과를 비교합니다.

입력

frameLimit
pid page
...
-1 -1                입력 종료

출력 — 알고리즘마다 아래 형식을 반복

FIFO: <페이지 폴트 수>
<프레임번호> <pid> <page>
...

교체 기준

• FIFO: 가장 먼저 적재된 페이지(loadedAt)를 내보냅니다. 구현이 간단하지만 프레임을 늘렸는데 폴트가 늘어나는 Belady의 이상현상이 발생할 수 있습니다.
• LRU: 가장 오래 참조되지 않은 페이지(lastUsedAt)를 내보냅니다. 과거 참조 기록을 근거로 하므로 실제 시스템에서 널리 쓰입니다.
• OPT: 앞으로 가장 늦게 참조될 페이지를 내보냅니다. 미래를 알아야 하므로 실제 구현은 불가능하지만, 다른 알고리즘의 성능을 평가하는 이론적 하한선입니다.

4. 메모리 배치 — memory_allocation.cpp

전체 메모리 크기 1000 을 기준으로, 시간에 따라 프로세스가 들어오고 나가는 상황에서 세 가지 배치 전략을 비교합니다.

입력

n
requestTime runTime size
... (n줄)

출력 — First Fit / Best Fit / Worst Fit 순서로 각 한 줄씩, 마지막 프로세스(pid = n-1)가 할당받은 시작 주소

배치 전략

• First Fit: 요구 크기를 만족하는 첫 번째 빈 공간에 넣습니다. 탐색이 가장 빠릅니다.
• Best Fit: 들어갈 수 있는 공간 중 가장 작은 곳에 넣습니다. 큰 공간을 아끼는 대신 쓸모없이 작은 조각이 많이 남습니다.
• Worst Fit: 가장 큰 공간에 넣습니다. 남는 조각을 크게 유지하려는 전략입니다.

빈 공간을 찾지 못한 프로세스는 대기 큐에 들어가고, 다른 프로세스가 종료되어 공간이 생기면 다시 할당을 시도합니다. 인접한 빈 공간은 병합해 외부 단편화를 줄입니다.