인프런 워밍업 클럽 - CS Day 11

Algorithm

• 영역을 2개로 나누어서 정렬을 수행하는 알고리즘

  • 정렬된 영역

  • 정렬되지 않은 영역

• 정렬되지 않은 영역에서 데이터를 하나씩 꺼내서 정렬된 영역 내의 적절한 위치에 삽입하여 정렬하는 알고리즘

시간 복잡도

• O(n^2) : 배열이 역순으로 정렬되어 있는 경우

장점

• 구현이 간단하고 이해하기 쉽다.

• 추가적인 메모리 소비가 적다.

단점

• 시간 복잡도가 O(n^2)로 느리다.

• 데이터의 상태에 따라 성능 편차가 크다.

  • 최선의 경우 : O(n)

  • 최악의 경우 : O(n^2)

OS

가상 메모리

• 프로세스는 OS 영역이 어디있는지, 물리 메모리의 크기가 얼마나 큰지 몰라도 된다.
  → 프로그래머는 물리 메모리의 크기와 프로세스가 메모리에 어느위치에 신경쓰지 않고 0x0번지에서 시작한다고 가정하고 프로그래밍을 한다.

• 프로세스는 메모리 관리자를 통해서 메모리에 접근한다.

  • 직접 메모리에 붙지 않는다.

• 가상 메모리의 크기

  • 이론적 무한대

  • 실제 : 물리 메모리 크기 + CPU 비트 수
    ex) 32bit → 표현 가능한 주소값 : 2^32 = 4GB

• 가상 메모리 시스템은 물리 메모리가 처리할 수 없는 용량을 프로세스들이 요구할 때 물리 메모리 내용의 일부를 하드 디스크에 있는 스왑 영역으로 옮기고 처리가 필요할 때 물리 메모리로 가져와서 처리한다.
  → 물리 메모리가 처리할 수 없는 용량의 작업들을 처리할 수 있게 한다.

• 메모리 관리자는 가상주소와 물리 주소를 1 : 1 매핑 테이블로 관리한다.
  

가상 메모리의 프로세스 할당 방법

• 가상 메모리 시스템에서는 OS 영역을 제외한 나머지 영역을 일정한 크기로 나누어서 프로세스에게 할당한다.

가변 분할 방식(Segmentation)

• 프로그램은 함수나 모듈 등으로 세그먼트를 구성한다.

• 각 세그먼트들이 인접해 위치할 필요는 없다.
  But. 프로세스 입장에서는 코드 영역, 데이터 영역, 힙 영역, 스택 영역을 서로 인접한 것 처럼 바라본다.

MMU(메모리 관리자)가 논리주소로 물리주소로 변환해주는 방법

• 세그멘테이션 테이블이라는 테이블이 존재

  • Base Address

  • Bound Address
    ⇒ 두 주소를 사용하여 물리 메모리 주소를 계산한다.

Address

• Base Address

  • 프로세스나 세그먼트의 물리 메모리 상 시작 주소를 나타낸다.

  • MMU의 base register에 저장되어 주소 변환에 사용

• Bound Address (또는 Limit)

  • 프로세스나 세그먼트의 크기를 나타낸다.

  • MMU의 bound/limit register에 저장되어 메모리 보호에 사용된다.

논리주소 → 물리주소

1. CPU에서 논리 주소 전달

2. MMU는 해당 논리 주소가 몇 번 세그먼트 인지 확인

3. MMU내의 Segment Table Base Register 내에 있는 세그멘테이션 테이블을 찾는다.

4. 세그먼트 번호를 인덱스로 Base Address와 Bound Address를 찾는다.

5. MMU는 CPU에서 받은 논리주소와 Bound Address의 크기를 비교한다.

   • 논리주소가 Bound Address보다 작은 경우

     • 논리주소와 Base Address를 더해 물리 주소를 더한다.

   • 논리주소가 Bound Address보다 큰 경우

     • 메모리를 침범했다고 간주하고 에러를 발생시킨다.

STBR(Segment Table Base Register)

• OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.
  → Context Switching이 고비용 작업인 이유

장점

• 메모리를 가변적으로 분할할 수 있다.

• 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 모듈로 처리할 수 있어 공유와 각 영역에 대한 메모리 접근보호가 편리하다.

단점

• 외부 단편화 발생

고정 분할 방식(Paging)

• 세그멘테이션 기법의 외부 단편화를 해결하기 위해 고안된 배치 정책

• 페이징은 메모리를 할당할 때 정해진 크기의 페이지로 나눈다.
  → 외부 단편화가 발생되지 않는다.

• Page : 일정한 크기로 균일하게 나뉘어진 논리주소공간

• Frame : 일정한 크기로 균일하게 나뉘어진 물리주소공간
  

가장 신경써야 하는 점

• 페이지 테이블의 크기

  • 각 프로세스마다 테이블을 갖는다.
    → 프로세스가 많아질 수록 페이지 테이블도 많아진다.
    → 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어든다.

  • 페이지 테이블 크기가 너무 큰 경우 : 사용자 영역이 부족하다.

Page Table

• 가상 주소를 물리 주소로 변환하는데 사용하는 테이블

• 각 프로세스의 가상 페이지 번호(VPN)을 물리 프레임 번호(PFN)로 매핑한다.

• 각 프로세스마다 독립적인 Page Table을 갖는다.

• 페이지 테이블에 Invalid로 되어 있으면 스왑영역에 저장되어 있는 상태

Page Table Entry(PTE)

• 페이지 기본 주소 (Page base address)

• 유효 비트 (Valid bit): 페이지가 메모리에 있는지 여부

• 보호 비트 (Protection bit): 읽기/쓰기/실행 권한

• 참조 비트 (Reference bit): 페이지 접근 여부

• 수정 비트 (Dirty bit): 페이지 내용 변경 여부

Page Table Base Register(PTER)

• 각 프로세스의 PCB에 위치하며, 해당 프로세스의 Page Table의 시작 주소를 가리킨다.

• OS는 컨텍스트 스위칭을 할 때마다 메모리 관리자내의 Segment Table Base Register를 해당 프로세스의 것으로 값을 바꿔줘야 한다.

논리주소 → 물리주소

1. CPU에서 논리주소 전달

2. MMU는 논리주소가 몇번 페이지인지 오프셋은 어떻게 되는지 확인

3. MMU에서 Page Table Base Register를 이용하여 물리 메모리에 있는 페이지 테이블을 찾는다.

4. 페이지 번호를 인덱스로 프레임 번호를 알아낸다.

5. 오프셋을 사용하여 물리 주소로 변환한다.
   

장점

• 메모리를 효율적으로 관리할 수 있다.

단점

• 내부 단편화 발생

  • 세그멘테이션의 외부 단편화와 비교하면 많은 공간을 비교하지 않는다.

Segmentation vs Paging

차이점

• 페이지의 크기

  • 세그멘테이션은 프로세스마다 크기가 달라 Bound Address를 갖는다.

  • 페이징은 모든 페이지의 크기가 동일해서 크기를 표현하는 Bound Address가 필요없다.

• 세그멘테이션은 논리적인 영역별로 세그먼트를 나눈다.
  → 세그먼트 마다 크기를 다르게 나눌 수 있다.
  → 코드 영역, 데이터 영역, 스택 영역, 힙 영역을 나눌 수 있다.

• 페이징은 페이지의 크기가 고정되어 있어 논리적인 영역을 나눌 수 없다.
  → 특정 영역만 떼어내서 공유하거나 권한을 부여하기 어렵다.

Paged Segmentation

• 세그멘테이션 - 페이징 혼용 기법

  • 각각의 장점을 혼합한 기법

• 세그멘테이션 테이블과 페이지 테이블을 결합하여 사용한다.
  

메모리 접근 권한

• 메모리의 특정 번지에 부여된 권한

• 상태값 : Read, Write, Execute

• 각 프로세스는 코드 영역, 데이터 영역, 힙 영역, 스택 영역이 존재한다.
  → 각 영역마다 접근 권한이 있다.

  • 코드 영역 : 프로그램 자체 ⇒ 읽기/실행 권한

  • 데이터 영역 : 일반변수, 전역변수, 상수로 선언한 변수 저장 ⇒ 읽기/(쓰기-Optional) 권한

  • 힙 영역 : 읽기/쓰기 권한

  • 스택 영역 : 읽기/쓰기 권한

• 메모리 접근 권한 검사는 가상주소에서 물리주소로 변환될 때마다 일어난다.

  • 권한을 위반하는 경우 에러를 발생시킨다.

주소 변환 과정

1. 세그먼트 번호로 세그먼트 테이블에 접근하여 세그먼트 길이와 해당 세그먼트의 페이지 테이블 시작 주소를 얻는다.

2. 해당 세그먼트가 메모리 접근 권한을 위반하는지 검사한다.

   • 접근 권한 위반 시 프로세스 종료

3. 세그먼트의 페이지 테이블 시작 주소에 세그먼트 내 페이지 번호를 더해 페이지 테이블 항목에 접근한다.

4. 페이지 테이블에서 프레임 번호를 얻는다.

5. 프레임 번호에 페이지 내 오프셋을 더해 최종 물리 주소를 얻는다.

단점

• 물리 메모리에 접근하기 위해 메모리에 두 번 접근해야 한다.

  1. 세그멘테이션 테이블 참조

  2. 페이지 테이블 참조
     → 페이징과 페이지드 세그멘테이션 기법을 적절히 섞어서 사용한다.

DAT(Dynamic Address Translation, 동적 주소 변환)

• 메모리 관리자가 물리 메모리와 스왑영역을 합쳐서 프로세스가 사용하는 가상주소를 물리주소로 변환하는 과정

• DAT를 거치면 프로세스는 마음대로 사용자 데이터를 물리 메모리에 배치할 수 있다.