운영체제 12주차 정리 - 1

메모리의 재배치전략

---

기억 장치 관리

---

사용 방식

---

기억 장치 응용

---

주요 키

가상 기억 장치(Virtual Memory)
• 보조 기억 장치의 일부를 주기억장치 처럼 사용
• 프로그램 크기의 제약을 극복(단, 실행 속도↓)

가상 디스크(Virtual Disk)
• 주기억장치의 일부를 보조기억장치처럼 사용
• 램드라이브(RAM Drive)

인터리빙(Interleaving)
• 기억 장치의 연속된 위치를 서로 다른 뱅크로 구성
• 동시에 여러 개의 위치에 접근이 가능(속도↑)

DMA(Direct Memory Access)
• CPU를 거치지 않고 주변장치가 직접 주기억 장치에 접근
• 입출력 속도가 향상
• 사이클 스틸링(Cycle Stealing, 사이클 훔치기) 기법이 사용됨

---

기억 장치 분할

---

고정 분할(정적 분할) = 페이징, Page, Paging

- 비연속 메모리 할당 기법을 사용

- 프로세스 하나가 여러 개의 블록으로 나뉘어 메모리에 할당됨
• 페이지(page)의 크기는 모두 동일

가변 분할 = 동적 분할, Segment, Segmentation

- 비연속 메모리 할당 방법

- 프로세스를 동적의 크기를 갖는 여러 개의 세그먼트(Segmentation)로 나눔

- 세그먼트를 나눌 때, 프로그램을 구성하는 서브루틴(subroutine), 프로시저(procedure), 함수(function) 단위로 함
• 각 세그먼트는 기능을 수행하는 하나의 작은 프로그램으로 간주

스래싱 = Thrashing

- 프로세스 동작 중 페이지 부재(page fault)가 발생되어 이를 해결하는 과정에서 성능 저하가 발생되는 현상
- 페이지 교체작업이 많아지면 전반적으로 속도가 느려짐
- 스래싱이 많이 발생하면 페이지 오류율이 상승함

 

스래싱 방지

- 다중 프로그래밍의 정도를 낮춤 = 동시 실행 프로그램 수를 줄임
- CPU 이용률을 낮춤
- 페이지 부재율을 조절
- 자주 사용하는 페이지들을 주기억 장치에 미리 갖다 놓음 (Working Set, 작업 집합)

 

구역성(Locality)

- The Locality Principle (1960s, a.k.a. Denning’s Definition)( 전체 이름: Peter J. Denning *)
- 프로그램 실행 시 어느 한 순간에 특정 부문을 집중적으로 참조
- 최근 호출된 자료나 명령은 곧바로 다시 사용될 가능성이 높음
- 캐시 메모리 시스템의 이론적 근거가 됨
- 디스크에서 주기억장치에 페이지블록을 가져올 때, 이왕이면 앞으로 사용가능성이

높은 페이지들도 함께 가져오는게 좋음

 

- 종류: 시간(Temporal) vs 공간(Spatial) 구역성

작업 집합(Working Set)

- Denning*이 제안
- 원활한 프로세스 동작을 위한 주기억 장치에 유지되어야 할 페이지들의 집합
- 자주 참조되는 페이지의 집합을 주기억 장치에 미리 적재
- 페이지 부재(page fault) 최소화
- 워킹셋 W(t, w) = 시간 t(time)에서 시간 w(width)까지 참조된 페이지들의 집합

 

예: 
• 순차적 참조 페이지 :

 W(0, 13) = {1,2,3,4,5}

---

기억 장치 관리 전략

---

종류

반입 전략(Fetch Strategy)

• 보조기억장치 내 프로그램/데이터를 주기억 장치로 가져오는 시기 결정
• 종류: 요구((On-)demand) 반입, 예상(Anticipatory) 반입

배치 전략(Placement Strategy)

• 프로그램/데이터를 주기억 장치에 배치
• 종류: 최초(First Fit), 최적(Best Fit), 최악(Worst Fit)

교체(재배치) 전략(Replacement Strategy)

• 빈 공간 확보를 위해 제거할 프로그램/데이터를 선택
• 종류: 최적화(OPT), FIFO(FCFS), LRU, LFU, NUR, PFF 등

---

반입(Fetch) 전략

---

요구(Demand) 반입

- 요구가 있을 때마다 주기억 장치로 옮기는 방식
- 사용자 명령에 의한 응용 프로그램 실행

예상(Anticipatory) 반입

- 앞으로 요구될 데이터 또는 프로그램을 미리 주기억 장치에 적재
- 가상 기억장치 기법에서 주로 사용

- 자주 사용되는 것을 미리 가져다 놓음 = 워킹 셋(Working Set) 개념
- 앞으로 사용할 가능성이 높은 페이지를 미리 가져다 놓음 = 구역성(Locality)의 개념

- 예상 성공 = 성능 향상
- 예상 실패 = 오버 헤드(Overhead) 발생

---

교체(Replacement) 전략

---

OPT 전략 = OPTimal Replacement, 최적 재배치 전략

- 페이지 사용 횟수를 정확히 예측하여 교체
- Belady의 알고리즘
- 앞으로 가장 오랫동안 사용되지 않을 페이지와 교체 = 미래를 봄
- 실현 가능성이 희박 = 미래를 알 수 없기 때문
- 페이지 부재 횟수가 가장 적으므로 성공률(Hit rate)이 가장 큼

OPT 전략 동작 예

FIFO(First In First Out) 전략

- 적재된 페이지에 타임 스탬프를 적용
- 페이지 프레임내 가장 오래된 페이지를 교체
- 페이지 교체가 가장 많음 = 페이지 부재가 가장 많이 발생

FIFO 전략 동작 예

LRU(Least Recently Used) 전략

- 참조된 지 가장 오래된 페이지를 대체
• LRU : 참조 페이지 기준
• vs. FIFO: 페이지 프레임 기준

- 현시점에서 가장 오랫동안 사용하지 않은 페이지를 교체
- 각 페이지마다 계수기를 두어 사용하는 기법

 

LRU 전략 동작 예

LFU(Least Frequently Used) 전략

- 페이지 별 참조된 횟수를 기억
- 참조 횟수가 가장 적은 페이지를 교체

LFU 전략 동작 예

NUR(Not Used Recently) 전략

- 두 개의 비트(bit)로 페이지 사용 및 변형 상태를 관리
- 최근에 사용(참조)하지 않은 페이지를 우선 제거
- 일정한 시간 후 다시 초기화

 

값 예:

PFF(Page Fault Frequently)

- 자주 사용(참조)하는 페이지들을 주기억 장치에 미리 배치 = 페이지 폴트↓
- 워킹 셋의 내용들을 관찰하여 최근 자주 사용되지 않는 것을 교체

• LFU의 변형

Second Chance(FIFO의 2차 기회 부여)

- FIFO에서 가장 오래된 페이지를 제거하기 전에 한 번 기회를 더 줌
- 가장 오래된 페이지임을 알기 위해 LRU 계수기가 필요