레지전트 셋이란, 메모리에 들어와있는 프로세스 페이지 정보들의 집합을 말한다. 또한 페이지의 갯수를 레지던트 셋 사이즈라 하는데, 이 사이즈를 규정하는 서로 다른 방법에 대해 알아보려 한다.
Process Resident Set
레지던트 셋 사이즈를 결정하는 기준
- Fixed allocation : 할당해주는 메모리 프레임의 수를 고정시킨다. 페이지 폴트가 발생하여 제거될 페이지를 선별해야 할 때, 자신이 갖고 있는 페이지 중에서 선택하는 Local Scope 영역에서 Replacement가 처리된다.
- Variable allocation : 할당해주는 메모리 프레임의 수를 유동적으로 결정한다. 해당 방법은 Replacement 처리 시 Local Scope와 Global Scope 영역 모두에서 사용된다.
Global Scope 처리 시 컴퓨터 메인 메모리 내의 모든 프로세스 페이지를 대상으로 한다. 해당 페이지에서 페이지 폴트가 발생하여 다른 페이지를 끌어오게 되면 셋 사이즈가 자동으로 늘어나며, 무수히 늘어나는 것을 방지하기 위해 적정 상한선을 유지하는 Page-Fault Frequency Scheme가 존재한다. 모든 프로세스가 공평한 성능을 낼 수 있게 유지하기 위하여 특정 프로세스가 페이지 폴트를 적게 당할 때는 메모리를 뺏기도 한다.
Process Scheduling
단일 CPU 컴퓨터에서 여러 프로세서들이 실행 순서를 결정하는 스케줄링 방식을 알아보자.
스케줄링 방식
- Long-term Scheduling : 생성은 되었지만 아직 메인메모리에 들어오지 않은(보조기억장치에서 가상 주소 공간에 저장되어 있는) Batch jobs 공간 내부의 new 상태의 프로세스들 중 ready 상태로 보낼 프로세스를 선택하는 스케줄링 방식이다. 모든 프로세스가 Batch jobs 공간에 들어가는 것은 아닌데 웹브라우저, 워드프로세스 같은 즉각적인 상호작용이 필요한 프로그램들은 new 상태를 건너뛰고 Ready queue에 추가된다. (new -> ready)
- Mid-term Scheduling : ready 상태로 존재하다 잠시 보조기억장치로 밀려나간 Suspended ready 상태에 존재하는 프로세스들을 다시 메인 메모리로 가져올 때의 스케줄링 방식이다. Suspended ready 뿐만 아니라 블록 상태에서 스왑 아웃 당한 프로세스들도 해당 방식을 통해 스케줄링한다. (Suspended ready / Suspended block -> ready / block)
- Short-term Scheduling : ready 상태의 프로세스들을 running 상태로 가져올 때 사용되는 스케줄링 방식. 앞에서 학습할 때 배운 스케줄링은 일반적으로 해당 방식을 말한다. (ready -> running)
Short-term Scheduling은 운영체제 내부에서 가장 빈번히 처리되는 스케줄링 방식이다. ready 상태의 프로세스를 ready queue에 집어넣는 일을 처리하며, 들어온 프로세스가 현재 CPU에서 처리 중인 프로세스보다 우선순위가 높은지 비교한다.
스케줄링 알고리즘
알고리즘 성능 기준치
- CPU Utilization : 전체 CPU 동작 시간에 비해 사용자 프로그램 실행에 투입된 시간의 비율
- Throughput : 단위시간당 실행이 끝난 프로그램의 수
- Turnaround Time : 프로세스 생성 후 끝날 때까지 걸리는 시간
- Response Time : 사용자 명령 입력 후 컴퓨터가 반응할 때까지의 시간
- Waiting Time : Ready queue에서 기다리는 시간의 총합. 레디 상태의 프로세스들만 스케줄링 대상이 될 수 있기 때문.
알고리즘 종류
- Priorities (우선순위 기반 스케줄링 알고리즘) : 준비 상태의 프로세스들 중, PCB에 기록된 우선순위 값을 보고서 제일 높은 것을 선택하는 방법. queue에서 후순위에 위치하더라도 우선순위를 따져 CPU에게 Dispatch한다. queue를 순회하는 과정에서 운영체제에 부하가 올 수 있기 때문에, 우선순위 등급별로 Ready queue를 두는 방법을 사용하기도 한다. 우선순위가 낮은 프로세스라면 무한정 대기해야 하는 Starvation 문제가 발생할 수도 있기 때문에, 이러한 프로세스는 동적으로 우선순위를 변화시켜준다.
- FIFO (선입선출 스케줄링 알고리즘) : 도착한 순서대로 스케줄링 처리. 대기 시간 증가될 수 있어 그리 효율적인 방식은 아님.
- Round Robin : 타임 쉐어링 시스템에서 사용되는 스케줄링 방법. 응답시간을 균등하게 부여하여 프로세스들을 처리한다. 스케줄링 간 이루어지는 컨텍스트 스위치로 인해 중단되는 당시의 정보를 PCB에 가져다 복원하여 연이어 실행. Response Time 성능이 우수하다.
보통 복수의 알고리즘을 혼합하여 사용한다. 사용자 관점(Ex. 빠른 반응 시간)에서의 성능과 시스템 관점(Ex. CPU 활용도 증가)에서의 성능이 같지 않기 때문이다. 아래의 알고리즘들이 그 예시이다.
Shortest Process Nest (SPN) 알고리즘
SPN 알고리즘은 Ready queue에 들어있는 프로세스들 중 실행 시간, 즉 서비스 타임이 가장 짧은 프로세스들을 골라 실행시키는 알고리즘이다. 실행 시간이 짧은 정도로 우선순위를 나누어 처리할 프로세스를 선택한다.
Shortest Remaining Time First 알고리즘
남은 시간이 제일 짧은 프로세스를 스케줄링 대상으로 선택하는 알고리즘으로, SPN과 유사하지만 Preemptive한 특성이 있다. 따라서 CPU를 사용 중인 프로세스의 자원을 뺏어올 수 있게 된다. 빨리 끝날 프로세스는 빨리 처리하자는 의미인데, 똑같이 Stavation이 발생할 수도 있을 듯 하다.
Feedback 알고리즘
여러 계층의 Ready queue를 통해 타임슬라이스를 차등 할당하는 방식이다. 처음에는 짧은 시간을 할당해주었다가, 갈수록 긴 시간을 할당해준다. 결국 가장 아래층에 남은 프로세스는 FIFO 혹은 Round Robin 알고리즘을 적용시키는데, 이 때문에 무한정 대기하는 Starvation을 방지할 수 있다.
