[정보처리기사]기억장치 관리

기억장치 배치 전략

• 최초 적합(First Fit) : 가능한 영역 중에서 첫 번째 분할 영역에 배치시키는 방법
• 최적 적합(Best Fit) : 가능한 영역 중에서 단편화를 가장 작게 남기는 분할 영역에 배치하는 방법
• 최악 적합(Worst Fit) : 가능한 영역 중에서 단편화를 가장 많이 남기는 분할 영역에 배치하는 방법

영역번호	영역크기	상태
1	5K	공백
2	14K	공백
3	10K	사용중
4	12K	공백
5	16K	공백

배치 전략 중 10K 프로그램이 할당 받는 영역의 번호는 다음과 같다.

• 최초 적합(First Fit) : 10K 프로그램이 들어갈 수 있는 첫 번째 영역은 2번이다.
• 최적 적합(Best Fit) : 10K 프로그램이 들어가고 단편화를 가장 작게 남기는 영역은 4번이다.
• 최악 적합(Worst Fit) : 10K 프로그램이 들어가고 단편화를 가장 많이 남기는 영역은 5번이다.

---

가상기억장치 구현

• 보조기억장치(하드디스크)의 일부를 주기억장치처럼 사용하는 것으로 가상기억장치에 저장된 프로그램을 실행하려면 가상기억장치의 주소를 주기억장치의 주소로 바꾸눈 주소 변환 작업(매핑)이 필요하다.
• 페이징 기법 : 프로그램을 동일한 크기로 나눈 단위를 페이지라 하며 이 페이지를 블록으로 활용하는 기법

• 세그먼테이션 기법 : 프로그램을 가변적인 크기로 나눈 단위를 세그먼트라 하며, 이 세그먼트를 블록으로 사용하는 기법

• 내부 단변화 : 프로그램이 할당된 후 남는 빈 공간, 영역 크기 16K > 프로그램 크기 14K 인 경우 내부 단편화 2K 발생
• 외부 단편화 : 영역 크기보다 프로그램 크기가 커서 할당되지 않아 남는 빈 공간, 영억 크기 12K < 프로그램 크기 14K 인 경우 외부 단편화 12K 발생

페이징 기법

• 페이지 : 프로그램을 일정한 크기로 나눈 단위(일반적으로 1~4KB)
• 프레임 : 페이지 크기로 일정하게 나누어진 주기억장치 단위
• 주소 변환을 위해서 페이지의 위치 정보를 가지고 있는 페이지 맵 테이블이 필요하다.
• 외부 단편화는 발생하지 않지만 내부 단편화는 발생할 수 있다.
• 장점 : 여러 개의 프로그램을 동시 실행할 수 있어 다중 프로그래밍 정도가 향상된다.
• 단점 : 주소 변환 과정에서 CPU 사용시간이 낭비되고 내부 단편화 문제가 발생한다.

세그먼테이션 기법

• 세그먼트 : 사용자 주소 공간을 논리적인 단위로 나눈 것, 각 세그먼트는 고유한 이름과 크기를 가진다.
• 주소 변환을 위해 세그먼트가 존재하는 위치 정보를 가지고 있는 세그먼트 맵 테이블이 필요하다.
• 장점 : 외부단편화에 의한 기억장치 낭비를 줄일 수 있다.
• 단점 : 세그먼트 크기가 가변적이기 때문에 세그먼트 영역이 다른 세그먼트 영역을 침범하지 않는 기억장치 보호키가 필요하다.

---

페이지 교체 알고리즘

• 페이지 부재가 발생했을 때 가상기억장치의 필요한 페이지를 주기억장치에 적재하는 데 어떤 프레임을 선택해 교체할 지 결정하는 기법

FIFO(First In First Out)

• 가장 오래 있었던 페이지를 고체하는 기법이다.
• 벨레이디의 모순 현상이 발생한다.(프레임 수가 늘어나면 페이지 부재 수가 줄어들지 않는 현상)

참조 페이지	1	2	3	4	1	2	5	1	2	3	4	5
Frame 1	1	1	1	4	4	4	5	5	5	5	5	5
Frame 2		2	2	2	1	1	1	1	1	3	3	3
Frame 3			3	3	3	2	2	2	2	2	4	4
페이지 부재	O	O	O	O	O	O	O			O	O

• 위 경우 페이지 부재가 총 9번 발생한다.
• 하지만, Frame 개수가 4개로 늘어나도 페이지 부재는 10번으로 증가한다. => 벨레이디 모순 현상

LRU(Least Recently Used)

• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 계수기나 스택같은 별로 하드웨어가 필요하며 시간적인 오버헤드가 발생하고, 실제로 구현하기 어렵다.

참조 페이지	2	3	2	1	5	2	3	5
Frame 1	2	2	2	2	2	2	2	2
Frame 2		3	3	3	5	5	5	5
Frame 3				1	1	1	3	3
페이지 부재	O	O		O	O		O

LFU(Least Frequently Used)

• 사용 빈도가 가장 적은 페이지를 교체하는 기법
• 활발하게 사용되는 페이지는 사용 횟수가 많아 교체되지 않고 사용된다.
• 초기에 많이 사용된 페이지가 그 후루도 사용되지 않을 경우 프레임을 계속 차지할 수 있다.

참조 페이지	2	3	1	3	1	2	4	5
Frame 1	2	2	2	2	2	2	2	2
Frame 2		3	3	3	3	3	3	3
Frame 3			1	1	1	1	1	1
Frame 4							4	5
페이지 부재	O	O	O				O	O

---

가상기억창치 관리

1. 페이지 크기
   • 페이지 크기가 작을 경우
     • 페이지 단편화가 가모되고 볼필요한 내용이 주기억장치에 적재될 확률이 적다.
     • 페이지 정보를 가지는 페이지 맵 테이블 크기가 커지고 매핑 속도가 늦어진다.
     • 디스크 접근 횟수가 많아져 전체적인 입출력 시간이 증가한다.
   • 페이지 크기가 클 경우
     • 페이지 정보를 갖는 맵 테이블의 크기가 작아지고, 매핑 속도가 빨라진다.
     • 디스크 접근 횟수가 줄어들어 전체적인 입출력 시간이 감소한다.
     • 페이지 단편화가 증가되고, 한 개의 페이지를 주기억장치로 이동하는 시간이 늘어난다.
2. 구역성(Locality)
   • 어느 순간 특정 페이지만 집중적으로 참조하는 것
   • 시간 구역성
     • 하나의 페이지를 일정 시간 동안 집중적으로 엑세스하는 현상
     • 한번 참조한 페이지는 가까운 시간 내에 계속 참조할 가능성이 높다.
   • 공간 구역성
     • 어느 하나의 페이지를 참조하면 그 근처의 페이지를 참조할 가능성이 높다.
     • 프로세스 실행 시 일정 위치의 페이지를 집중적으로 액세스하는 현상
3. 워킹 셋(Working Set)
   • 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합
   • 자주 참조되는 워킹 셋을 주기억장치에 상주시킴으로써 페이지 부재 및 교체 현상이 줄어들어 사용이 안정화된다.
4. 스레싱(Thrashing)
   • 프로세스 처리 시간보다 페이지 교체에 소요되는 시간이 더 많아지는 현상
   • 어떤 프로세스가 실제로 사용하는 프레임 수만큼의 프레임을 갖지 못한 경우 발생
   • 방지 방법 : 다중 프로그래밍 정도 완화, Working Set 이용
   • cf) 다중 프로그래밍 정도 : 얼마나 많은 프로그램을 동시에 수행하는 정도

---

디스크 스케줄링

• 사용할 데이터가 디스크 상의 여러 곳에 저장되어 있을 경우 디스크 헤드가 움직으는 경로를 결정하는 기법
• 목적 : 처리량 최대화, 응답 시간 최소화, 응답 시간 편차의 최소화

FCFS(First Come First Service)

• 디스크 대기 큐에 가장 먼저 들어온 트랙에 대한 요청을 먼저 서비스하는 기법
• 더 높은 우선순위의 요청이 입력되어도 순사가 바뀌지 않아 공평성이 보장된다.
• 디스크 오버헤드가 적을 때 효율적이며, 오버헤드가 커지면 응답 시간이 길어진다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67

SSTF(Shortest Seek Time First)

• 탐색 거리가 가장 짧은 트랙에 대한 요청을 먼저 서비스하는 기법
• 현재 헤드 위치에서 가장 가까운 거리에 있는 트랙으로 헤드를 이동한다.
• 현재 헤드 위치에 가장 가까운 트랙에 대한 요청이 계속 발생하는 경우 먼 거리의 서비스는 무한정 기다리는 기아 상태가 발생할 수 있다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183

SCAN

• SSTF가 갖는 탐색 시간의 편차를 해소하기 위한 기법
• 현재 헤드 위치에서 진행 방향이 결정되면 탐색 거리가 짧은 순서에 따라 그 방향의 모든 요청을 서비스 후 역방향의 요청 사항을 서비스한다.
• 오버헤드가 적을 경우 가장 효율적인 기법이다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183 -> 199 -> 37 -> 14

C-SCAN(Circular SCAN)

• 항상 바깥쪽에서 안쪽으로 한 방향으로만 움직이며 가장 짧은 탐색 거리를 갖는 요청을 서비스하는 기법
• 처음가 마지막을 인접시킨 것과 같은 원형 형태로 디스크를 처리한다.
• 디스크 대기 큐 : 53,98,183,37,122,14,124,65,67
• 이동 순서 : 53 -> 37 -> 14 -> 0 -> 199 -> 183 -> 124 -> 122 -> 98 -> 67 -> 65