1. 절대주소 vs 상대주소

	절대 주소	상대 주소
관점	메모리 관리자 입장	사용자 프로세스 입장
시작 주소	물리 주소 0번지 부터	물리 주소와 관계 없이 항상 0번지 부터
주소 공간	물리 주소(실제 주소) 공간	논리 주소 공간

• 절대 주소값 = 상대 주소 값 + 재배치 레지스터 값

---

2. 메모리 분할

• 여러 프로세스를 메모리에 적재하기 위해 고안된 방법
• 하나의 분할에 하나의 프로세스가 적재되는 방식

2-1. 고정 분할

메모리를 여러 개의 고정된 크기의 영역으로 분할하는 방식

2-1-1. 프로세스 배치 방법

	절대번역 및 적재	재배치 가능 번역 및 적재
큐 설정	각 분할영역마다 별도의 큐 설정	메모리 전체에 하나의 큐만 설정
프로세스 적재 방식	큐에 들어온 프로세스는 해당 분할영역에만 적재	모든 프로세스를 하나의 작업 큐에 넣어서 어느 분할에서든 실행 가능
주소 번역 방식	프로그램 컴파일 시 절대주소로 번역	프로그램 컴파일 시 상대주소로 번역
장점	구현 용이	절대번역 및 적재보다 기억장치의 낭비 감소
단점	큐가 빈 분할이 있어도 다른 큐의 프로세스를 적재할 수 없음 → 효율성이 낮음	절대번역기보다 더 복잡함

2-1-2. 내부 단편화(Internal fragmentation)

• 고정 분할 방식에서 프로세스의 크기가 적재된 분할영역의 크기보다 작아서 분할영역 내에 남게 되는 메모리가 낭비되는 현상
• 수행할 프로세스의 크기를 미리 알고 그에 맞춰 고정 분할을 할 경우 해결 가능

2-2. 동적 분할

메모리의 분할경계가 고정되지 않고 각 프로세스에 필요한 만큼의 메모리만 할당하는 방식

• 필요한 시점에 필요한 만큼의 메모리만 할당 받음 → 내부 단편화 X

2-2-1. 외부 단편화(External fragmentation)

• 메모리의 할당과 반환이 계속 반복됨에 따라 작은 크기의 공백이 메모리 공간에 흩어져 생기는 현상
• 공백보다 큰 프로세스가 메모리 할당을 요청하는 경우 대기 필요

2-2-1-1. 해결 방법

✅ 통합(coalescing)

인접된 공백을 더 큰 하나의 공백으로 만드는 과정

1. 하나의 프로세스 종료
2. 종료된 프로세스가 차지하고 있는 메모리 영역이 다른 비어 있는 메모리와 인접해 있는지 조사
3. 인접된 경우 빈 공간 리스트에 새로운 공백이나 기존의 공백과 합쳐 하나의 공백으로 만듦

• 문제점
  • 공백이 메모리 내에서 여기저기 분산되어 상당한 크기의 메모리를 차지하고 있는 경우 발생
  • 하나의 프로세스가 일정 크기의 큰 메모리 영역이 필요할 때 다음과 같은 경우 발생
    • 통합된 여러 공백의 합 > 작업의 기억장소 필요량
    • 제일 큰 공백 하나로는 그 프로세스를 수행할 수 없음

✅ 집약(compaction) = 압축

메모리 내의 모든 공백을 하나로 모으는 작업

• 동적 분할에서 통상적으로 발생하게 되는 여러 개의 작은 공백을 하나의 커다란 저장공간으로 만드는 것
  • 이용 가능한 기억장소가 연속으로 모여있게 됨
    • 집약으로 생긴 하나의 공백 > 작업의 기억장소 필요량 → 작업 실행 가능

---

3. 메모리 배치기법(메모리 관리 전략)

• 동적 분할 다중 프로그래밍에서 새로 반입된 프로그램이나 데이터를 메모리의 어느 위치에 배치할 것인가를 결정하는 것
• 운영체제가 유지하는 빈 공간 리스트 중 적합한 공간을 찾음

할당 전략	설명	특징
최초 적합 (first-fit)	프로세스가 적재될 수 있는 빈 공간 중 가장 먼저 발견되는 빈 공간 할당	· 메모리의 주소순으로 빈 공간 리스트 유지 · 할당 속도 빠름
후속 적합 (next-fit)	이전에 탐색이 끝난 그다음 부분부터 시작하여 사용 가능한 빈 공간 중에서 가장 먼저 발견되는 곳 할당	최초 적합 변형 방식
최적 적합 (best-fit)	필요한 공간을 제공할 수 있는 빈 공간 중 가장 작은 곳을 선택하여 할당	큰 빈 공간을 최대한 많이 확보
최악 적합 (worst-fit)	필요한 공간을 제공할 수 있는 빈 공간 중 가장 큰 곳을 선택하여 할당	작은 자투리 공간 발생 최소화

---

4. 버디 시스템(buddy system)

4-1. 개념

• 컴퓨터 운영체제에서 메모리를 효율적으로 할당하고 관리하기 위해 사용하는 메모리 할당 기술

4-2. 구현

1. 메모리 분할 : 메모리를 고정된 크기의 블록으로 나눔(2의 거듭제곱)
2. 할당 요청 처리 : 프로세스가 메모리를 요청할 때마다 시스템이 요청된 메모리 크기를 수용할 수 있는 가장 작은 사용 가능한 블록 탐색
3. 메모리 할당 및 해제
   • 프로세스가 메모리를 해제하면 시스템은 해당 블록을 사용 가능한 것으로 표시하고 버디 블록 재탐색
   • 인접한 해제된 블록들은 다시 합쳐져 더 큰 블록을 형성할 수 있음

4-3. 특징

• 내부 단편화 발생
• 제한된 메모리를 가진 환경에서 유용 ex) 임베디드 시스템

---

5. 가상 메모리(virtual memory)

5-1. 개념

• 컴퓨터 시스템의 메모리 크기보다 더 큰 기억공간이 필요한 프로세스를 실행할 수 있게 하는 방법
• 실행 중인 프로세스에 의해 참조되는 주소를 실제 메모리에서 사용하는 주소와 분리
• 전체 프로그램 및 데이터 중 현재 필요한 일부만 메모리에 적재

5-2. 사상(mapping)

• 가상주소를 참조하는 프로세스를 메모리에서 실행시키기 위해 가상주소를 물리주소로 변환하는 과정

5-2-1. 가상 주소(virtual address)

• 실행 프로세스가 참조하는 주소

5-2-2. 물리 주소(physical address) = 실주소(real address)

• 실제 메모리에서 사용하는 주소

5-3. 동적 주소 변환(Dynamic Address Traslation: DAT)

• 프로세스가 실행되는 동안 가상주소를 실주소로 변경하는 절차
• 주소변환 사상표 이용
• 인위적 연속성을 가짐

  💡 인위적 연속성
  가상주소 공간에서 연속적인 주소가 실주소 공간에서도 연속적일 필요는 없음

5-3-1. 페이징(paging) 기법

✅ 개념

• 가상 메모리를 페이지 단위로 나누어 관리하는 기법

  💡 페이지(page)
  고정된 크기의 블록

✅ 페이지 프레임

• 가상 메모리와 동일하게 고정된 크기로 분할된 메모리 영역의 블록
• 가상 메모리상의 페이지를 담을 수 있도록 실제 메모리에 틀(frame)을 만들어 둔 것

✅ 페이지 사상표

• 페이지가 메모리에 적재된 후에도 바로 찾을 수 있도록 프로세스가 사용하는 가상주소를 실주소로 동적 변환할 수 있게 함
• 가상주소의 페이지 번호별 저장 정보

✅ 동적 주소변환

	설명
직접사상	페이지 사상표를 직접 이용하여 동적 주소변환을 하는 방식
연관사상	페이지 변환 정보를 연관 메모리에 저장한 연관사상표를 이용하여 동적 주소변환을 하는 방식
연관/직접 사상	· 연관사상표에 참조된 페이지 항목이 없을 경우   직접사상 기법으로 변환하는 방식 · 연관사상표에는 가장 최근에 참조된 페이지 항목만 보관하고   나머지는 페이지 사상표에 수록

✅ 특징

• 메모리 보호는 페이지 단위로 이루어짐
• 외부 단편화 X, 내부 단편화 O

5-3-2. 세그먼테이션(segmentation) 기법

✅ 개념

• 가상 메모리를 세그먼트 단위로 나누어 관리하는 기법

  💡 세그먼트(segment)
  논리적 의미에 부합하는 다양한 크기의 블록 ex) 함수, 배열 등

• 메모리 적재는 최초 적합, 최적 적합 등의 방법 이용

✅ 세그먼트 사상표

• 페이지 사상표와 유사
• 가상주소의 세그먼트 번호별 저장 정보

5-3-3. 페이징/세그먼테이션 혼용기법

• 세그먼테이션 기법의 논리적 장점 + 페이징 기법의 메모리 관리 측면 장점
• 프로그램을 논리적인 세그먼트로 구분한 후, 각 세그먼트를 더 작은 페이지로 나누어 메모리에 적재하는 방식

---

6. swapping

6-1. 정의

• 현재 사용되지 않는 프로세스들을 보조기억장치의 일부 영역으로 쫓아내고, 그렇게 생긴 빈 공간에 새 프로세스를 적재하는 메모리 관리 방식

6-2. 과정

우선 순위가 높은 프로세스가 실행 대기 중인 경우,
우선 순위가 낮은 프로세스는 swap-out,
우선 순위가 높은 프로세스를 메모리에 로드하여 실행

• swap-in : 하드 디스크에서 프로세스를 주 메모리로 가져옴
• swap-out : 주 메모리에서 프로세스를 하드 디스크로 옮김

6-3. 장점

• 프로세스 실행 대기 시간 감소 → CPU 활용도 향상

6-4. 단점

• 프로세스의 주 메모리 ↔ 보조 메모리 이동으로 인한 시스템 성능 저하
• swapping 중 갑자기 종료되면 swap-out된 프로세스의 데이터가 손실될 수 있음

---

7. 페이지 교체 알고리즘

7-1. 정의

• 페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘

7-2. 페이지 부재 최소화

7-2-1. 페이지 부재(page fault)

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

7-2-2. 최적화 원칙

• 최적의 성과를 얻기 위해 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택
• 미래를 예측할 수 없으므로 실제로 실현 불가능

7-2-3. 교체 제외 페이지

효율적인 동작을 위해 교체가 발생하지 않도록 페이지 프레임에 페이지 고정

• 페이징을 위한 커널 코드 영역
• 커널에 속하지 못한 보조기억장치 드라이버 영역
• 시간을 맞춰 동작해야 하는 코드 영역
• I/O 장치로부터 직접 데이터가 교환되어야 하는 데이터 버퍼 영역

7-3. 알고리즘

7-3-1. FIFO(First-In First-Out)

✅ 개념

• 메모리 내에 가장 오래 있었던 페이지 교체
• FIFO 큐로 구현

✅ 단점

• 가장 많이 사용하는 페이지를 교체시킬 가능성 존재

• Belady의 이상현상 발생

  💡 Belady의 이상현상
  메모리에 더 많은 수의 페이지 프레임을 할당했을 때, 기대와 달리 페이지 부재가 더 많이 발생하는 현상

  • 메모리에 더 많은 페이지 프레임을 할당하면 프로세스가 사용할 수 있는 메모리 공간이 늘어나므로 페이지 부재가 발생할 확률이 낮아져야 함
  • 즉, 더 많은 데이터를 메모리에 적재할 수 있으므로 swapping이 감소할 것으로 기대
  • 그러나 새로운 페이지 프레임의 추가가 기존에 메모리에 있던 페이지들의 교체 순서를 바꿔 더 많은 페이지 부재를 발생시키게 됨

7-3-2. LRU(Least Recently Used)

✅ 개념

• 메모리 내에서 가장 오랫동안 사용되지 않은 페이지 교체

• 국부성 휴리스틱에 의존

  💡 국부성(locality)
  프로세스는 기억장치 내의 정보를 어느 한 순간에 특정 부분을 집중적으로 참조한다는 것

  💡 국부성 휴리스틱
  최근의 상황이 가까운 미래에 대한 좋은 척도

  • 시간 국부성 : 참조시간이 가장 오래된 페이지를 교체 대상으로 선택
  • 공간 국부성 : 메모리에 적재된 페이지 번호를 저장하는 리스트의 끝에 있는 페이지를 교체 대상으로 선택

✅ 장점

• Belady의 이상현상이 발생하지 않음
• 최적화 원칙에 근사한 선택이 가능함

✅ 단점

• 경험적 판단이 맞지 않는 상황이 존재함
• 막대한 오버헤드 발생
  • 시간 스탬프 관리
  • 가장 오래된 페이지 탐색

7-3-3. LFU(Least Frequently Used)

✅ 개념

• 메모리 내에서 참조된 횟수가 가장 적은 페이지 교체

✅ 단점

• 가장 드물게 사용되는 페이지가 가장 최근에 메모리로 옮겨진 페이지일 가능성 존재
• 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지가 불필요하게 메모리를 점유할 가능성 존재
• 막대한 오버헤드 발생
  • 사용 빈도 카운팅
  • 페이지 교체 결정 과정

7-3-4. 클럭 알고리즘

• 2차 기회 알고리즘에서 큐를 변형된 원형 큐로 관리

  💡 2차 기회 알고리즘
  참조 비트가 0이면서 메모리 내에 가장 오래 있었던 페이지 교체

• 원형 큐의 포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴

---

8. 프로세스별 페이지 집합관리

8-1. 워킹 세트 알고리즘

8-1-1. 워킹 세트(working set)

• 한 프로세스가 최근에 참조한 페이지의 집합
• 페이지 부재 비율을 감소시키기 위해 데닝(Denning)이 제안한 모델

8-1-2. 쓰레싱(thrashing)

• 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체처리에 너무 많은 시간을 소비함으로써 시스템의 처리량이 급격히 저하되는 현상

8-1-3. 워킹 세트 알고리즘

✅ 개념

• 프로세스의 워킹 세트를 메모리에 유지시키는 것을 원칙으로 하는 기법

✅ 방식
1. 각 프로세스의 워킹 세트를 감시하여 워킹 세트 크기에 해당하는 충분한 페이지 프레임 할당
2. 충분한 여분의 페이지 프레임이 존재하면 다른 프로세스를 들여와 실행 프로세스의 수 증가시킴
3. 실행 중인 프로세스들의 워킹 세트 크기의 합이 증가하여 총페이지 프레임 수를 넘을 경우 다음 과정 수행

• 우선순위가 가장 낮은 프로세스를 일시적으로 중지시켜 여유 페이지 프레임 확보
• 워킹 세트에 포함되지 않는 페이지를 담고 있는 프레임은 필요시 교체 대상으로 선택

✅ 문제점

• 과거를 통해 미래를 예측하는 것이 정확하지 않음
• 워킹 세트를 알아내고 업데이트하는 것이 현실적으로 어려움
• 워킹 세트를 구하기 위한 윈도 크기 δ의 최적값을 알기 어려움

8-2. 페이지 부재 빈도 알고리즘

8-2-1. 개념

• 페이지 부재 빈도(PFF)를 이용하여 프로세스별 페이지 집합의 크기를 변화시키는 기법

  💡 페이지 부재 빈도(Page Fault Frequently: PFF)
  페이지 부재로 교체가 발생하는 빈도를 나타내는 척도

• PFF > 상한 : 페이지 프레임 개수 1 증가
• PFF < 하한 : 그 사이에 참조되지 않았던 페이지 모두 제거

8-2-2. 장점

• 프로세스별 페이지 집합이 워킹 세트 알고리즘처럼 자주 바뀌지 않음
  → 페이지 부재가 발생하거나 PFF가 상한이나 하한을 벗어나는 경우에만 바뀜