8강

• TLB : pagetable에서 자주사용하는 PTE를 저장하는 버퍼 (캐시처럼)
  • 공간적 지역성, 시간적 지역성 활용
  • TLB miss
    • CISC → HW handle (walk : 테이블에 갱신후 다시 접근) / RISC → SW handle(Trap handler)
  • TLB Entry
    • 병렬로 구성되어 있고, valid bits, protection bits, address-space identifier, dirty bit 구성
    • context switch를 할 때 TLB에서 혼동이 발생(VPN같음)하지 않도록 ASID를 이용한다.
    • PFN이 같다면 메모리 공간을 확보할 수 있다!
  • TLB의 교체 정책 : LRU

9강

• Page Table의 크기는 Page 사이즈에 의해 결정된다.
  • 전체 공간 / Page size ⇒ page의 개수 = page entry의 개수 → page entry 개수 * 4(페이지 엔트리 크기) ⇒ page table의 전체 공간의 크기
    • 페이지의 크기가 작으면 페이지 테이블이 커져서 메모리(공간)를 많이 사용하고, 페이지 크기가 크면 내부단편화가 발생한다.
• Page table에 사용하지 않는 엔트리가 많다. (공간 낭비)
  • 해결법
    • paging과 segments
      • 모든 entry를 공간으로 만들지 말고, segment처럼 사용하는 공간만 메모리 할당
      • Page의 비트표현에서 맨 앞의 2비트를 segment bit로 나타낸다.
        • 00 → 사용하지 않는 세그먼트, 01 → code, 10 → heap, 11 → stack
      • page의 segment bits(SN)을 보고 base-bound 쌍을 결정하고, pagetable의 VPN과 계산하여 실제 물리주소를 얻는다.
      • 하지만 이 방법도 문제가 있다 : 외부단편화
    • Multi-level Page Table : page table에서 사용하지 않는 공간은 메모리에서 제거!
      • Page directory : page table을 page의 단위로 자른 후에 page table의 각각의 page를 참조하는 page directory entry를 여러개 담은 구조를 의미한다.
        • page 단위에서 1개의 page table entry라도 사용중이라면 해당 page table의 page directory entry의 valid bit을 1로 set!
          • valid bit이 0이라는 것은 접근할 수 없는 즉, 프로세스에 의해 할당되지 않아 접근할 수 없는 상태를 의미한다. ⇒ segmentation fault!
      • 장점 : 실제 pagetable이 사용하는 공간만 할당
      • 단점 : 메모리 접근을 기존에 2번에서 3번을 허용하게 됨 → 시간과 공간의 상충 문제
      • page 단위로 나눠진 page table의 수 = page directory entry의 수
        • page의 수와 page entry의 수가 같아야하는 점을 이용하여 잘 계산하기
        • vpn = page directory entry bit + page table entry bit
    • More than Two Level : directory를 또 다른 directory로 층을 만들어서 연결 → page directory index가 0 / 1로 나뉨
    • Inverted Page Tables
      • 프로세스마다 page table이 1개씩 존재하는 것이 아니라, 모든 프로세스가 1개의 pagetable을 공유하는 방법
      • 더 자세한 정보를 담아내야함, But page table의 메모리 사용을 줄일 수 있음

10강

• 메모리 계층

• Swap space (Disk, file..)
  • 메모리의 공간보다 더 큰 공간이 필요할 때 사용되고, page 크기 단위로 저장된다.
  • present bit : memory에 있으면 1, disk에 있으면 0
  • 메모리가 full일때, 새로운 페이지를 물리주소로 변환시켜야 할 때 → page-replacement
    • Segmentation fault : 할당된 범위를 벗어난 접근 (valid = 0)
    • Page fault : 할당됐지만 메모리에 올라와 있지 않고 Swap space에 존재할 때 접근 (valid = 1, present = 0)
• Page fault
  • page fault는 page가 물리주소(memory)에 올라와 있지 않아서 OS가 disk에서 page를 가져와 메모리에 할당하고, present bit를 1로 업데이트 + TLB도 업데이트 → 다음 접근은 TLB로!
    • OS는 페이지폴트 발생시 희생시킬 페이지 찾음
  • Page replacement : swap daemon에 의해서 처리된다. daemon은 free page의 개수를 세는 역할을 하고, LW(low-watermark) 이하 or HW 이상이 되면 대몬이 victim 발생시킨다!
  • Page replacement 정책
    • 캐시 replacement 정책과 매우 유사하다.
      • 처음 배치될 때의 miss를 **compulsory miss(강제 미스)**라고 한다.
      • BELADY’S ANOMALY : 캐시의 자리가 증가해도 Hit rate가 항상 증가하는 것은 아니다.
    • Page를 replacement한다는 얘기는 page가 present되지 않았기에 하는 것이다. 즉, pagefault가 발생한다.
    • 방법 : FIFO, Random, LRU
      • 지역성이 없는 작업량에서는
        • FIFO = LRU = RAND
          • 입력을 모르기에 셋 다 같아진다.
      • The 80-20 Workload (자주 사용하는 페이지가 80%를 차지한다. 나머지가 20%)
        • FIFO = RAND < LRU
          • 자주 사용되는 page에 의해 LRU가 hit확률이 올라간다.
      • (시험) The Looping Sequential / N = 50(반복되는 순서) ex) 0,1,2,…49,0,1,2,…49~
        • LRU = FIFO = 0%, RAND = 정비례, 자리(block)수가 50이상부터는 셋 다 100%
          • LRU : 다들 1번씩 순차적으로 나오기에 가장 처음에 넣었던게 희생됨 (FIFO)
            • 그러면 무조건 0%가 나옴
    • LRU를 조금 더 잘 사용할 수 없을까?
      • HW의 도움을 받자 : page 접근한 시간을 타임스탬프로 → But 자원 많이 소모..
        • HW의 지원 : use bit(Reference bit, R bit)을 사용하자. (타임스탬프 느낌)
      • 접근될때 마다 R bit을 1로 바꿈 (즉, 0은 “나 최근에 사용안했어!”)
        • 희생할 페이지를 고르는 기준 : 0이면 희생할 페이지로 고름, 1이면 0으로바꾸고 다음 넘어감 → 모든 페이지를 돌면서 과정 반복(모든 페이지를 초기화하는 방법)
      • 이 R bit을 사용한다면(Clock), 80-20 workload에서 FIFO = RAND < Clock < LRU 된다.
        • 완벽한 LRU에 거의 근접한 성능을 보임
    • Dirty bit
      • D bit : 메모리에서 수정되었다면 1, 수정되지 않았다면 0
        • 메모리에서 값이 변경되었다면 victim시킬때 디스크에 저장되어 있던 값과 다를테니까 디스크에 저장해준다. 변경되지 않았다면 victim시킬때 discard해버림
    • OS는 page를 가져올 시기도 정해야함
      • Prefetching 예측하여 가져오는 것 (기존은 demand 수요 paging)
        • 즉, 같이 사용될 것 같은 애들을 같이 데려옴
      • Clustering, Grouping 클러스터링
        • Write buffer를 이용해서 victim시킬때 buffer에 넣어놓고 한번에 보낸다. (disk의 free space 공간만큼만)
      • (시험) Thrashing : 여러 프로세스들로 하여금 요구되는 메모리의 크기가 실제 메모리의 크기보다 큰 경우
        • context switch 될때마다 page fault 계속 발생 ! (CPU의 부담이 커진다.)
          • 해결책
            1. page fault를 발생시키는 하위 프로세스를 종료한다.
            2. 메모리가 과부하를 겪지 않도록 프로세스의 수를 감소시킨다.

11강

• Thread
• 멀티 스레드
• Race condition 경쟁상태
• Critical Section 임계영역
• pthread_create : fork와 같음, 스레드 생성 / pthread_join : wait와 같음, 스레드 실행이 끝날때까지 기다림
• Lock : 상호배제를 위한 수단
• Condition Variables 조건 변수

12강