운영체제 ③ (KOCW 반효경 교수님 강의)

http://www.kocw.net/home/search/kemView.do?kemId=1046323

운영체제

 

 

이 글은 반효경 교수님의 강의를 듣고 잊지않고 공부하기 위해 작성되었다. 

 

 

 

Ch.8 Memory Management

출처 KOCW 반효경 교수님 수업 자료

• Logical address( = virtual address, 가상주소, 논리주소)
  • 프로세스 마다 독립적으로 가지는 주소공간

출처 KOCW 반효경 교수님 수업 자료

출처 KOCW 반효경 교수님 수업 자료

• Physical address (물리주소) 
  • 메모리에 실제 올라가는 위치 
  • 할당 
    • OS 상주 영역 : interrupt vector와 함께 낮은 주소 영역 사용 
    • 사용자 프로세스 영역 : 높은 주소 영역 사용 
      • Contiguous allocation : 각각의 프로세스가 메모리의 연속적 공간에 적재되도록(통채로), 할당공간 및 가용공간(hole)을 유지 
        • 방식  
          • Fixed partition allocation : 고정 분할 방식 
            • 물리적 메모리를 몇개의 영구적 분할로 나눔 
            • 분할 크기가 모두 동일한 방식과 다른 방식이 존재 
            • 분할당 하나의 프로그램 적재 
            • 융통성이 없어 동시에 메모리에 load 되는 프로그램 수가 고정 되어 최대 수행 가능 프로그램 크기 제한
            • Internal fragmentation(내부 조각) + external fragmentation(외부 조각)발생 
          • Variable partition allocation : 가변 분할 
            • 프로그램의 크기를 고려하여 할당 
            • 분할의 크기 개수가 동적으로 변화
            • 기술적 관리 기법 필요
            • External fragmentation 발생
        • Hole 해결 방안 
          • Dynamic Storage-Allocation Problem 
            • 가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제
            • Firstfit, Bestfit이 Worstfit 보다 속도와 공간 이용률 측면에서 효과적인 것으로 알려짐   
            •  방식 
              • FIrstfit
                • Size n 이상인 것 중 최초로 찾아지는 hole에 할당 
              • Bestfit
                • Size n 이상인 것 중 가장 작은 hole을 찾아 할당 (가장 맞는)
                • Hole이 크기순으로 정렬되지 않은 경우 모든 Hole 리스트를 탐색 
                • 많은 수의 아주 작은 Hole 들이 생성됨 
              • Worstfit
                • 모든 리스트를 탐색하여 가장 큰 Hole에 할당 
                • 상대적으로 아주 큰 hole들이 생성 
          • compaction
            • external fragmentation 문제를 해결하는 한가지 방법 
            • 사용중인 메모리 영역을 한군데로 몰고 hole들을 다른 한 곳으로 몰아 큰 block 만들기 
            • 매우 비용이 많이 든다 (힘들다)
            • 최소한의 메모리 이동으로 compaction하는 방법(매우 복잡)
            • 프로세스의 주소가 실행시간에 동적으로 재배치가 가능한 경우에만 사용 가능 (변경가능)
      • Noncontiguous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음 (현대 사용 많음) 
        • Paging
          • 프로세스의 가상 메모리를 동일한 사이즈의 page단위로 나눔 
          • 일부는 backing storage, 일부는 물리 메모리에 저장 
          • 일정크기로 잘라놓기 때문에 hole걱정이 없음 (대신 주소 변환 페이징 별로 바인딩 어려움)
          • 방법 
            • 물리 메모리를 동일한 크기의 frame으로 나눔 
            • 논리 메모리를 동일 크기의 page로 나눔(frame 크기)
            • 모든 가용 frame들을 관리 
            • 페이지 테이블(어디로 올라가는지 표시(프레임위치), 메인 메모리에 상주)을 사용하여 논리 주소를 물리 주소로 변환 
              • Page-table base register(PTBR)가 페이지 테이블을 가리킴
              • Page-table length register(PTLR)가 테이블 크기를 보관 
              • 모든 메모리 접근 연산에는 2번의 메모리 접근 필요 (page table, 실제 data/instruction)
              • 속도 향상을 위해서 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup 하드웨어 캐시 사용 
                • Associative register 
                  • parallel search가 가능 
                  • 페이지 테이블 중 일부만 존재 
                  • 주소 변환 시 페이지 테이블 중 일부가 Associative register에 보관되어 있는 경우 곧바로 frame 을 얻지만 없는 경우 메인 메모리에 있는 페이지 테이블 로 부터 frame을 얻음 
                  • TLB는 프로세스마다 다르기 때문에 context switch때 flush 된다 (remove old entries)
            • External fragmentation 발생 X
            • Internal fragmentation 발생 O
            • 프로그램 마다 용량 큰 페이지 테이블이 메모리에 존재 (프레임을 알기위해서 및 데이터 접근)
            • Two-Level Page Table
              • 현대의 컴퓨터는 주소 공간이 매우 큰 프로그램을 지원한다 
              • page 사이즈가 4K 시 1M개의 페이지 테이블 엔트리 필요 
              • 그러나 대부분의 프로그램은 4G의 주소공간 중 지극히 일부만 사용하여 page table 공간이 심하게 낭비된다 
              • 페이지 테이블 자체를 페이지로 구성하여 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값을 null로 입력 (대응하는 inner page table없음)
              • 시간은 더 걸려도 공간의 사용은 작다 
            • Multilevel Pageing and Performance
              
              • 주소공간이 더 커지면 다단계 페이지 테이블이 필요 
              • 논리 주소에서 물리주소 변환시 더많은 메모리 접근이 필요 
              • 캐시 메모리를 통해 메모리 접근 시간을 줄일 수 있다 
            • Inverted Page Table
              • 페이지 프레임 당 페이지 테이블에 하나의 entry를 둔 것 (system-wide)
              • 각 페이지 테이블 entry는 각가의 물리적 주소의 page-frame이 담고 있는 내용을 표시한다 (process id, process의 논리주소)
              • 테이블 전체를 탐색해야만 한다 (조치 : associative register(비쌈)를 사용)
              • <-> 기존의 페이지 테이블 : 논리 주소에 대응하느 모든 페이지에 대해 페이지 테이블 엔트리가 존재하기 때문에 페이지 테이블의 크기가 크다 
            • Shared Page
              • Shared code 
                • Re-entrant Code( = Pure code)
                • 1) Read-Only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (ex)텍스트에디터, 컴파일러들, 윈도우 시스템)
                • 2) Shared code는 모든 프로세스의 논리 주소 공간(&& 동일 물리 주소)에서 동일한 위치에 있어야 한다 
                • Private code and data
                  • 각 프로세스들은 독자적으로 메모리에 올린다 
                  • 개인 데이터는 논리 주소 공간의 아무곳에 와도 무방하다 
            • 메모리 보호 : 페이지 테이블의 각 entry마다 다음의 bit를 둔다
              • Protection bit : 페이지 연산에 대한 접근 권한 (read/write/read-only) 
              • Valid-invalid bit : 해당주소의 frame에 그 프로세스를 구성하는 유효한 내용의 유무 
                • 없는 경우(invalid) 
                  • 프로세스가 그 주소 부분을 사용하지 않는 경우 
                  • 해당 페이지가 메모리에 올라와 있지 않고 swap out한 경우 
        • Segmentation
          • 의미있는 단위로 잘라 크기가 균일하지 않음 -> Hole 발생 가능성 있음 
          • 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능 
          • 일반적으로는 code, data, stack부분이 하나씩의 세그먼트로 정의됨 
          • 논리 주소는 두가지로 구성 <segment-number, offset>
          • Segment table
            • base - 시작점 (물리주소의)
            • limit - 세그먼트 길이(offset) 
          • Segment-table base register(STBR)
            • 물리적 메모리에서의 segment table의 위치 (시작위치)
          • Segment-table length register(STLR)
            • 프로그램이 사용하는 segment의 수 
            • segment number는 STLR보다 작을 때 유효하다(넘으면 잘못된 요청)
          • Protection
            • 각 세그먼트 별로 protection bit 보유 
            • Valid, Read/Write/Execution 권한 bit
          • Sharing 
            • shared segment : 같은 논리 물리 메모리 
            • same segment number 
            • segment는 의미 단위이기 때문에 공유와 보안에 있어 페이징보다 훨씬 효과적
          • Allocation 
            • firstfit/bestfit
            • 세그먼트의 길이가 일정하지 않기 때문에 external fragmentation (hole) 발생 가능 
        • Paged Segmentation
          • segment-table entry가 segment의 base address를 가지고 있는 것이 아닌 segment를 구성하는 page table의 base address를 가진다. 
• 주소 바인딩
  • 주소를 결정하는 것 (어디로 올라갈지) (주요문제 : Logical-> Physical 단계가 언제 이루어지는가?)
  • Symbolic Address(변수/함수 이름만 주고 실질적 주소 X) -> Logical Address -> Physical Address
  • 주소변환은 운영체제가 아닌 하드웨어의 역할 (프로세스가 CPU 가지면서 메모리에 접근(운영체제 X)<-> I/O장치는 운영체제 접근)
  • Compile time binding 
    • 물리적 메모리 주소 (physical address)가 컴파일시 알려짐 
    • 시작위치 변경시 재컴파일 
    • 컴파일러는 절대 코드(absolute code)생성
  • Load time binding
    • Loader의 책임하에 물리적 메모리 주소 부여 
    • 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능
  • Execution time binding( = Runtime binding) 현대컴퓨터 
    • 수행이 시작된 이후에도 프로세스의 메모리상 위치를 변경 가능 
    • CPU가 주소를 참조할 때 그때그때 마다 binding을 점검 (address mapping table)
    • 하드웨어 적인 지원이 필요  
    • MMU(Memory Management Unit)
      • 논리주소를 물리주소로 매핑해주는 하드웨어 장치 (register 두개를 이용) 
      • scheme
        • 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 base register(=relocation register)의 값을 더한다 
      • 사용자 프로그램 
        • 논리 주소만을 다룬다 (실제 물리 주소에 대해서는 알 필요가 없음)
    • CPU가 요청하는 주소(논리주소)-> 요청이 오면 물리적환 주소 획득 -> 요청 전달 -> CPU에 값 전달 

출처 KOCW 반효경 교수님 수업 자료

• Dynamic Loading ( 동적할당 != 지금의 phasing 시스템)
  • 프로세스를 필요할때 (해당루틴이 불려질때) 메모리에 load
  • memory utilization 향상 
  • 가끔씩 사용되는 많은 양의 코드의 경우 유용 
  • 운영 체제의 특별한 지원 없이 프로그램 자체에서 구현이 가능 (OS는 라이브러리를 통해 지원 가능)
• Overlays 
  • 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림 (초창기에 메모리가 작아서 나눠서 올리던 것을 프로그래머 수작업으로 => Manual Overlay)
  • 프로세스의 크기가 메모리보다 클 때 유용
  • 운영체제의 지원 없이 사용자에 의해 구현
  • 프로그래밍이 매우 복잡

출처 KOCW 반효경 교수님 수업 자료

• Swapping 
  • 프로세스를 일시적으로 메모리에서 backing store(디스크 = swap area)로 쫓아내는 것 
  • Swap in / Swap out
    • 일반적으로 중기 스케줄러에 의해 swap out 시킬 프로세스가 선정된다 
    • priority based CPU scheduling algorithm
    • Compile time 혹은 load time binding에서는 쫓겨나도 원래 메모리 위치로 swap in 해야한다(변경 불가능)
    • Execution time binding에서는 추후 빈 메모리 영역 아무데나 올리 수 있다 (변경 가능)
    • swap time은 대부분 transfer time(swap 되는 양에 비례하는 시간)임
      • head가 이동하는 시간이 대부분이며 transfer time은 미미한 시간이다 (많이 swap하면 시간이 걸리긴 하지만)
• Dynamic Linking
  • 연결 시간을 실행시간 까지 미루는 기법 
  • 라이브러리가 실행 시 연결 (컴파일 포함 X)
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴 ( shared Library)
  • 운영체제의 도움이 필요 
  • <-> static linking
    • 라이브러리가 프로그램의 실행 파일 코드에 포함됨
    • 실행 파일의 크기 커짐
    •  동일한 라이브러리를 각각의 프로세스가 메모리에 올려 메모리 낭비(프로그램의 주소 공간 안에서 실행)

 

 

Ch.9 Virtual Memory(운영체제의 개입 O)

출처 KOCW 반효경 교수님 수업 자료

• Demand Paging
  • 실제로 필요할 때 page를 메모리에 올리는 것 
  • I/O의 양 감소
  • Memory 사용량 감소 
  • 빠른 응답 
  • 더 많은 사용자 수용 
  • Valid/Invalid bit의 사용 
    • 처음에는 모든 page entry가 invalid로 초기화 
    • address translation 시에 invalid bit가 set 되어있으면 page fault(요청한 페이지에 정보가 없음-> Trap -> CPU -> 운영체제 -> fault난 페이지 올림)
    • Page fault 
      • 1) invalid 페이지 접근 
      • 2) MMU가 trap 발생 (page fault trap)
      • 3) 커널 모드에서 page fault handler가 실행됨
      • 4) 잘못된 레퍼런스 인지 확인(잘못된 주소 또는 권한 보호 위반 등) 후 잘못된 요청이면 프로세스를 버린다
      • 5) 비어있는 페이지 프레임을 획득(없으면 replace(쫓아낸다))
        • 곧바로 사용되지 않을 페이지를 쫓아내는 것이 좋다 
        • 동일한 페이지가 여러번 메모리에서 쫓겨났다가 다시 들어올 수 있다 
        • Replacement Algorithm
          • page fault rate를 최소화 하는 것이 목표 
          • Optimal Algorithm (= offline optimal algorithm)
            • 가장 먼 미래에 참조되는 페이지를 replace(실제로는 알기 어렵지만 안다고 가정)
            • 다른 알고리즘의 성능에 대한 upper bound를 제공한다 
            • Belady's optimal algorithm, MIN, OPT
          • FIFO(FIrst IN First Out) Algorithm
            
            • 먼저 들어온 것을 먼저 내쫓음 
            • FIFO Anomaly(Belady's Anomaly)
            • 메모리를 늘리면 성능이 줄어든다 
          • LRU(Least Recently Used) Algorithm (가장 많이 쓰임)
            • 가장 오래전에 참조된 것을 지움 
          • LFU(Least Frequently Used) Algorithm
            • 참조횟수가 가장 작은 페이지를 지움 
            • 최저 참조 횟수인 페이지가 여럿있는 경우 임의로 선정하거나 성능 향상을 위해서 가장 오래전에 참조된 페이지를 지우게 할 수 있음 
            • LRU 처럼 작지거인 시간 규모를 보지만 최근성을 반영하지 못하고 구현이 어려움 
      • 6) 해당 페이지를 디스크에서 메모리로 읽어온다 (오래걸림)
        • disk I/O가 끝날 때까지 이 프로세스는 CPU를 선점 당함(block)
        • dist read 가 끝나면 페이지 테이블 엔트리 기록, valid/invalid bit = 'valid'
        • 대기열에 프로세스를 삽입 -> dispatch
      • 7) 이 프로세스가 CPU를 잡고 다시 running
      • 8)중단되었던 instruction 재게 
• 캐시 
  • 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로 부터 직접 서비스 
  • paging system, cache memory, buffer caching, web caching 
  • 시간 제약 
    • 교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 시제 시스템에서 사용할 수 없음 
    • Buffer caching || Web caching 
      • O(1)에서 O(logN)정도까지 허용
    • page system
      • 제약조건이 더 많으며 page fault인 경우에만 OS가 관여된다 (swap발생 때문에 시간이 오래걸릴 수 있다)
      • 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS는 모른다(CPU에게 물어봤을 때만 알 수 있고 메모리는 모른다)
      • O(1)인 LRU의 리스트 조작조차 불가능 
• Clock Algorithm
  • LRU의 근사 알고리즘 ( = Second chance algorithm, NUR(Not Used Recently) 또는 NRU(Not Recently Used))
  • reference bit를 사용해서 교체 대상 페이지 선정 (circular list)
  • 레퍼런스 비트가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동 
  • 0인것을 찾으면 페이지 교체 
  • 한바퀴 되돌아 와서도 (second chance) 0 이면 그때에는 replace 단한다 
  • 자주 사용되는 페이지라면 second chance가 올때 1
  • 개선 
    • reference bit와 modified bit(dirty bit)를 함께 사용
    • reference bit = 1 : 최근에 참조된 페이지 
    • modified bit = 1 : 최근에 변경된 페이지(우선순위가 낮다, I/O를 동반하는 페이지) 
• Page Frame Allocation : 각 프로세스에 얼만큼의 페이지 프레임을 할당할 것인가  
  • 필요성
    • 메모리 참조 명령어 수행시 최소한 할당되어야 하는 프레임 수가 있음 
    • loop를 구성하는 페이지들은 한꺼번에 할당되는 것이 유리하며 최소한의 할당이 없으면 매 loop 마다 page fault가 발생하게 된다. 
  • scheme
    • Equal allocation
      • 모든 프로세스에 똑같은 갯수 할당 
    • Proportional allocation
      • 프로세스 크기에 비례하여 할당 
    • Priority allocation
      • 프로세스의 priority에 따라 다르게 할당 
• Replcement
  • Global Replacement : 페이지가 필요로 하는 만큼 할당 (경쟁)
    • 대체 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있다 
    • 프로세스별 할당량을 조절하는 또다른 방법
    • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당 
    • Working set, PFF 알고리즘 사용
  • Local Replacement : 자신에게 할당된 페이지를 퇴출 
    • 자신에게 할당된 프레임 내에서만 대체
    • FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시
• Thrashing
  • 프로세스의 원할한 수행에 필요한 최소한의 페이지 프레임 수를 할당받지 못하면 발생 
  • page fault rate가 매우 높아짐 
  • CPU 이용도 낮아짐 
  • OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
  • 또다른 프로세스가 시스템에 추가됨(higher MPD)
  • 프로세스당 할당된 프레임 수가 더욱 감소
  • 프로세스는 페이지의 swap in /swap out으로 매우 바쁨
  • 대부분의 시간에 CPU는 한가하다 
  • low throughput
•  Working set model 
  • Locality of reference
    • 프로세스는 측정 시간 동안 일정 장소만을 집중적으로 참조
    • 집중적으로 참조되는 해당 페이지들의 집합을 loclity set이라고 지칭
  • Localit에 기반하여 프로세스가 일정 시간동안 원할하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합
  • 프로세스의 working set전체가 메모리에 올라와 있어야 하고 그렇지 않으면 모든 프레임을 반납한 후 swap out (suspend)
  • Thrashing을 방지 
  • Multiprogramming degree를 결정 
  • working set algorithm
    • working set window를 통해 알아냄 
    • 프로세스들의 working set 사이즈의 합이 페이지 프레임의 수보다 큰 경우 일부 프로세스를 swap out시켜 남은 프로세스의 working set을 우선적으로 충족(MPD 줄임)
    • working set을 다 할당하고도 페이지 프레임이 남는 경우 swap out 되었던 프로세스에게 working set을 할ㄷ아 (MPD를 키움)
  • window size 
    • 너무 작으면 locality set 수용 불가 
    • 너무 크면 여러 규모의 locality set 수용 
    • 무한대면 전체 프로그램을 구성하는 페이지를 working set으로 간주 
  • PFF(Page Fault frequency) Scheme
    • page Fault Rate의 상한값과 하한값을 두고 넘으면 frame 더할당, 이하이면 할당 프레임 수 줄임 
    • 빈 프레임이 없으면 일부 프로세스를 swap out
  • page size의 결정 
    • 페이지 사이즈 감소시 
      • 페이지 수 증가 
      • 페이지 테이블 크기 증가 (entry수가 증가하기 때문)
      • Internal fragmentation 감소
      • Disk transfer의 효율성 감소(seek/rotation vs transfer)
      • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 (Locality 활용 측면에서는 좋지 않다(순차찾기 어려움)
      • 최신 트랜드는 큰 페이지 사이즈