[CS] 운영체제 자원 관리 알고리즘

1. 페이지 교체 알고리즘

페이지 교체 알고리즘은 운영체제의 가상 메모리 관리에서 중요한 역할을 합니다.

메모리가 가득 찼을 때 어떤 페이지를 교체할지 결정하는 알고리즘으로, 페이지 폴트(Page Fault)를 최소화하는 것이 중요합니다.

구분	FIFO	LRU	LIFO
설명	가장 먼저 들어온 데이터를 가장 먼저 제거	가장 오래 사용되지 않은 데이터를 제거	가장 마지막에 들어온 데이터를 가장 먼저 제거
기본원리	큐(Queue) 구조 기반	최근 사용 시간 추적	스택(Stack) 구조 기반
교체 우선순위	가장 오래된 항목	가장 오랫동안 접근되지 않은 항목	가장 최근에 추가된 항목
장점	구현이 단순	효율적 캐시 관리	구현이 단순
단점	최근 자주 사용하는 항목이 제거될 수 있음	구현 복잡도와 자원 소모 증가	성능 효율이 떨어질 수 있음
캐시 효율성	보통	높음	낮음

 

 

 

 

페이지 교체 알고리즘이 중요한 이유는 메모리 관리 효율성에 직접적인 영향을 주기 때문입니다.

실제 시스템에서는 LRU와 같은 알고리즘이 많이 사용되지만, LRU는 가장 오랫동안 사용되지 않은 페이지를 추적하기 위해 복잡한 데이터 구조를 유지해야 하므로, 시스템 자원을 소모합니다. 그래서 구현 복잡성과 *오버헤드를 고려하여 수정된 형태로 적용되는 경우가 많습니다.

 

(*오버헤드는 특정 기능을 수행하는데 필요한 추가적인 자원이나, 간접적인 비용을 의미합니다.)

 

 

2. SRT 스케줄링 알고리즘

SRT 스케줄링은 SJF 알고리즘의 선점형 버전으로, 실행 중인 프로세스를 포함하여 남은 실행시간이 가장 짧은 프로세스를 선택하여 실행합니다. 새로운 프로세스의 실행 시간이 더 짧다면 현재 프로세스를 중단하고 새 프로세스를 실행합니다.

프로세스	도착시간	실행시간	완료시간	대기시간	평균 대기 시간
A	0	8	17	9	6.5
B	1	4	5	0
C	2	9	26	15
D	3	5	10	2

 

 

3. 라우팅 프로토콜 비교

RIP는 동적 라우팅 프로토콜 중 하나로 소규모 네트워크에서 활용됩니다.

거리 벡터 알고리즘을 사용하며, 홉 카운트 기반으로 결정됩니다. 즉, 거치는 라우터의 수를 기준으로 최적 경로를 결정합니다. 또한 유효기간이 있는데, 라우팅 정보는 180초 동안만 유효하며, 이후 업데이트가 없으면 해당 경로를 삭제 합니다.

 

OSPF는 가장 널리 사용되는 링크 상태 라우팅 프로토콜 입니다.

RIP의 단점을 해결하여, 새로운 기능을 지원하며, 최단 경로 탐색에 Dijkstra(다익스트라) 알고리즘을 사용합니다. 주로 대규모 네트워크에 사용되고 있습니다. 링크 상태를 실시간으로 반영하여, 최단 경로로 라우팅을 지원합니다.

 

BGP는 EGP를 대체하기 위해 만들어진 경로 벡터 프로토콜입니다. 인터넷 서비스 제공업체와 자율 시스템 간의 라우팅에 사용되는 프로토콜로, 데이터 패킷 전송을 위한 최적 경로 선택 기술을 사용합니다.