운영체제 ch 10. Virtual Memory

Virtual Memory

• Background
• Demand Paging
• Copy-on-Write
  
  • 프로세스끼리 메인 메모리를 공유하게 하면서 동시에 프로세스 자신만의 데이터를 저장
• Page Replacement
• Allocation of Frames 
• Thrashing
  • 요구하는 페이지가 메인 메모리에 없어 disk로부터 불러오고, 불러오는 페이지의 공간을 마련하기 위해 이전 페이지를 disk에 저장하는 page fault가 자주 발생하는 것
• Memory-Mapped Files
• Allocating Kernel Memory
• Other Considerations
• Operating-System Examples

 

Objectives

• virtual memory system의 이점을 설명
• demand paging, page-replacement algorithm 및 page frame 할당의 개념 설명
• working-set model의 원리 논의
  • working-set: 프로세스의 페이지들 중 메인 메모리에 있어야 하는 instruction/data의 집합, 금방 사용될 부분들
  • 지역성(locality)을 가지고 working-set 구분
• shared memory와 memory-mapped files 간의 관계를 검사
• 커널 메모리가 관리되는 방법 탐색

 

Background

• 실행하려면 코드가 메모리에 있어야 하지만, 전체 프로그램은 거의 사용되지 않음
  • 오류 코드, 비정상적인 루틴, 대용량 데이터 구조
• 전체 프로그램 코드가 동시에 필요하지 않음
• 부분적으로 로드된 프로그램(partially-loaded program)을 실행할 수 있는 능력 고려
  • 프로그램이 더 이상 물리적 메모리 제한에 의해 제한되지 않음
  • 필요한 부분만 메인 메모리에 존재해 작은 크기의 메인 메모리가 필요 (적은 수의 페이지 필요)
  • 각 프로그램이 실행되는 동안 더 적은 메모리를 사용 → 더 많은 프로그램이 동시에 실행
    • 응답 시간(response time)이나 소요 시간(turnaround time)을 늘리지 않고 CPU 활용률 및 처리량 향상
    • Multiprogramming - CPU 활용도 ↑, I/O 수행시 CPU가 다른 프로세스에 할당됨
• 프로그램을 메모리에 로드하거나 swap하는 데 필요한 I/O 감소 → 각 사용자 프로그램의 실행 속도가 향상됨
  • I/O size ↓ - 필요한 부분만 읽기 때문

 

Virtual memory

• 물리 메모리에서 사용자 논리 메모리 분리
• 실행을 위해 프로그램의 일부만 메모리에 있어야 함
• 따라서 논리 주소 공간은 물리 주소 공간보다 훨씬 클 수 있음
• 장점
  • 여러 개의 프로세스가 동시에 메인 메모리에 존재 가능
  • 여러 프로세스에 의해 주소 공간이 공유될 수 있음 ex) dynamic library
  • 보다 효율적인 프로세스 생성 가능
  • 더 많은 프로그램이 동시에 실행될 수 있음
  • 프로세스 로드 또는 swap에 필요한 I/O 감소 - I/O 속도 빠름

 

Virtual address space

• 프로세스가 메모리에 저장되는 방식에 대한 logical view (프로세스의 공간)
• 일반적으로 주소 0에서 시작하며 공백이 끝날 때까지 연속적인 주소
• 한편, 물리 메모리는 page frames로 구성
• MMU는 논리 주소를 물리 주소로 매핑해야 함
• virtual memory는 다음을 통해 구현될 수 있음
  • Demand paging - 실행에 필요한 page만 메인 메모리에 탑재
  • Demand segmentation

 

Virtual Memory That is Larger Than Physical Memory

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 프로세스의 공간이 훨씬 커 메인 메모리에 없을 수 있음 → disk로부터 페이지를 불러오는 page fault 발생
• page fault 자주 발생 → thrashing
• MM size < disk size
  • free page frame이 없는 경우 → 메인 메모리에 있는 것 중 사용될 가능성이 적은 애를 swap out
  • disk에 있는 페이지를 읽어오기 위해 메인 메모리에 있는 page frame을 교체해야 함 - page replacement
    • swap out할 내용이 메인 메모리로 들어온 다음에 수정되지 않은 것이라면 disk의 내용과 같아 swap out할 필요가 없고 disk로부터 불러오기만 하면 됨
    • modify bit (dirty bit)
      • 해당 페이지가 메인 메모리에 들어온 후 수정이 되었는지 안 되었는지 알려주는 bit
      • modify bit = 0 → disk에서 메인 메모리로 읽어온 후 수정되지 않음. 새로운 걸 overwrite
      • modify bit = 1 → 메인 메모리로 들어온 후 수정됨, 메인 메모리의 내용 ≠ disk의 내용, 교체하기 전에 disk에 써줘야 함

 

Virtual-address Space

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 일반적으로 stack이 최대 논리 주소에서 시작하여 heap이 "up"되는 동안 "down" 되도록 논리 주소 공간을 설계
  • 주소 공간 사용 극대화
  • stack, heap 사이의 사용되지 않은 주소 공간이 hole
    • heap 또는 stack이 주어진 새 페이지로 증가할 때까지 물리 메모리가 필요하지 않음
    • 여러 프로세스들에 의해 공유되는 dynamic library 같은 것이 hole에 매핑 → 공유가 가능한 메모리를 프로세스 안에 매핑시키기 위해 hole 사용
    • 통신에 사용되는 shared memory의 경우 중간에 매핑되는 페이지들이 read/write 되어야 함
• 남아 있는 holes이 sparse 주소 공간, 동적으로 연결된 라이브러리 등을 사용 가능
• virtual address space로의 매핑을 통해 공유되는 시스템 라이브러리
  
• 페이지 read/write를 virtual address space에 매핑하여 shared memory 제공
• fork() 중에 페이지가 공유될 수 있어 프로세스 생성 속도 향상
  • fork()시 parent가 만들어지고 이 parent의 내용들이 child로 들어가게 됨
  • parent와 child가 똑같은 부분들을 공유할 수 있도록 만들어 줌 → 빠르게 child 생성
  • child를 수정해야 될 경우 자기만의 데이터를 수정할 수 있는 별도 공간이 만들어짐

 

Shared Library Using Virtual Memory

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 각 프로세스의 주소 공간 안에 매핑
• ex) dynamic library 같은 것 or 통신에 사용되는 shared memory

 

Demand Paging

• 필요한 부분만 메인 메모리에 할당
• load time에 전체 프로세스를 메모리로 가져올 수 있음
• 또는 필요할 때만 page를 메모리로 가져옴
  • 필요한 I/O 감소, 불필요한 I/O 없음
    
  • I/O 수행시 CPU가 switch 되므로 CPU 활용도 높아짐
  • 필요한 메모리 감소
    
  • 필요한 부분만 존재하므로 더 많은 프로세스가 메인 메모리에 존재 가능
  • 더 빠른 응답
  • 더 많은 사용자
    

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• swap 기능이 있는 페이징 시스템과 유사함 (그림)
  
• 페이지가 필요 → 그것을 참조
  • 메인 메모리 안의 각각의 page는 별도 정보 필요
    1. 해당 프로세스의 페이지인지 여부
    2. page fault 필요한지 여부
  • invalid reference → 해당 프로세스의 페이지가 아님 → 중단(abort)
    
  • not-in-memory → 메모리로 가져옴 (page fault)
    
• Lazy swapper
  • 페이지가 필요할 때까지 메모리로 페이지를 swap하지 않음
    
  • 실행에 필요할 때 메인 메모리에 swap-in 시켜줌
  • 페이지를 다루는 swapper는 pager

 

Basic Concepts

• swapping에서, pager는 다시 swapping하기 전에 사용할 페이지를 추측
  
• 대신 pager는 해당 페이지만 메모리로 가져옴
  
• 해당 페이지 집합을 어떻게 결정하는가?
  
  • demand paging을 구현하기 위한 새로운 MMU 기능 필요
    
• 필요한 페이지가 이미 메모리에 있는 경우
  
  • non demand-paging과 차이 없음
    
• 필요한 페이지가 메모리에 없는 경우
  
  • 프로그램 수정이 절대 있어서는 안 됨! → user transparency
  • storage에서 페이지를 찾아 메모리에 로드해야 함
    
  • 프로그램 동작을 변경하지 않고, 프로그래머가 코드를 변경할 필요가 없음

 

Valid-Invalid Bit

• 각 page table entry에는 valid-invalid bit가 연결됨 (v → in-memory (메모리 상주), i → not-in-memory)
  
• 초기에 valid-invalid bit가 모든 entry에서 i로 설정됨
  
• page table snapshot 예시
  

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• MMU 주소 변환 중 page table entry의 valid-invalid bit가 i → page fault

 

Page Table When Some Pages Are Not in Main Memory

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• ex) B → page fault 발생

 

Page Fault

• 페이지에 대한 참조가 있는 경우 해당 페이지에 대한 첫 번째 참조는 운영 체제에 trap됨: page fault 라면
  • access할 때 page fault인지 확인

1. 운영 체제는 다음을 결정하기 위해 또다른 테이블을 봄
   
   • Invalid reference → 중단(abort) - 프로세스의 페이지가 아닌 것
     
   • not-in-memory → page fault
     
2. free frame 찾기
3. 예약된 disk operation을 통해 page를 frame으로 전환 (disk에서 메인 메모리로 불러옴)
   
4. 메모리 안에 현재 page를 나타내도록 table 재설정, validation bit = v로 설정
   
5. page fault를 발생시킨 instruction을 재시작

 

Steps in Handling a Page Fault

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• load M - instruction
• 2 - M이 존재하지 않아 interrupt 발생
• 3 - disk 어느 위치에 요청하는 페이지가 있는지 확인

 

Aspects of Demand Paging

• Extreme case – 메모리에 프로세스에 대한 page가 하나도 없는 상태에서 프로세스 시작
  • 페이지를 첫 번째로 액세스할 때 메인 메모리에 없는 것을 확인하고 page fault 발생
    • OS가 프로세스의 첫 번째 instruction으로 instruction 포인터를 설정, non-memory-resident → page fault
    • 처음 액세스할 때 다른 모든 프로세스 페이지에 대해 page fault로 시작
  • Pure demand paging
  • 속도가 매우 느려 미리 예측해 page를 가져오는 것이 필요함
• 주어진 instruction은 여러 페이지에 액세스할 수 있음 → multiple page faults
  • 메모리에서 2개의 숫자를 추가하고 결과를 메모리에 다시 저장하는 instruction의 fetch와 decode를 고려
  • locality of reference으로 인해 pain이 감소 (지역성에 의해 예측)
    • temporal locality (시간), spatial locality (공간) → demand paging에 대한 overhead 감소
• demand paging에 필요한 하드웨어 지원
  • valid / invalid가 있는 page table
  • Secondary memory (swap space가 있는 swap device)
  • Instruction restart

 

Performance of Demand Paging

● Demand Paging 단계 (worse case) - 메인 메모리에 페이지 없음

1. 운영 체제에 대한 trap - interrupt 발생
2. 사용자 레지스터 및 프로세스 상태 저장 (disk로부터 I/O 발생시 CPU가 다른 프로세스에 할당됨) - 메인 메모리에 있는 데이터 스트럭처인 PCB 안에 저장
3. interrupt가 page fault인지 확인
4. 페이지 참조가 legal인지(자신의 페이지인지) 확인하고 disk에서 페이지 위치를 확인
5. disk에서 free frame으로 read (현재는 page replacement 고려 x)
   
   1. read request가 처리될 때까지 이 device waiting queue에서 대기 (disk device가 busy라면 기다림)
   2. device seek 및/또는 latency time(지연 시간) 대기 - secondary storage seek, rotation delay 등 여러가지 내용
   3. free frame으로 페이지 전송 시작
6. 기다리는 동안 CPU를 다른 사용자에게 할당 - running → waiting 상태 (이 동안 CPU는 다른 프로세스에 할당)
7. 디스크 I/O 하위 시스템에서 interrupt 수신 (I/O 완료)
8. 다른 사용자에 대한 레지스터 및 프로세스 상태 저장 - CPU가 돌아와야 하므로 할당되었던 다른 프로세스의 내용을 다른 프로세스의 PCB에 저장
9. interrupt가 disk로부터 발생했는지 확인 - interrupt가 처리되었는지 확인
10. 페이지가 현재 메모리에 있음을 표시하도록 page table 및 기타 tables 수정 - page frame, valid 수정
11. CPU가 이 프로세스에 다시 할당될 때까지 기다림
12. 사용자 레지스터, 프로세스 상태 및 새 페이지 테이블을 복원한 다음 중단된 instruction 재시작 - PCB 내용 레지스터로 복원

 

Performance of Demand Paging (Cont.)

• 3개의 주요 활동
  
  • interrupt 서비스 (무시) – 신중한 코딩은 수백 개의 instruction만 필요로 함
    
  • 페이지 읽기 (많은 시간) - disk로부터 I/O 읽어들이는 시간이 대부분
    
  • 프로세스 재시작(무시) - 짧은 시간에 다시 시작 가능
    
• Page Fault Rate 0 ≤ p ≤ 1
  
  • p = 0 → page fault가 없는 경우 (다 메인 메모리에 존재)
    
  • p = 1 → 모든 참조가 fault (다 page fault)
    
• Effective Access Time (EAT)
  
  • EAT =  (1 – p) x memory access + p (page fault overhead + swap page out + swap page in)

 

Demand Paging Example

• Memory access time = 200 ns
  
• Average page-fault service time = 8 ms
  
• EAT = (1 – p) x 200 + p (8 ms) = (1 – p x 200 + p x 8,000,000) = 200 + p x 7,999,800 ns
  
• 1,000개의 액세스 중 하나가 page fault를 유발하는 경우
  • p = 0.001
  • EAT = 8.2 microseconds = 8200 ns
    
  • 200 ns에서 40배만큼 느려짐
    
• 10% 미만의 성능 저하를 원하는 경우
  
  • 220 > 200 + 7,999,800 x p → 20 > 7,999,800 x p
    
  • p < .0000025
    
  • p < 메모리 액세스 400,000건당 1 page fault

 

Copy-on-Write

• 프로세스 사이의 공유할 수 있는 메모리를 최대한으로 하고, 수정해야 하면 그때 수정되는 부분만 copy하자
• Copy-on-Write (COW) 는 parent와 child processes가 처음에 메모리에서 같은 pages를 공유할 수 있도록 함
  
  • 두 프로세스 중 하나가 공유 페이지를 수정하는 경우에만 페이지가 복사됨
    
• COW를 사용하면 수정된 페이지만 복사되므로 보다 효율적인 프로세스 생성이 가능함
  
• 일반적으로 free pages는 zero-fill-on-demand page pool에서 할당됨
  
  • 빠른 demand page execution을 위해 pool에는 항상 free frames이 있어야 함
    
    • page fault에서 free frames뿐만 아니라 다른 처리를 원하지 않음
      
  • 페이지를 할당하기 전에 페이지를 0으로 설정(zero-out)해야 하는 이유는 무엇인가?
    • zero-out - 새로운 page frame을 새 프로세스에게 할당할 때 zero로 초기화 (page frame을 zero로 초기화  시킨 후 필요할 때 page frame을 할당함)
• fork() 시스템 콜에 대한 변동인 vfork()는 parent를 일시 중단하고 child가 parent의 주소 공간을 copy-on-write 해 사용하게 함
  
  • child call exec()을 사용하도록 설계됨 - child가 자기만의 데이터로 수정할 때 exec()를 이용
    
  • 매우 효율적
• parent, child는 공유하는 같은 부분이 많음
  • if child가 수정 → 공유되는 부분은 최대한 공유, 수정되는 부분을 다른 page frame에 copy

 

Before Process 1 Modifies Page C

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

 

 

After Process 1 Modifies Page C

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 공유되는 부분들은 그대로 두고 한 프로세스가 수정하는 부분만 copy해 자기만의 데이터 써주기
• process2가 page C에 있는 데이터를 copy하여 수정 → Copy of page C
  • free page frame에 필요한 부분만 copy해서 수정 
• 공유하는 메모리를 극대화, 필요한 부분만 copy해 수정하도록 만들어줌
• 똑같은 copy가 여러 개 존재하게 되는 걸 막아줌

 

What Happens if There is no Free Frame?

• 프로세스 페이지에서 모두 사용됨
• 커널, I/O buffers 등의 수요도 있음
  
• 각각 얼마나 할당해야 하는가?
  
• Page replacement – 메모리에 존재하지만 실제로 사용하지는 않는 페이지를 찾아 페이지를 내보냄
  
  • Algorithm – terminate? swap out? replace the page?
    
  • 성능 – 최소 page faults의 수를 산출하는 알고리즘을 원함
    
  • 다음에 사용될 확률이 낮은 page를 교체함
• 같은 페이지가 여러 번 메모리에 저장될 수 있음

 

Page Replacement

• 프로세스에게 필요한 만큼 page frame을 할당해주고 메모리에 여유분이 없을 때 잘 쓰지 않는 페이지를 swap-out 하고 새로운 내용을 swap-in함 → 프로세스에게 큰 page frame이 아니어도 적당히 할당해도 됨
• page replacement를 포함하도록 page-fault service routine을 수정하여 메모리의 over-allocation 방지 (최대 한도 할당 → 비효율적)
  
• modify(dirty) bit를 사용하여 page transfer의 overhead를 줄임 - 수정된 페이지만 디스크에 기록함 (수정되지 않았다면 swap out X, swap in만 함)
  
• modify bit는 page table 안에 있어야 함
• page replacement를 통해 논리 메모리와 물리 메모리 간의 분리가 완료됨 - 더 작은 물리 메모리에 대용량의 virtual memory를 제공할 수 있음

 

Need For Page Replacement

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• page number 3의 M을 불러오기 위해서는 page fault 발생
• physical memory에서 누군가가 swap-out 되고 M이 swap-in 되는 page replacement가 필요

 

Basic Page Replacement

1. disk에서 원하는 page 위치 찾기 - OS가 하는 일
   
2. free frame 찾기
   • free frame이 있으면 사용
   • free frame이 없으면 page replacement algorithm을 사용하여 victim frame 선택
     • dirty인 경우 disk에 victim frame을 쓰기 (swap out 후 swap in)
       
3. 원하는 페이지를 (새) free frame으로 가져옴; page와 frame tables 업데이트
   
4. trap을 발생시킨 instruction을 다시 시작하여 프로세스를 계속함
   

이제 page fault에 대해 2 page 전송 가능성이 있으므로 EAT가 증가

 

Page Replacement

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

1. victim page swap out
2. victim에 대해 valid-invalid bit를 invalid로 바꿈
3. 원하는 페이지 swap in
4. 새로운 페이지에 대해 page table 재설정

 

Page and Frame Replacement Algorithms

• Frame-allocation algorithm은 다음을 결정
  
  • 각 프로세스에 제공할 frames 수 (얼마만큼의 frames를 할당할 것인가)
    
  • 교체할 frames
    
• Page-replacement algorithm
  
  • 첫 번째 액세스와 재액세스 모두에서 가장 낮은 page fault 비율을 원함 (page fault 비율 ↓)
    
• 특정 메모리 참조 문자열(reference string)에서 알고리즘을 실행하고 해당 문자열의 page faults 수를 계산하여 알고리즘을 평가
  
  • 문자열은 page numbers일 뿐 전체 주소가 아님
    
  • 동일한 페이지에 반복적으로 액세스해도 page fault가 발생하지 않음
    
  • 사용 가능한 프레임 수에 따라 결과가 달라짐
    
• 예에서 참조된 페이지 번호의 reference string (참조 문자열: 프로세스가 수행하면서 필요한 페이지 번호)
  
  • 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

 

Graph of Page Faults Versus The Number of Frames

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 가로축: 프로세스에 할당된 page frames
• page frames ↑ → page faults ↓

 

First-In-First-Out (FIFO) Algorithm

• 처음 메모리에 들어온 page를 replacement
• reference string: 7,0,1,2,0,3,0,4,2,3,3,0,3,3,2,1,2,0,1,7,0,1
  
• 3 frames (프로세스당 한 번에 3 pages를 메모리에 저장할 수 있음)
  

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 15 page faults
• reference string에 따라 달라질 수 있음: 1,2,3,4,1,2,5,1,2,3,4,5 고려
  
  • 일반적으로 page frames ↑ → page faults ↓
  • 그러나 FIFO는 frames을 더 추가하면 page faults가 더 많이 발생할 수 있음!
    
    • Belady's Anomaly - page frames ↑ → page faults ↑
      
• 페이지 사용 기간을 추적하는 방법?
  
  • FIFO queue 사용

• FIFO → Belady's Anomaly 발생 가능

 

FIFO Illustrating Belady’s Anomaly

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

 

Optimal Algorithm

• 미래에 사용될 페이지를 놔두고, 사용되지 않을 페이지를 replacement
• 장기간 사용되지 않는 페이지 교체
  
  • 9는 예제에 최적
    
• 문제 → 어떤 페이지가 사용될지 모름
• 알고리즘이 얼마나 잘 수행되는지 측정하는 데 사용됨

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

 

Least Recently Used (LRU) Algorithm

• 지역성에 의해 가까운 과거에 사용되지 않았던 페이지를 교체하자!
• 미래보다는 과거의 지식을 사용
  
• 가장 오랫동안 사용하지 않은 페이지 교체
  
• 각 페이지와 마지막 사용 시간 연결
  

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 12 faults – FIFO보다는 낫지만 OPT보다는 나쁨
  
• 일반적으로 우수한 알고리즘이며 자주 사용됨
  
• 하지만 어떻게 구현해야 할까?

 

LRU Algorithm (Cont.)

• Counter implementation
  
  • 페이지가 사용될 때마다 시간을 counter에 저장해, 가장 적은 시간을 가진 페이지(가장 과거)를 replacement
  • 모든 page entry에는 counter가 있음. 이 entry를 통해 페이지를 참조할 때마다 counter에 시간을 저장
    
  • 페이지를 교체해야 할 경우 카운터를 보고 가장 작은 값을 찾음
    
    • Table search 필요
      
• Stack implementation
  
  • 페이지 번호의 스택을 이중 링크 형식으로 유지:
    
  • 참조된 페이지:
    
    • 그것을 맨 위로 옮김
      
    • 6개의 포인터가 변경되어야 함
      
  • 그러나 업데이트할 때마다 비용이 더 많이 듦
    
  • replacement search 없음
    
• LRU 및 OPT는 Belady's Anomaly가 없는 stack algorithms의 사례임

 

Use Of A Stack to Record Most Recent Page References

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

 

LRU Approximation Algorithms

• LRU에는 특수 하드웨어가 필요하고 여전히 느림 (overhead 존재)
• Reference bit
  • page table에 추가
  • 각 페이지와 연관된 bit는 초기에 = 0
    
  • 페이지가 참조될 때 bit가 1로 설정됨 (페이지가 메인 메모리에 들어와서 access 될 때마다 1로 설정)
    
  • reference bit = 0 (존재하는 경우)인 어떤 것을 교체
    
    • 하지만 우리는 순서를 모름!
      
• Second-chance algorithm
  • 일반적으로 FIFO + 하드웨어 제공 reference bit
    
  • Clock replacement
    
  • 교체할 페이지가 다음과 같은 경우
    
    • Reference bit = 0 → 교체
      
    • Reference bit = 1 라면:
      
      • reference bit를 0으로 설정, 메모리에 페이지 남기기
        
      • 다음 페이지 교체, 동일한 규칙 적용

 

Second-Chance (clock) Page-Replacement Algorithm

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• reference bit = 1인 페이지를 0으로 바꾸고 기회 한 번 더 줌

 

Enhanced Second-Chance Algorithm

• reference bit와 modify bit (사용 가능한 경우)를 사용하여 알고리즘 개선
  
• 순서가 지정된 쌍 가져오기 (reference, modify)
  
• 모든 페이지가 가지는 형태

1. (0, 0) 최근에 사용되지 않음, 수정됨
   • 교체하기에 가장 좋은 페이지 (replacement 1순위)
     
2. (0, 1) 최근에 사용되지 않았지만, 수정됨
   • 그다지 좋지 않음, 교체하기 전에 swap out하여 disk에 쓰고 swap in 해야함
     
   • 메인 메모리에 페이지 들어와 사용되면서 일정 시간이 지나면 reference = 1로 바뀜 → 주기적으로 reference bit를 clear 시켜줘서 reference = 0이 됨
   • modify bit는 clear하지 않음! (메인 메모리에만 수정된 데이터가 존재하므로)
3. (1, 0) 최근에 사용되었지만, 수정되지 않음 (clean)
   • 아마도 곧 다시 사용될 것
     
   • 사용될 확률 ↑ (가까운 과거에 사용됨)
4. (1, 1) 최근에 사용 및 수정
   • 아마도 곧 다시 사용될 것이며 교체하기 전에 swap out하여 disk에 쓰고 swap in 해야함
     
   • 사용빈도가 높음

• 페이지 교체가 필요한 경우 clock 방식을 사용하지만 비어 있지 않은 가장 낮은 클래스에서 4개의 클래스 교체 페이지를 사용
  
  • circular queue을 여러 번 검색해야 할 수 있음

 

Thrashing

• page faults가 너무 자주 일어나는 것
• 근본적인 이유: 프로세스에 할당된 page frame 개수가 적기 때문에 발생
• 프로세스에 "충분한" 페이지가 없으면 page-fault rate가 매우 높음
  
  • page fault로 페이지를 가져옴
    
  • 기존 frame을 교체
    
  • 그러나 금방 교체된 프레임을 다시 필요로 함 (swap out한 애가 또 필요해서 swap in 되는 과정 반복)
    
  • 이로 인해 다음과 같은 결과가 초래됨
    
    • 낮은 CPU 활용률 (CPU 효율 ↓ 대부분 I/O)
      
    • OS는 multiprogramming의 정도를 높여야 할 필요가 있다고 생각함
      
    • 시스템에 다른 프로세스가 추가됨
      
• Thrashing → 프로세스가 페이지를 안팎으로 교환하느라 바쁨

 

Thrashing (Cont.)

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• CPU 효율도 떨어짐 (thrashing - 필요한 부분이 모두 page faults 발생)
• 메인 메모리에 있는 프로세스의 개수 = degree of multiprogramming
• 메인 메모리에 있는 프로세스의 개수 ↑ → 프로세스에게 할당되는 페이지 프레임 개수 ↓ (어느 정도까지는 괜찮지만 필요한 부분들이 모두 다 page faults가 일어난다면 thrashing)
• 해결 방법
  • 프로세스에게 할당되는 page frames 개수를 늘려줘야함
  • 메인 메모리에 있는 프로세스 개수 ↓ (multiprogramming의 정도 ↓) → 각 프로세스에 할당되는 page frames 개수 늘어남! → 해결

 

Buddy System

• 메모리를 할당할 때 프로세스가 필요한 메모리의 가장 가까운 2의 power로 할당
• 똑같은 크기로 할당된 이웃한 메모리가 free될 때 두 메모리가 merge → free page frames
• 물리적으로 연속되는 페이지로 구성된 fixed-size segment에서 메모리 할당
  
• power-of-2 allocator를 사용하여 할당된 메모리
  
  • 2의 거듭제곱으로 크기가 지정된 단위로 요청을 충족
    
  • 요청을 다음으로 높은 2의 거듭제곱으로 반올림함
    
  • 사용 가능한 것보다 더 적은 할당이 필요한 경우, 현재 청크는 2의 다음으로 낮은 지수의 두 개의 버디로 분할됨
    
    • 적절한 크기의 청크를 사용할 수 있을 때까지 계속함
      
• ex) 256KB 청크를 사용할 수 있고 커널이 21KB를 요청한다고 가정
  
  • 각각 128KB의 AL 및 AR로 분할
    
    • 하나는 64KB의 BL과 BR로 더 나뉨
      
      • 각각 32KB의 CL 및 CR에 한 번 더 나눠짐 - 이중 하나가 요청을 충족하는 데 사용
        
• 장점 – 사용하지 않는 청크를 더 큰 청크로 신속하게 통합(coalesce)
  
• 단점 - fragmentation
  • ex) 한 프로세스가 17KB가 필요하다면 32KB에 들어가야 함 → 15KB만큼의 fragmentation 발생

 

Buddy System Allocator

Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne

• 같은 크기의 이웃한 chunk가 free 되면 merge 가능
• ex) 100KB가 필요한 프로세스 → 128KB에 할당
• ex) 21KB, 30KB가 필요한 두 프로세스 → 32KB에 할당
  • 21KB가 필요한 프로세스가 종료되어 free되더라도 30KB가 필요한 프로세스는 아직 사용 중이라 merge 안 됨
  • 30KB가 필요한 프로세스가 종료되면 똑같은 크기의 이웃한 memory chunk가 merge → 64KB가 됨
  • 64KB + 64KB → 128KB
  • 100KB가 필요한 프로세스가 종료되면 128KB + 128KB → 256KB가 됨

 

 

 

 

 

 

참고 자료 : Operating System Concepts - 10th edition, Sliberscahatz, Galvin and Gagne