15 가상 메모리2

2-1) 페이지 부재(Page Fault)
  * 페이지 부재가 발생하면 해당 페이지를 HDD (혹은 Backing Store)에서 찾아서 메모리에 적재해야 한다.
  (1) 페이지 테이블 참조했을 때 페이지 부재가 발생하면
  (2) 인터럽트(trap)이 걸려서 O/S로 전달
  (3) O/S가 HDD에서 해당 페이지 찾음
  (4) O/S가 해당 페이지를 메모리의 빈 프레임에 적재함
  (5) 페이지 테이블 갱신 (Frame Number 추가, i => v)
  (6) 페이지 테이블 재참조

  * 요구 페이징은 메모리를 절약하는 장점이 있지만 페이지 폴트가 발생 함으로써 프로세스 처리 시간이 늦어지게 된다.
    HDD에서 페이지를 읽어오는 시간이 오래 걸리게 된다.


2-2) 유효 접근 시간(Effective Access Time)
  * 프로세스 전체 집합(모든 페이지)가 메모리에 적재되어져 있지 않고 일부만 적재되어져 있기 때문에 페이지 폴트가 일어날 때와 일어나지 않을 때가 있다.
  * 페이지 폴트의 빈도에 따라 메모리에 접근하는 접근 시간이 달라지게 된다.
  * 이는 페이지 폴트의 발생 확률과 밀접한 관련이 있으며 그 시간을 유료 접근 시간이라고 한다.
    Teff (유요 접근 시간) = (1-P)Tm + PTp
    P : 페이지 폴트 발생률(page fault rate)
    Tm : 메모리를 읽는데 걸린 시간
    Tp : 페이지 폴트가 발생하여 이를 처리하는데 걸리는 시간

    예제)
    Tm = 200 nsec
    Tp = 8 msec = 8,000,000 nsec
    Teff = (1 - P)200 + P8,000,000 = 200 + 7,999,800P
    만약 P = 1/1,000 이면 Teff = 8.2 usec (Tm에 비해 약40배 느려짐)
    만약 P = 1/399,990 이면 Teff = 220 nsec (Tm에 비해 약10% 느려짐)

  * 페이지 폴트가 너무 자주 일어나면 처리 속도가 느려지기 때문
   : (1) 페이지 폴트를 최소화 하도록 한다.
   : (2) backing store로 플래시 메모리(SSD)와 같은 속도가 빠른 보조기억 장치를 이용한다.

  * 지역성(Locality)
   : 시간적 지역성
      한 번 읽으면 곧 또 읽을 확률이 많다. 반복문과 같은 코드가 많이 있기 때문이다.
     한번 페이지 부재가 생겨서 가져 오면 그 시간 이후에는 자주 일어나지 않게 된다.

   : 공간적 지역성
     예를들어 지금 1,000번지를 읽고 있으면 1,000번지 부근을 또 읽을 확률이 높다.
     즉, 보통 그 인접한 구역을 읽게 된다.
     유사한 코드가 함께 근처에 블록단위로 있기 때문이다.
     한 번 페이지 부재가 생겨서 읽어 오면 그 영역을 계속 읽기 때문에 페이지 부재가 다시 일어나지 않게 된다.

15 가상 메모리1

0) 가상 메모리란?
  * 출현 계기
    : 물리 메모리(Physical Memory)의 크기에 따른 한계를 극복하기 위한 기술
      즉, 물리 메모리(Physical Memory)보다 큰 프로세스 실행이 가능하다.
      예) 100MB 메인 메모리에서 200MB 크기의 프로세스 실행가능
          원래는 100MB인 메인 메모리보다 큰 프로세스는 실행이 불가.
  * 적용 방법
    : 현재 실행에 필요한 부분만 메모리에 올린다!
     즉, 프로세스 이미지를 모두 메모리에 올릴 필요는 없다.
     오류 처리, 배열의 일부, 워드프로세스에서 정렬, 표 기능 등은 제외가능하다.
      동적 적재 (dynamic loading)와 비슷한 개념이다.

1) 요구 페이징(Demand Paging)

  * 대체로 "가상 메모리 = 요구 페이징"을 의미함.
  * 프로세스를 페이지 단위로 나누고 CPU가 처리하는데 필요한 페이지만 즉, 요구되는 페이지만 메모리에 적재하는 것이어서 "요구 페이징(demand paging)"이라고 한다.
  * 프로세스는 페이지의 집합이다.
  * 메모리에 적재되지 못한 프로세스의 나머지 페이지들은 backing store에 저장되어져 있다.

  * 위 그림의 경우 10 Mb 메인 메모리에 각각 5 Mb, 7 Mb, 4 Mb인 프로세스 3개를 모두 적재하였다. 단, 각 프로세스에서 필요한 페이지(3개, 4개, 1개)만 적재되어져 있다.

  * 페이지 부재(Page Fault)
    : CPU가 필요로 하는 Page가 메인 메모리에 적재되어져 있지 않은 경우를 의미한다.
    : 페이지 부재(Page Fault)가 발생하면 해당 페이지를 메모리에 적재해주어야 한다.

  * 순수 요구 페이징(Pure Demand Paging)
    : 순수하게 현재 시점에 필요한 페이지만 적재한다.
    : 장점 - 메모리 절약을 최대화 할 수 있다.
    : 단점 - 시작하자 마자 페이지 부재가 일어난다. 속도가 느려진다.

  * 프리페이징(Prepaging)
    : 당연히 사용될 페이지라고 예측되어지는 페이지는 미리 적재한다.
    : 장점 - 미리 적재되어져 있기 때문에 속도가 빠르다.
    : 단점 - 페이지 부재가 적다. 만약 사용되지 않으면 메모리 낭비가 된다.

  * Swapping vs Demand Paging
    : Swapping - 프로세스 단위로 이동
    : Demand Paging - 페이지 단위로 이동

14. 메모리 관리3

3) 세그멘테이션(Segmentation)
  * 프로세스를 논리적 내용(=세그멘트)으로 잘라서 메모리에 배치
    : 프로세스는 세그멘트(segment)의 집합
  * 동일한 크기를 갖는 페이징과는 달리 메모리를 프로그램을 구성하는 메인루틴, 서브루틴(Sub-Routine), 프로시저(Procedure), 함수(Function) 또는 모듈(Module), 전역 변수, 스택(Stack) 등의 각각 다른 크기를 갖는 세그먼트로 나눔.
    : 각 세그먼트는 연관된 기능을 수행하는 하나의 모듈 프로그램임으로 논리적 구조화가 쉬움.
    : 각 세그먼트가 페이징처럼 메모리에서 서로 인접할 필요는 없음.

 * 논리 주소 vs 물리 주소

  * 메모리 보호(Protection)
    : 모든 주소는 세그먼트 테이블을 경유하도록 한다.
    : 세그먼트 테이블 엔트리(각 열)마다 r(읽기), w(쓰기), x(시행) 비트를 둔다.
    : 논리적 단위로구분되어 있어서 페이징 보다 훨씬 수월하다.

  * 메모리 공유(Memory Sharing)
    : 같은 프로그램을 쓰는 여러 종류의 프로세스들은 Code를 공유할 수 있다.
      (단, pure code = reentrant code = non-selfmodifying code)
     즉, 프로세스의 세그먼트 테이블 코드 영역이 같은 곳을 가리키도록 한다.
    : 논리적 단위로구분되어 있어서 페이징 보다 훨씬 수월하다. 

  * 문제점
    : 연속 메모리 할당과 같은 메모리 할당 기법을 고려해야한다.
     이로 인해 외부 단편화 문제가 존재한다.
    : 따라서 세그멘테이션 보다는 페이징 기법이 더 일반화되어 사용된다.


4) 페이지드 세그멘테이션(Paged Segmentation)
 * 프로세스를 나눌 때 세그먼트 단위로 나눈다.
   그리고 각 세그먼트를 페이지 단위로 다시 일정하게 나눈다.
 * 장점은 보호와 공유가 용이하고 외부 단편화를 없앨 수 있다.
 * 단점은 세그먼트 테이블과 페이지 테이블이 필요하게 됨으로 주소 변환과정이 더 복잡해지고 시간이 오래 걸리게 된다.

14. 메모리 관리2

2) 페이징(Paging)

 * 프로세스를 일정한 크기로 잘라서 메모리에 할당한다.
   : 프로세스의 일정한 크기 => 페이지(page)
   : 메모리의 일정한 크기공간 => 프레임(frame)
 * 물리 메모리내에 하나의 프로세스가 연속된 메모리를 할당받을 필요 없이 여러 개의 페이지 조각으로 나누어져서 분산 할당된다.
 * 프로세스와 메모리가 동일한 크기로 규격화 됨으로써 외부 단편화가 발생하지 않는다.
 * 내부 단편화(Internal Fragmention)가 발생하지만 심각한 수준은 아니다.
   내부 단편화
    - 메모리 10 kb 프레임에 3 kb 페이지(23 kb 프로세스 였다면 3 kb 짜투리가 남음)가 할당되면 해당 메모리는 7 kb의 내부 단편화가 발생한다.

 * 논리 메모리 vs 물리 메모리 변환

< 논리 주소 50은 물리 주소로 몇 번지인가? >

   * 페이지 테이블의 크기는 프로세스 크기(160 kb) / 페이지 크기 (16 kb) = 10개
   * CPU는 50번지를 요청했지만, 실제 데이타는 98번지에 위치해 있게 된다.
     즉, CPU는 실제 메모리 주소는 고려하지 않고 자신이 원하는 주소를 제공하면 MMU (여기서는 Page Table)를 거치면서 자동 변환되어 처리된다.
   * CPU는 프로세스가 메모리에 연속된 주소에 있는 것으로 처리되기 때문에 문제 없이 처리되도록 하고, 실제 메모리는 페이지 단위로 할당해서 외부 단편화 문제를 해결하게 된다.

   * 메모리 보호(Protection)
    : 모든 주소는 페이지 테이블을 경유하도록 한다.
    : 페이지 테이블 엔트리(각 열)마다 r(읽기), w(쓰기), x(시행) 비트를 둔다.
   * 메모리 공유(Memory Sharing)
    : 같은 프로그램을 쓰는 여러 종류의 프로세스들은 Code를 공유할 수 있다.
      (단, pure code = reentrant code = non-selfmodifying code)
     즉, 프로세스의 페이지 테이블 코드 영역이 같은 곳을 가리키도록 한다.

   * 장점
    : 공유 페이지의 이용 가능
    : 외부 단편화가 발생하지 않으며, 압축이 불필요.
    : 메모리 활용을 통한 다중 처리 프로그래밍 실현.

   * 단점
    : 내부 단편화 발생 (but 외부 단편화에 비해 무시가능한 수준임)
    : 페이징 사상을 위한 하드웨어로 가격 상승과 속도 저하
    : 같은 크기의 메모리 프레임에 추가해야하기 때문에 Code와 Data의 경계가 특정 프레임에 함께 들어가는 문제가 있다.

14. 메모리 관리1

1) 연속메모리 할당(Contiguous Memory Allocation)

  * 하나의 프로세스는 연속된 메모리 공간에 할당을 받게 된다.

  * 부팅직후에는 메모리홀이 매우 크지만 시간이 지날 수록 프로세스의 생성과 소멸이 반복되면서 불연속적으로 단편화된 작은 홀들이 흩어 지게 된다.

   위 그림의 마지막에서 3칸을 차지하는 Process는 메모리에 진입할 수 없게 된다.

  * 외부 단편화(External Fragmentation)

    : 빈 메모리 공간이 있지만 이 공간이 여러개의 불연속적인 작은 공간으로 나뉘어져 있어서 프로세스를 할당할 수 없는 상태일 때 이 조각난 공간들에 대한 현상을 외부 단편화라고 한다. 외부 단편화는 심한 메모리 낭비의 원인이 된다.

 * 메모리 할당 방식

  : 메모리를 프로세스에게 어떻게 할당하는 것이 바람직한가?에 대한 문제.

  (1) First-fit (최초 적합)

     : 최초로 할당받을 수 있는 크기의 공간에 무조건 할당된다.(위 또는 아래 부터)

  (2) Best-fit (최적 적합)

     : 크기가 가장 근접한 공간에 할당된다.

  (3) Worst-fit (최악 적합)

      : 크기가 가장 많이 차이가 나는 공간에 할당된다.

  * 속도면에서는 "best-fit"이 최고이다.

  * 이용률 면에서는 "first-fit"과 "best-fit"이 좋은 편이고 "worst-fit"은 좋지 못함. 

  * 어떤 경우이든 외부 단편화는 존재하기 마련이다.

 * 압축(Compaction)

  : 외부 단편화의 해결방안으로 흩어져 있는 홀들을 하나의 커다란 홀로 통합하여 사용한다.

  : 문제는 어떤 방식으로 압축을 할 것인가가 큰 문제가 된다. 상대적으로 커다란 프로세스를 이동하여 압축을 하게 된다면 압축을 위한 비용이 많이 들어 비효율적이게 된다.

13. 주기억 장치의 이해2

2) 효율적인 메모리 사용을 위한 기법

 (1) 동적 적재(Dynamic Loading)
    : 프로그램이 실행될 때 프로그램의 모든 것이 다 한 번에 메모리에 적재(정적 적재, static loading)되는 것이 아니라 프로그램이 실행되는데 필요한 부분만 필요에 따라서 적재하는 방법이다. 사용되지 않거나 사용될 가능성이 낮은 내용은 애초에 메모리에 적재하지 않음으로써 메모리를 절약한다.
    : 모든 루틴(routine)이 다 사용되는 것은 아니다.
      예) 오류처리 - 예외가 발생했을 때만 필요하다.
    : 모든 데이터(data)가 다 사용되는 것은 아니다.
      예) 배열 - 배열의 어떤 일부는 필요할 때만 접근 하면 된다.
    : 모든 클래스가 다 사용되는 것은 아니다.
     예) 자바 - 특정 클래스는 필요할 때만 호출하면 된다.
        파워포인트 - 파워포인트를 실행했을 때 디자인 템플릿을 미리 메모리에 올려놓을 필요는 없다. 사용자가 디자인 템플릿 사용을 요청했을 때 메모리에 올리면 된다.

 (2) 동적 연결(Dynamic Linking)
    : 여러 개의 프로그램이 실행될 때 다수의 프로그램이 공통으로 사용하는 라이브러리를 사용하는 프로그램의 수 만큼 메모리에 적재하는 것이 아니라 한 번만 적재하고 각 프로그램이 공동으로 해당 라이브러리를 사용할 수 있도록 함으로써 메모리를 절약할 수 있게 된다.
    : printf() 함수와 관련된 라이브러리는 대부분의 프로그램이 사용줄이다. 다라서 처음 프로그램이 실행될 때 로드된 printf()함수와 관련된 라이브러리를 적재하고 이후의 프로그램들은 처음 적재된 printf()함수의 라이브러리를 공유해서 사용한다.
    : 동영상 실행과 음악 실행은 소리를 재생하는 라이브러리를 공유하도록 한다.
    : Email과 FTP 프로그램은 네트웍 라이브러리를 공유하도록 한다.
    : dll(Dynanic Linking Library) - link를 exe 파일을 만들 때 하지 않고 메모리에 적재할 때 link를 한다.

 (3) 스와핑(Swapping)
    : 메모리에 적재되어져 있으나 현재 사용되지 않는 프로세스에 대해 HDD로 추출(swap-out)하거나 추출되었던 프로세스가 재사용됨에 따라 다시 메모리로 적재(swap-in)하는 것.
     메모리 공간만 차지하고 사용되지 않는 프로세스를 추출함으로써 메모리를 절약할 수 있다.

   : 프로세스가 매우 클경우 스와핑(out / in)에 대한 부담이 커지게 된다.
   : backing store는 일반적으로 HDD의 일부 영역을 활용하지만 서버와 같은 특수한 환경에서는 별도의 전용 backing store를 사용하기도 한다.

13. 주기억 장치의 이해1

1) 실행파일, 메모리의 구조와 원리
  (1) 실행파일의 생성

  (2) 메모리에 프로그램 적재

  (3) 메모리 구조(Memory Structure)

    * 주소버스
      : CPU가 접근하고자 하는 메모리의 주소(논리 주소)를 전달하는 통로

    * 데이타 버스
     : CPU가 메모리의 프로세스 명령이나 데이타를 전달 받거나 CPU의 처리 결과를 메모리에 전달하여 그 내용을 업데이트하도록 하는 데이타 전송 통로

  (4) 논리 주소(Logical address)와 물리 주소(Physical address)

   * 논리 주소(Logical Address)
     : 하나의 프로그램이 만들어 질 때 메모리의 어떤 주소에 위치하게 될지 알 수 없다. 또한 CPU는 프로그램들이 연속된 메모리의 프로세스로 적재된다고 전제하고 있다. 따라서 CPU가 메모리를 접근하기 위해 임의의 연속된 메모리를 할당해 주게 되는데 이 주소를 논리 주소라고한다.

   * 물리 주소(Physical Address)
     : CPU가 논리 주소를 이용해 메모리에 접근하려 하면, CPU가 제공한 논리 주소와 매핑된 실제 메모리의 주소를 물리 주소라고 한다.

   * 재배치 레지스터(Relocation register)
     : 논리주소를 물리 주소로 변환시켜 주는 메모리 관리 장치(MMU)내의 레지스터