11. 프로그래밍 언어 활용 - 메모리관리기법(2)

 

 

 

[목차]

 

 

1. 페이지 교체 알고리즘

2. 기출 및 기출 예상 문제 풀이

3. 디스크 스케줄링 (보조기억장치)

4. 기출 및 기출 예상 문제 풀이

 

 

 

---

 

 

[페이지 교체 알고리즘]

 

 

1. 페이지 교체(Replacement) 알고리즘

 

1-1) 정의

: 페이제 부재(page fault)가 발생하였을 경우, 가상기억장치(보조기억장치)의 필요한 페이지를

주기억장치의 어떤 페이지 프레임으로 선택, 교체해야 하는가를 결정하는 기법

 

1-2) 종류

: OPT (OPTimal replacement, 최적교체), FIFO (First In First Out), LRU (Least Recently Used),

LFU (Least Frequently Used), NUR(Not Used Recently)

 

 

2. FIFO (First In First Out)

: 가장 먼저 들여온 페이지를 먼저 교체시키는 방법 (주기억장치 내에 가장 오래 있었던 페이지를 교체)

 

: 벨레이디의 모순 (Belady's Anomaly) 현상

- 페이지 프레임 수가 증가하면 페이지 부재가 더 증가

 

 

3. OPT (OPTimal replacement) 최적교체

: 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법으로 실현 가능성이 없다.

 

 

4. LRU (Least Recently Used)

: 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

: 각 페이지마다 계수기를 두어 현 시점에서 볼 때 가장 오래 전에 사용된 페이지를 교체

 

 

5. LFU (Least Frequently Used)

: 사용 횟수가 가장 적은 페이지를 교체하는 기법

 

 

6. NUR (Not Used Recently)

: 최근에 사용하지 않은 페이지를 교체하는 기법

: "근래에 쓰이지 않은 페이지들은 가까운 미래에도 쓰이지 않을 가능성이 높다" 라는 이론에 근거

: 각 페이지마다 2개의 하드웨어 비트(호출비트, 변형비트)가 사용됨

: 가장 우선적으로 교체 대상 - 참조도 안되고 변형도 안된 페이지

 

 

 

---

 

 

[기출 및 기출 예상 문제 풀이]

 

 

 

최근에 사용하지 않았다, 참조(호출)비트/변형비트 = NUR (Not Used Recently)

: 최근에 참조도 안되고(0) 변형도 안된(0) 페이지가 교체순위 1순위 > 가장 나중은 1,1

 

가장 오랫동안 사용하지 않았다, 계수기/스택 = LRU (Least Recently Used)

: 가장 오래된 페이지 교체, 최근 최소 사용!

 

 

참조된 횟수가 가장 적다 - LFU (Least Frequently Used)

 

 

---

 

 

 

 

[디스크 스케줄링(보조기억장치)]

 

 

1. 디스크 스케줄링(보조기억장치)

1-1) 정의

: 사용할 데이터가 디스크상의 여러 곳에 저장되어 있을 경우,

데이터를 액세스하기 위해 디스크 헤드가 움직이는 경로를 결정하는 기법

 

1-2) 목적

: 처리량의 최대화, 응답시간의 최소화, 응답시간 편차의 최소화

 

1-3) 종류

: FCFS, SSTF, SCAN, C-SCAN 기법 등

 

 

2. FCFS (First-Come First-Service)

: 입출력 요청 대기 큐에 들어온 순서대로 서비스를 하는 방법

 

 

3. SSTF (Shortes Seek Time First)

: FCFS 보다 처리량이 많고 평균 응답 시간이 짧다.

: 탐색 거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법

: 디스크 스케줄링 기법 중에서 현재 헤드 위치의 가까운 곳에 있는 모든 요구를 먼 곳보다 먼저 처리

: 탐색 시간 편차 큼 : 안쪽이나 바깥쪽 트랙이 가운데 트랙보다 서비스를 덜 받는 경향

- 헤드에서 멀리 떨어진 요청은 기아상태(starvation)가 발생할 수 있다.

- 응답시간의 편차가 크므로 대화형 시스템에는 부적합

: 처리량이 많은 일괄처리 시스템에 유용

 

4. SCAN (한 방향으로 가장 짧은 거리)

: SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법

: 현재 진행중인 방향으로 가장 짧은 탐색 거리에 있는 요청을 먼저 서비스

: 현재 헤드의 위치에서 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라

그 방향의 모든 요청을 서비스하고, 끝까지 이동한 후 역방향의 요청 사항을 서비스함

- 끝까지 이동하지 않을 경우(LOOK 기법)

: 디스크 스케줄링 기본 전략

 

 

 

5. C-SCAN (Circular SCAN)

: 무조건 바깥쪽에서 안쪽 가장 짧은 거리로 이동

: 항상 바깥쪽에서 안쪽으로 움직이면서 가장 짧은 탐색서리를 갖는 요청을 서비스

: 디스크 스케줄링 기법 중 가장 안쪽과 가장 바깥쪽의 실린더에 대한 차별대우를 없앤 기법

: 헤드는 트랙의 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 서비스하여 끝까지 이동한 후,

안쪽에 더 이상의 요청이 없으면 헤드는 가장 바깥쪽의 끝으로 이동한 후 다시 안쪽으로 이동하면서

요청을 서비스함

- 끝까지 이동하지 않을 경우 (C-LOOK 기법)

 

 

6. N-step SCAN

: SCAN의 무한 대기 발생 가능성을 제거한 것으로 SCAN보다 응답 시간의 편차가 적고,

SCAN과 같이 진행 방향상의 요청을 서비스 하지만, 진행 중에 새로이 추가된 요청은 서비스하지

않고 다음 진행시에 서비스하는 디스크 스케줄링

 

  

---

 

 

[기출 및 기출 예상 문제 풀이]

 

 

탐색 거리가 가장 짧다 = SSTF (Shortest Seek Time First)

항상 바깥쪽에서 안쪽으로 이동 = C-SCAN

무한대기 발생 가능성 제거, 진행 중 추가된 요청은 서비스 안한다 = N-step SCAN

한방향으로 짧은거리 = SCAN (도중에 방향 못 바꿈)

들어온 요청대로 처리 = FCFS

 

 

디스크 스케줄링은 처리량, 시간적인 부분과 관계가 있지 공간, 용량등과는 관계없음

 

 

 

출처: 유튜브 기사퍼스트 권우석

https://www.youtube.com/watch?v=gFprlxTkqFI&list=PLz95GL3y9Hv1pC1yOWBV1yqHxi4jEOKez&index=40