개발공부 기록지

페이지 프레임 할당 -> 물리적 메모리공간에 할당

페이징 ?

프로세스의 주소 공간을 미리 동일한 크기의 페이지 단위로 나누어 물리적 메모리의 서로 다른 위치에 페이지들을 저장하는 방식

할당 알고리즘 (allocation algorithm)

• 균등 할당(equal allocation) : 페이지 프레임을 균일하게 할당
• 비례 할당(proportional allocation) : 프로세스의 크기에 비례하게 할당
• 우선순위 할당(priority allocation) : 우선순위에 따라 페이지 프레임을 다르게 할당

고려해야할 사항

• 알고리즘 만으로는 페이지 참조 특성을 다 반영 못할 수 있는 경우
  • 실행 중인 프로세스가 너무 많아서 메모리 양이 과도하게 작아지는 경우 
    : 명령을 실행 할때 하나가 아니라 여러 페이지(코드, 데이터, 스택 등등) 를 동시에 참조 하기 때문
  • 반복문(loop)의 경우
    : 반복문을 구성하는 모든 프로세스를 한꺼번에 메모리에 올려놓는 것이 유리
    : 반복문을 구성하는 페이지의 수보다 적은 양의 프레임을 할당 -> 페이지 부재 발생
  • 프로세스에 필요한 최소한의 메모리양이 시간에 따라 다를 수 있는 경우 
    

페이지 교체 란

페이지 부재가 발생 하였을 때 물리적 메모리에 빈 공간이 없을 때 하나의 페이지를 스왑아웃하여 빈 공간을 확보하는 작업 

페이지 교체 알고리즘 

(목표) 페이지의 부재율을 최소화 -> 미래에 참조될 가능성이 가장 적은 페이지를 선택하여 스왑아웃 하는 방안을 모색

(페이지 교체의 예)

(성능) 주어긴 페이지 참조열 (page reference string)에 대해 부재율을 계산하여 평가

          (페이지 참조열 예시) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
                               참조되는 페이지들의 번호를 시간 순서에 따라 나열
                               해당 번호의 페이지가 이미 메모리에 올라와 있으면 메모리에서 적중(hit)
                               메모리에 없는 경우 페이지 부재 발생

1) 최적 페이지 교체

빌레디의 최적 알고리즘 (Belady's opitmal algorithm) 또는 MIN, OPT 로 불림

: 페이지 중 가장 먼 미래에 참조될 페이지를 쫓아내서 페이지 부재율을 최소화하는 알고리즘

: 미래에 어떤 페이지가 어떠한 순서로 참조될지 미리 알고 있다는 전제하에 운영 -> 오프라인 알고리즘

+ 알고리즘 중에 가장 적은 페이지 부재율을 보장
+ 한 시스템에서 새로운 알고리즘 설계시의 성능평가의 기준
- 실제 시스템에서는 사용 불가 

(작동원리 예시)

페이지 부재가 7번째에 발생 -> 미래에 일어날 페이지 순서 참조 -> 4 를 스왑아웃 하고 5를 적재

2) 선입선출(First In First Out :FIFO) 알고리즘

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는다.

- 비효율적인 상황이 발생 (페이지 부재 다수 발생)

메모리 공간이 늘어나도 성능은 오히려 너 나빠질수도 있다. -> FIFO의 이상 현상

3) LRU(Least Recently Used) 알고리즘

성능향상을 위해서는 향후 사용될 가능성이 낮은 페이지를 우선적으로 메모리에서 쫓아내는 것이 바람직

• 메모리 참조 성향 중 중요한 한가지 성질 => 시간지역성(temporal locality)
  • 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질

LRU 알고리즘은 시간지역성을 이용하여 마지막 참조 시점이 가장 오래된 페이지를 쫓아낸다.

4) LFU (Least Frequently Used) 알고리즘

메모리에있는 페이지 중 참조 횟수가 가장 적었던 페이지를 쫓아내는 알고리즘

• Incache-LFU : 메모리에 올라온 후 부터 참조 횟수를 카운트 
• Perfect-LFU : 메모리에 올라온 이력에 관계없이 해당 페이지가 과거에 참조 된 총 횟수 카운트
  + 페이지 참조 횟수를 정확히 반영
  - 모든 페이지의 참조 기록을 보관하여야 하므로 오버헤드 발생

5) 클럭 알고리즘(clock algorithm) / 2차 기회 알고리즘

NUR(Not Used Recently) 또는 NRU(NOT Recently Used) 알고리즘

하드웨어적인 지원을 통해 알고리즘의 운영에 시간적인 오버헤드를 줄인 방식

• 오랫동안 참조되지 않은 페이지 중 하나를 교체
• 하드웨어적인 지원으로 동작하여 LRU 보다 페이지의 관리가 빠르고 효율적
• 시곗바늘이 한 바퀴 도는 동안 다시 참조 되지 않은 페이지를 교체
• 페이지 부재율을 줄이도록 설계
• 작동원리
  • 프레임내의 페이지가 참조 되면 하드웨어가 자동으로 1로 셋팅
  • 시곗바늘이 참조비트가 1인 페이지를 지나면 0으로 셋팅
  • 시곗바늘이 참조비트가 0인 페이지를 지나면 교체 대상 페이지

프로세스를 구성하는 페이지 중에 당장  사용될 페이지만을 올리는 방식

특정 페이지에 대해 CPU의 요청이 들어온 후에야 해당 페이지를 메모리에 적재

요구 페이징 기법의 이점

+ 메모리 사용량 감소

+ 입출력 오버헤드 줄어듬

+ 시스템이 더 많은 프로세스를 수용 가능

+ 프로그램이 물리적 메모리의 용량 제약을 벗어나는 것이 가능

유효-무효 비트 (valid-invalid bit)

가상 메모리 기법에서 프로세스가 실행되는 동안
페이지들이 물리적 메모리와 스왑영역에 존재하는데

어떤 페이지가 물리적 메모리에 존재하는지 구별이 필요

=> 요구 페이징 기법에서는 유효-무효 비트를 페이지 테이블의 각 항목별로 저장

• 유효(v)
  메모리에 해당 페이지가 적재되어 있는 경우
• 무효 (i)
  해당 페이지가 스왑영역에 있는 경우,
  현재 메모리에 없는 경우,
  페이지가 속한 영역을 프로세스가 사용하지 않는 경우

1) 요구 페이징의 페이지 부재 처리

페이지 부재(page-falut)

CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아 유효-무효비트가 무효로 세팅되어 있는 경우

페이지 부재를 처리하는 과정

CPU가 무효 페이지에 접근
       -> MMU(주소 변환을 담당하는 하드웨어)가 페이지 부재 트랩 발생
       -> 운영체제의 페이지 부재 처리 루틴 호출
               -> 페이지에 대한 접근이 부 적법 (사용되지 않는 영역에 속한 페이지에 접근 / 해당 페이지에 대한 접근 권한 위반)
                       -> 프로세스 종료

               -> 페이지에 대한 접근이 적법
                       -> 물리적 메모리에 있는 빈 프레임을 할당받아 페이지를 읽어 해당 공간에 적재 

                       -> 빈 프레임이 없는 경우

                             -> 물리적 메모리에 올라와 있는 페이지 중 하나를 디스크에 내려 놓음 (스왑 아웃) 

즉, 부재 상태의 페이지를 메모리에 적재하기에  앞서 운영체제가 해당 페이지에 대한 접근이 적법한지 체크하는 과정

페이지 부재를 발생 시킨 프로세스 -> 봉쇄상태(디스크에서 파일을 다 읽어올때 까지 CPU를 반환)

   (이유) 해당 페이지를 디스크에서 물리적 메모리에 적재하기까지 시간이 오랜시간 소요 - CPU 가 필요없음, 오버헤드 발생

디스크에 요청한 입출력 작업이 완료-> 인터럽트 발생 -> 해당 페이지 테이블에서 유효 비트로 설정 -> 준비 큐에서 대기

2) 요구 페이징의 성능

요구 페이징의 성능에 가장 큰 영향을 미치는 것은 페이지 부재의 발생 수

(이유) 디스크에서 메모리에 적재하는 과정(스왑아웃 -> 스왑인 -> 문맥교환) 에서 오버헤드 발생

유효 접근시간이 짧을 수록 ( 페이지 부재의 발생수가 적을 수록) 
 -> 요구 페이징 기법의 성능은 향상

성능 평가 방법

• 유효 접근시간(effective access time)
  = (1- P) × 메모리 접근시간
       + P × ( 페이지 부재 발생 처리 오버헤드
                     + 메모리에 빈 프레임이 없는 경우 스왑 아웃 오버헤드
                     + 요청된 페이지의 스왑 인 오버헤드
                     + 프로세스의 재시작 오버헤드)
  • (1 - P) : 페이지 부재가 일어나지 않는 비율
• 페이지 부재 발생비율(page fault rate)   0 ≤ P ≤ 1
  P = 0 : 페이지 부재가 한 번도 일어나지 않은 경우  
  P = 1 :  모든 참조 요청에서 페이지 부재가 발생한 경우

프로그램이 CPU에서 실행이 되려면 실행에 당장 필요한 부분이 메모리에 올라와 있어야 함

하지만 메모리는 한정적이므로 프로그램이 나누어서 사용

따라서, 운영체제는 어느 프로그램에게 어느정도의 메모리를 할당할 것인가 하는 문제를 처리

• 운영체제의 메모리 할당 방식
  메모리는 몇몇 프로그램에게 집중적으로 메모리를 할당
  -> 메모리 회수 -> 다른 프로그램에게 집중적으로 할당

이유는 프로세스의 빠른 수행을 위해 확보해야하는  메모리의 크기가 존재하기 때문

• 운영체제가 물리적 메모리의 연장공간으로 사용하는 요소
  • swap area
    운영체제는 CPU에서 당장 수행해야 할 부분만을 메모리에 올리고
    나머지는 swap area에 내려놓는 방식으로 swap area를 메모리의 연장 공간으로 사용
  • 가상메모리 (virtual memory)
    운영체제가 프로그램이 자기 자신만의 메모리를 사용하는 것처럼 가정해 프로그램하는 것을 지원
    -> 프로그램은 0번지부터시작하는 자기자신만의 메모리 주소공간을 가정

가상메모리는 프로세스마다 각각 0번지부터 주소공간을 가지고,

이들 공간 중 일부는 물리적 메모리에 적재, 일부는 swap area에 존재

프로세스의 주소 공간을 메모리로 적재하는 단위에 따라 

가상메모리 기법은 다음과 같다.

• 요구 페이징(demand paging) 방식
• 요구 세그먼테이션(demand segmentation) 방식

페이징 기법과 세그먼트 기법의 장점만 취하는 주소 변환 기법

• 프로그램을 의미 단위의 세그먼트로 나눈다.
• 메모리에 적재하는 단위는 페이지 단위
• 주소변환을 위해 외위의 세그먼트 테이블 과 내부의 페이지 테이블 이용
       - > 2단계 페이지 테이블과 유사한 구조
  • < 세그먼트 번호, 오프셋> 으로 구성된 논리적 주소를 물리적주소로 변환
    • 세그먼트 번호를 이용하여 세그먼트 테이블의 해당 항목에 접근
    • 항목에 있는 세그먼트 길이와 세그먼트의 페이지 시작 주소 를 획득
    • 세그먼트의 길이를 넘어서는 메모리접근 시도인지 확인
    • 오프셋 값이 큰지 여부 확인
    • 테이블의 시작위치에서 페이지 번호만큼 떨어진 곳이 물리적 메모리의 페이지 프레임 위치
    • 페이지의 프레임 위치에서 오프셋의 하위 비트값인 페이지 내 변위만큼 떨어진 곳이 물리적 메모리 주소