[CS/운영체제] 스케줄링, 메모리 관리 정리

한정적인 자원의 CPU 탓에 여러 프로세스를 효율적으로 사용할 수 있도록 해야 한다.

 

그 방법이 바로 스케줄링 기법이다.

 

# 스케줄링의 주된 목적

1. 공평성: 모든 프로세스 공평하게 실행, 특정 프로세스가 실행되지 않는 경우가 없도록

2. 효율성 : 자원이 계속 사용될 수 있도록

3. 안정성 : 우선순위를 고려하여, 우선순위의 프로세스를 먼저 처리하도록

4. 반응 시간 보장 : 프로세스가 오랜 시간 응답이 없을 시, 사용자가 시스템이 멈춘 것으로 보기 때문에 일정 시간 내에 응답할 수 있도록

5. 무한 연기 방지 : 특정 프로세스에 대한 처리가 무한히 연기되지 않도록

 

프로세스 상태도(출처: 기술면접대비 CS전공 핵심요약집)

 

# 스케줄링의 단계

## 장기 스케줄링

잡 스케줄링 또는 승인 스케줄링이라고 칭함.

준비 큐에 어떤 프로세스를 넣을지 결정해 메모리에 올라가는 프로세스 수 조절

디스크에서 메모리를 얼마나 올릴지!

(생성 -> 준비)

 

## 중기 스케줄링

메모리에 로드된 프로세스 수를 동적으로 조절

메모리에 프로세스 수가 많다? -> 스왑 아웃 처리(중단 상태로)

준비 상태에서 스왑 아웃 : 중단된 준비 상태

대기 상태에서 스왑 아웃 : 중단된 대기 상태

(준비 또는 대기 상태에서 중단될 때, 메모리 <-> 저장 공간)

 

++

스왑 인이란? 스왑 아웃한 프로세스를 다시 실행하고자 할 때 메모리로 다시 올리는 것(재시작)

스와핑이란? 스왑 인과 스왑 아웃 통틀어 이르는 말.

 

## 단기 스케줄링

CPU 스케줄링이라고도 함.

준비 큐에 있는 대기 상태 프로세스 중 어떤 프로세스를 다음으로 실행할 지 스케줄링 알고리즘으로 결정

메모리에 있는 것들을 CPU로 갖다 놓는 역할

(준비 -> 실행)

스케줄리의 단계(출처: 기술면접대비 CS전공 핵심요약집)

스케줄러 관점에서 스케줄링(출처: 기술면접대비 CS전공 핵심요약집)

① 준비 큐에 있는 대기 상태의 프로세스 중 스케줄링 알고리즘을 이용하여 CPU에 디스패치함. (단기 스케줄링)

② 프로세스 수행이 완료되면 종료 | 일정 시간 초과 시, 인터럽트가 발생하여 다시 준비 큐로 이동| 입출력 요청 시, 입출력 수행이 완료될 때까지 대기 큐에서 대기, 완료되면 준비 큐로 들어감

③ fork() 호출 시, 자식 프로세스가 생성되고 자식 프로세스는 준비 큐로 들어감. 부모 프로세스는..?

=> 부모 프로세스는 자식 프로세스의 PID를 반환받고, 그 이후부터는 자식과 별도로 실행. 자식 프로세스가 준비 큐에 들어가는 동안, 부모 프로세스는 스케줄링에 따라 다시 실행 큐로 들어가거나 다른 작업을 수행한다. 결론, 독립적으로 움직인다!

 

# 스케줄링 알고리즘

단기 스케줄러가 준비 큐에 있는 프로세스 중 어떤 프로세스를 실행시킬지 결정하는데 사용

 

## 스케줄링 목적

1. CPU 사용률

2. 처리량 - 단위 시간 당 실행한 프로세스 수

3. 응답 시간 - 프로세스에 요청이 발생했을 때 응답까지 걸리는 시간

4. 반환 시간 - 프로세스가 로드된 이후부터 종료될 때까지 걸리는 시간

5. 대기 시간 - 프로세스가 대기 큐에서 대기하는 시간의 총합

 

## 비선점형 스케줄링(non-preemptive)

실행 중인 프로세스가 종료될 때까지 다른 프로세스 실행할 수 없음. (동기 비동기에서 동기와 같은 맥락)

 

### FCFS 스케줄링

먼저 들어온 사람이 승자!

준비 큐에 먼저 들어온 프로세스가 우선순위를 가짐.

 

### SJF(SJN) 스케줄링

제일 빨리 끝나는 사람이 승자!

실행 시간이 짧은 프로세스가 우선 순위 가짐. 

장점: 평균 대기 시간이 짧다.

단점: 실행 시간이 긴 프로세스는 기아 상태가 될 수 있다.(ㅠ.ㅠ)

 

++

기아 상태란? 프로세스마다 우선 순위가 있는데 우선순위가 높은 프로세스에게 밀려 계속해서 실행되지 못하는 것을 의미한다.

 

### HRRN 스케줄링

대기 시간이 가장 긴 작업에 우선 순위 부여

 

## 선점형 스케줄링(preemptive)

스케줄러가 실행 중인 프로세스를 중단 시키고 다른 프로세스를 실행할 수 있음(자네 그만하고 이리 나오시게)

 

### RR 스케줄링

공산주의 기법. Aka. 니코로빈 기법

일정 시간 동안(타임 퀀텀 | 타임 슬라이스) 실행. 일정 시간 초과할 시, 순서대로 다른 프로세스 실행.

장점: 모든 프로세스가 반복 수행되어 응답 속도 빠름.

단점: 콘텍스트 스위칭 빈번하게 일어나 오버헤드 큼.

 

### SRTF 스케줄링

대기(실행?) 시간이 가장 짧게 남은 프로세스가 우선 순위 가짐.

실행 시간이 더 짧은 프로세스가 준비 큐에 들어오면 실행 시간이 더 짧은 프로세스가 선점!

장점: 평균 대기 시간 짧음.(계속 비교하면서 바꾸니까)

단점: 수행 시간이 긴 프로세스는 기아 상태가 될 수 있음.

 

+++

SJF와 차이점?

=> 선점 vs 비선점 의 차이

=> 계속해서 시간을 비교하고 콘텍스트 스위칭을 하기 때문에 선점 기법인 SRTF가 오버헤드가 더 크다.

 

### 멀티 레벨 스케줄링

준비큐를 목적에 따라 여러 개로 분리해 사용.

분리한 큐는 각각의 우선 순위가 있고 다른 스케줄링 알고리즘 적용 가능.

foreground 큐와 background 큐로 나뉨.

foreground 큐: 응답 속도 중요한 프로세스

background 큐: 성능 중요한 프로세스

 

# 논리 메모리와 물리 메모리

논리(가상) 메모리 영역 : CPU가 프로세스를 처리할 때 보는 메모리 영역

물리 메모리 영역 : 실제로 사용되는 메모리 영역, RAM

논리 주소 | 가상 주소 : CPU가 프로세스를 처리할 때 보는 주소 값

물리 주소 : 실제 주소 값, 실제 메모리에서 사용되는 주소

 

CPU가 프로세스를 실행할 때 사용하는 주소 값(논리 주소)과 실제 주소 값(물리 주소)가 다르므로 논리 -> 물리 변환 작업을 해야 함.

=> 이런 변환 과정을 하는 하드웨어 장치를 메모리 관리 장치(MMU, Memory Management Unit)라고 한다.

MMU 작동 방식(출처: 기술면접대비 CS전공 핵심요약집)

 

# 연속 메모리 할당

멀티 프로세스 환경에서 여러 프로세스를 메모리에 연속적으로 로드

 

## 연속 메모리 할당 방식

### 고정 분할 방식

메모리 영역을 분할한 후, 각 영역에 프로세스 할당 (선 분할 후 할당)

분할된 크기는 서로 다를 수 있고 분할된 크기는 고정.

메모리에 올릴 수 있는 프로세스 수와 각 프로세스 크기가 제한 => 단편화(fragmentation) 발생

 

프로세스 크기와 분할된 메모리 크기가 안 맞는 경우(공간이 작으면) => 외부 단편화

프로세스 크기가 작아 분할된 메모리 공간이 남는 경우 => 내부 단편화

고정 분할 방식 예(출처: 기술면접대비 CS전공 핵심요약집)

### 가변 분할 방식

할당할 프로세스 크기에 맞게 메모리 공간을 분할하는 방식(할당 우선 후 분할)

메모리 할당 알고리즘(최초 적합, 최적 적합, 최악 적합)

 

최초 적합(first-fit)

공간 순서대로, 모두 탐색 X, 공간 찾으면 바로 할당(위에서 부터 탐색)

최초 적합 예(출처: 기술면접대비 CS전공 핵심요약집)

 

최적 적합(best-fit)

해당 프로세스를 수용 가능한 메모리 공간 중 가장 작은 것부터 할당(남는 공간을 최대한 줄이는 방식)

최적을 찾아야 하기 때문에 가용 메모리 공간을 모두 탐색해야 함!

최적 적합 예(출처: 기술면접대비 CS전공 핵심요약집)

 

최악 적합(worst-fit)

해당 프로세스를 수용 가능한 메모리 공간 중 가장 큰 것부터 할당(남는 공간을 최대한 만드는 방식)

최악을 찾아야 하기 때문에 가용 메모리 공간 모두 탐색해야 함!

공간 낭비 MAX, 효율X

최악 적합 예(출처: 기술면접대비 CS전공 핵심요약집)

 

++ 외부 단편화 문제 해결 방안 - 메모리 압축

이미 차있는 공간들을 한쪽으로 밀어넣어서 공간을 만들어낸다.

메모리 압축 예(출처: 기술면접대비 CS전공 핵심요약집)

# 비연속 메모리 할당

프로세스의 메모리 영역(논리, 물리)을 나눠서 메모리 공간에 저장

 

## 페이징(paging) 기법

프로세스의 논리 메모리와 물리 메모리를 각각 일정한 크기의 페이지(page)와 프레임(frame)으로 나눔.

페이지와 프레임 크기 동일, 각각 번호 할당(페이지 테이블에 맞는 번호끼리 페이지와 프레임 매핑)

페이지 테이블은 각 프로세스의 PCB에 저장

장점 : 외부 단편화 해결

단점 : 내부 단편화 발생할 수 있음, 페이지 테이블을 저장하기 위한 메모리 공간 추가 필요.

페이징 기법 예(출처: 기술면접대비 CS전공 핵심요약집)

계층적 페이징(멀티레벨 페이징) : 페이지 테이블을 다시 페이지로 나눠 페이지 테이블 자체를 페이징함. 
해시 페이지 테이블 : 해시 테이블의 각 항목에 저장된 연결 리스트에 페이지 번호를 해싱한 뒤에 첫 번째 요소와 가상 페이지 번호를 비교하는 방식
역 페이지 테이블 : 프레임을 이용해 페이지를 찾는 방식(페이지로 프레임 찾는 거랑 반대)

 

## 세그먼테이션 기법

프로세스의 메모리 영역을 논리적 단위인 세그먼트로 분할해 메모리를 할당

세그먼테이션 테이블 사용하여 논리 주소를 물리 주소로 매핑

세그먼트 테이블에서 세그먼트 번호를 인덱스로 사용.

물리 메모리에서의 시작 주소 -> base, 세그먼트 길이 -> limit

 

장점 : 단위별로 데이터 보호하기 쉬움

단점 : 세그먼트의 크기가 균등하지 않아 외부 단편화 발생, 오버플로 발생 시 둘 중 하나의 세그먼트를 스왑 아웃해야 함.

세그먼테이션 예(출처: 기술면접대비 CS전공 핵심요약집)