정보처리기사 필기 공부중에 설명이 굉장히 빈약한 분야가 있어서 혼자 전전긍긍하며 이해를 한 개념이다.
이런 개념은 누군가를 알려주기위한 목적으로 쉽게 설명해줄 수 있다면 확실히 나의 지식이 된다.
내가 이해한 밑바닥 개념수준에서 위의 교체기법 알고리즘을 설명해보겠다.
(참고서는 수제비 정보처리기사 필기를 사용하고 있다.)
교체 기법 알고리즘에서는 이런 표가 보인다!!
| 참조 스트링 | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| 주기억 장치 상태 (페이지 프레임) |
||||||||||||
| 페이지 부재 (Page Fault) |
모든 문제를 이해하려면 그 틀이 뭔지 정확히 알아야 한다.
그렇다면 덜렁 주어진 이 표가 무엇을 의미하는지 정확히 알아야 문제를 풀 수 있다.
일단 위 표는 아래 제시에 따라 만들어진 표이다.
(제시)
1. 프로세스에 3개의 페이지 프레임이 고정으로 할당되어 있고, 초기에 3개의 페이지 프레임들이 모두 비어있다고 가정.
2. 참조할 스트링은 12개 (0 1 2 3 0 1 4 0 1 2 3 4)
그러므로
저 위 표의 주기억 장치 상태(페이지 프레임)에는 3개가 있고, 참조 스트링은 12개가 뚫려있는 것이다.
그리고 초기에 3개의 페이지 프레임들이 모두 비어있다고 가정되었으니, 저기에는 아무것도 적혀져 있지 않은 것이다.
만약에 초기 3개의 페이지 프레임에 0, 1, 2 이 있다고 가정을 한다면
| 참조 스트링 | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| 주기억 장치 상태 (페이지 프레임) |
0 | |||||||||||
| 1 | ||||||||||||
| 2 | ||||||||||||
| 페이지 부재 (Page Fault) |
위와 같이 표가 조성이 될 것이다.
이해가 되었는가??!
이해가 되었다면 아래로 넘어가자!!!
FIFO(First in First Out) 페이지교체 알고리즘 계산을 해보자!!
| 참조 스트링 | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| 주기억 장치 상태 (페이지 프레임) |
||||||||||||
| 페이지 부재 (Page Fault) |
위의 표가 이해가 되었다면, 이제는 이 표를 통해 알고리즘 계산을 해보자.
우리가 처음 해결할 문제는 FIFO 페이지교체 알고리즘을 통해 페이지 부재가 얼마나 발생하는지 알아보는 것이다.
문제 조성을 위해 제시된 가정은 아래와 같다.
(제시)
1. 프로세스에 3개의 페이지 프레임이 고정으로 할당되어 있고, 초기에 3개의 페이지 프레임들이 모두 비어있다고 가정.
2. 참조할 스트링은 12개 (0 1 2 3 0 1 4 0 1 2 3 4)
※ 우리는 메모리 관리 기법을 공부하고 있다는 점을 다시 상기하자.
그리고 메모리 관리 기법은 주기억 장치에서 프로세스를 좀 더 효율적으로 이용하기 위해 사용한다.
우리가 자주 쓰는 프로그램(프로세스)들은 메모리에 상주한다. 그 메모리에 상주하는 프로세스 관리방법을 알고리즘한 것을 우리는 배우고 있는 것이다!!
다시 문제로 돌아와서...
참조할 스트링은 위에 적혀져있고 스트링은 그대로 페이지 프레임의 첫번째 위치로 오게 된다.
여기서 우리가 공부할 알고리즘은 FIFO(First in First Out)이다. 먼저 들어왔던 것이 제일 처음에 나간다.
| 참조 스트링 | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| 주기억 장치 상태 (페이지 프레임) |
0 | |||||||||||
| 페이지 부재 (Page Fault) |
F |
설명대로 참조스트링을 아래로 내리니 페이지 부재(Page Fault)가 생겼다.
페이지 부재(Page Fault)는 페이지 프레임에 참조스트링이 없을 경우(페이지 내 스트링이 부재할 경우) 체크된다.
한마디로 보조기억장치(하드디스크)에는 프로세스가 저장되어있고, 주기억장치(RAM)로 프로세스를 불러와야 하는 것이다. 그럼 디스크가 돌아가야하니 시간이 좀 더 걸리게 된다.
(우리가 오랜만에 돌리는 문서나 게임의 경우에 하드가 우우이이이이잉 하면서 돌아간 적이 있을 것이다.
그러한 개념이지 않을까?)
이해가 되었다면 쭉쭉 가보자.
| 참조 스트링 | 0 | 1 | 2 | 3 | 0 | 1 | 4 | 0 | 1 | 2 | 3 | 4 |
| 주기억 장치 상태 (페이지 프레임) |
0 | 1 | 2 | 3 | 0 | 1 | 4 | 4 | 4 | 2 | 3 | 3 |
| 0 | 1 | 2 | 3 | 0 | 1 | 1 | 1 | 4 | 2 | 2 | ||
| 0 | 1 | 2 | 3 | 0 | 0 | 0 | 1 | 4 | 4 | |||
| 페이지 부재 (Page Fault) |
F | F | F | F | F | F | F | F | F |
FIFO 알고리즘의 표가 완성되었다.
새로 참조할 참조스트림이 페이지프레임에 없다면 새로 읽어서 페이지프레임에 넣는 것이 페이지 부재이다.
페이지 부재가 없는 칸의 경우에는 이미 페이지 프레임에 해당 스트링이 남아있어서 페이지 부재가 아니다.
이는 페이지 히트(Page hit)라고 표현한다.
이 개념을 바탕으로
알아볼 다음 알고리즘은 LRU(Least Recently Used), LFU(Least Frequently Used)이다.
LRU(Least Recently Used) 알고리즘
| 참조 스트링 | 2 | 3 | 2 | 1 | 5 | 2 | 3 | 5 |
| 주기억 장치 상태 (페이지 프레임) |
2 | 3 | 2 | 1 | 5 | 2 | 3 | 5 |
| 2 | 3 | 2 | 1 | 5 | 2 | 3 | ||
| 3 | 2 | 1 | 5 | 2 | ||||
| 페이지 부재 (Page Fault) |
F | F | F | F | F |
Least Recently Used는 최소 최근 사용이다.
사용된 시간을 확인하여 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.
참조 스트링을 자세히보면
페이지 히트였다 하더라도 가장 최근에 사용한 요소들의 페이지 프레임 상태가 바뀐다.
그리고 페이지 부재 상황에서는 가장 나중에 쓰인 페이지가 밀려나가면서 새로운 스트링이 페이지 프레임에 불려온다.
만약 이해가 가지 않는다면 위 FIFO에서 설명했던 표에 대한 이해 과정을 한번 더 읽고 LRU로 넘어오길 바란다.
LFU(Least Frequently Used) 알고리즘
| 참조 스트링 | 2 | 3 | 1 | 3 | 1 | 2 | 4 | 5 |
| 주기억 장치 상태 (페이지 프레임) |
2 | 3 | 1 | 1 | 1 | 1 | 4 | 5 |
| 2 | 3 | 3 | 3 | 3 | 1 | 1 | ||
| 2 | 2 | 2 | 2 | 3 | 3 | |||
| 주기억 페이지 | 2 | 2 | ||||||
| 페이지 부재 (Page Fault) |
F | F | F | F | F |
Least Frequently Used는 최소 빈도 사용이다.
이 표에서는 더 직관적인 이해를 위해 주기억 페이지를 하나 더 추가했다.
위의 스트링에서
참조 스트링 1은 2번씩, 참조 스트링 2도 2번씩, 참조 스트링 3도 2번씩 페이지 참조가 되었다.
그렇기때문에 4번이 새롭게 참조되며 페이지부재가 났을 때 2번은 주기억 페이지에서 살아남을 수 있었고
새로이 5번이 새롭게 참조될 때, 참조되었던 빈도가 1번뿐인 4번이 날아가며 5번이 들어오게 되었다.
궁금한 사항은 댓글 달아주시면
어떻게든 찾아서 답변을 드리겠다.
파이팅!!
'했던것들 > 정보처리기사' 카테고리의 다른 글
| [요점정리] 2022년 정보처리기사 필기 2과목. 소프트웨어 개발 (0) | 2022.04.21 |
|---|---|
| [요점정리] 2022년 정보처리기사 필기 1과목. 소프트웨어 설계 (0) | 2022.04.21 |
| 속성 C 언어 : 배열 사용하기 (0) | 2022.04.13 |
| 속성 C 언어 : 포인터 사용하기 (0) | 2022.04.13 |
| 속성 C언어 : break와 continue (0) | 2022.04.12 |
