운영체제 기말 파트 정리본

밈무·2022년 5월 24일
운영체제
0


(이화여자대학교 권진욱 교수님의 수업을 듣고 기말 시험 부분을 간략히 정리한 정리본입니다.)

ch06 Process Synchronization

  1. Synchoronization의 전형적인 문제들(33p)

    • 종류
      1. Bounded-Buffer Problem(Producer-Consumer Problem)
      2. Readers and Writers Problem
      3. Dining-Philosophers Problem
    • Bounded-Buffer Problem(Producer-Consumer Problem)
      • producer를 consumer가 쫓아가면서 생산, 소비
      • Producer
        1. Empty 버퍼가 없으면 기다림
        2. 공유데이터에 lock 걺(전체에 lock 걺)
        3. Empty buffer에 데이터 입력 및 버퍼 조작
        4. unlock
        5. full buffer ++
      • Consumer
        1. full 버퍼 없으면 기다림
        2. 공유데이터에 lock
        3. full buffer에서 데이터 꺼내고 버퍼 조작
        4. unlock
        5. empty buffer ++
      • shared data
        • buffer 자체 및 buffer 조작 변수(empty/full buffer의 시작 위치)
      • Synchronization variables
        • mutual exclusion : 한번에 하나의 process만 접근 가능하도록 제어하는 세마포어 필요 → binary semaphore (공유 데이터의 mutual exclusion을 막기 위해)
        • resource count : 남은 full/empty buffer의 표시 → integer semaphore
    • Readers-Writers Problem
      • 특징
        • write : 한 process만 DB에 접근 가능
        • read : 동시에 여럿이 해도 됨 (차이점)
        • starvation 발생 가능
      • solution

        1. writer가 DB에 접근 허가를 얻지 못했다면 모든 대기중인 reader들 다 DB에 접근 가능(Writer가 DB에서 빠져나가야만 Reader의 접근 허용)

        2. Writer는 대기 중인 Reader가 하나도 없을 때 DB 접근 가능

          → if(readcount==1) P(db) : block writer(1개일 때만 db에 세마포어, 1초과일 땐 이미 걸려있는 상태라)

          ...

          if(readcount==0) V(db) : enable writer(하나도 안 남았을 때만 세마포어 풀림)

        3. Writer가 DB에 접근 중이면 Reader들 접근 금지

      • Shared data
        • DB 자체
        • readcount(현재 DB에 접근 중인 Reader의 수 (reader가 없어야 writer 접근이 가능하므로)
      • Synchronization variables
        • mutex (공유변수 readcount를 접근하는 코드(critical section)의 mutual exclusion보장)
        • db(공유 db에 올바르게 접근)
    • Dining-Philosophers Problem
      1. 왼 → 오른
        • 문제점 : Deadlock의 가능성(모든 철학자가 동시에 왼쪽 젓가락을 집어든 경우)
        • 해결
          1. 젓가락 개수 - 1 명의 철학자만 테이블에 앉도록
          2. 젓가락을 두개 모두 집을 수 있을 때만 젓가락 들게 ( p(c[i])와 p(c[(i+1}%n]) 동시에 수행)
          3. 비대칭
            • 짝수 철학자는 왼쪽 젓가락부터 집도록
            • 홀수 철학자는 오른쪽 젓가락부터 집도록
      2. 해결책
        1. 젓가락 두개 모두 집을 수 있을 때만
          • semaphore self[5]=0
            • pickup : P(self[i]) : 1→0 = eating 상태로 들어갈 수 있음
            • test : V(self[i]) : 0→1
    1. Monitor(35p)
    • Semaphore의 문제점
      • 코딩하기 힘들다
      • 정확성(correctness)입증 어렵
      • 자발적 협력(voluntary cooperation) 필요 = 프로세스가 서로 협조
      • 한번의 실수가 모든 시스템에 치명적인 영향
      • ex) P와 V를 거꾸로 쓴 경우 : Mutual exclusion 깨짐
      • ex2) 둘다 P로 쓴 경우 : Deadlock
    • 특징
      • OOP(Object Oriental Program)
      • 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유 보장을 위해 high-level synchronization construct
      • 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
      • 프로그래머가 동기화 제약 조건(세마포어)을 명시적으로 코딩할 필요 없음(객체 자체가 그걸 보장하기 때문)
      • condition variable : 프로세스가 모니터 안에서 기다릴 수 있게 함, wait와 signal 연산에 의해서만 접근 가능
      • wait () : signal을 invoke하기 전까진 suspend
      • signal() : 정확하게 하나의 suspend된 프로세스를 resume(suspend된 프로세스가 없으면 아무 일도 일어나지 않음)
    • Bonded-Buffer Problem (bounded-Buffer = Ring Buffer) 모니터로 구현
      • void produce(int x)
      • void consume(int * x)
    • Dining Philosophers 모니터로 구현
      • void pickup(int i)
      • void putdown(int i)
      • void test(int i)
      • void init()
      • pickup()→ eat()→ putdown() → think()

ch7 Deadlocks(p37)

  1. Deadlock : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
    • Resource(자원) : hw, sw 등을 포함하는 개념
      • ex) I/O device, CPU cycle, memory space, semaphore 등
      • 프로세스가 자원을 사용하는 절차 : Request → Allocate → use → release
      • 자원할당그래프
        • P→R : 리소스 달라고 요청
        • R→P : R가 P에 의해 점유(사용)되고 있음
        • cycle
          • 그래프에 cycle없으면 ) deadlock 아님
          • cycle 있으면 ) deadlock일 가능성
            • 만약 R에 하나의 instance밖에 없으면(네모안에 점 하나) 무조건 deadlock
            • 여러 개이면 deadlock일 가능성
    • deadlock 예시
      • 하드웨어 : tape drive에서 프로세스가 tape drive를 하나 보유한 채 다른 하나 기다림
      • 소프트웨어 : Binary semaphores A and B에서 발생할 수 있음
    • 발생 조건
      1. Mutual exclusion : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음
      2. No preemption : 프로세스가 자원을 강제로 빼앗기지 않음
      3. Hold and wait : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음
      4. Circular wait : 자원을 기다리는 프로세스 간 사이클 형성
    • 처리 방법

      1. Deadlock Prevention - 적극적으로 막음(예방) ( p38)

        자원 할당 시 Deadlock의 4가지 조건 중 어느 하나가 만족되지 않도록 하는 것

        • Mutual Exclusion : 이건 어쩔 수 없음
        • Hold and Wait : 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 못하게 해서 해결 방법 1. 프로세스 시작시 모든 필요한 자원을 할당받게 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
        • No Preemption
          • 프로세스가 자원을 wait하면 이미 보유한 자원이 선점됨(강제로 빼앗김)으로 해결
          • 필요한 모든 자원을 얻을 수 있을 때 프로세스 다시 시작됨
          • CPU, memory 에서 주로 사용(state를 쉽게 save하고 restore할 수 있는 자원)
        • Circular Wait : circular 생기는 것을 막음
          • 자원에 할당 순서를 정해서 정해진 순서대로만 자원할당
          • ex) 순서 3인 자원 R1을 가지고 있을 때 순서 1인 자원 R2를 할당받으려면 R1을 release해야함

        ⇒ 단점 : utilization 저하, throughput 감소, starvation 문제

      2. Deadlock Avoidance - 적극적으로 막음(예방) (p39)

        • deadlock의 가능성이 없는 경우에만 자원할당(by 자원 요청에 대한 부가적인 정보 이용), 안전한지 동적으로 조사
        • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
        • 이것의 단순하고 일반적인 모델 = 프로세스들이 필요로하는 자원별 최대 사용량을 미리 선언하도록 하는 방법
        • safe state : 프로세스들에 대한 safe sequence 존재하는 상태
          • safe sequence : Pi의 자원 요청이 "가용자원 +모든 Pj(j<i)의 보유자원" 에 의해 충족되어야 함
          • 시스템이 unsafe state에 있으면 deadlock의 가능성 있음→ 시스템이 unsafe state에 들어가지 않는다는 걸 보장
        • avoidance 알고리즘

          1. Resource Allocation Graph algorithm : single instance per resource type의 경우 사용

          2. Banker's Algorithm : multiple instances per resource types의 경우 사용

            cf ) resource allocation graph algorithm의 경우 O(n^2) ???

      3. Deadlock Detection and recovery - 발생시 해결

        deadlock 발생은 허용하지만 그에 대한 detection루틴을 두어 deadlock을 발견하면 recover함

        • detection
          • single instance인 경우 : cycle이 곧 deadlock 의미
          • multiple instance인 경우 : Banker's algorithm과 유사
          • Wait-for graph 알고리즘 : single instance인 경우 프로세스 간의 cycle형성 관계를 살펴봄(그래프에 R없고 P만) O(n^2) 자원의 최대 사용량을 미리 알릴 필요 없으므로 자원할당그래프와 달리 점선 없음
        • Recovery
          • Process termination
            1. deadlock 된 거 한번에 다 죽임(abort)
            2. deadlock cycle없어질 때까지 한번에 하나씩 죽임
          • Resource Preemption
            • victim 선정
            • starvation 발생가능(동일한 프로세스가 계속 빅팀으로 선정되는 경우, rollback 횟수도 같이 고려)

      4. Deadlock Ignorance - 무시

        Deadlock을 시스템이 책임지지 않음 , UNIX 포함한 대부분의 OS가 채택

ch08. Memory Management(p42)

  1. Logical vs Physical Address

    • Logical Address(=virtual address) : 프로세스마다 독립적으로 가지는 주소공간(가상의 주소)
    • Physical Address : 메모리에 실제 올라가는 위치
    • 주소 바인딩 : 주소 결정 Symbolic Address → Logical Address → Physical Address

  2. 주소 바인딩(Address Binding)

    • Compile time binding
      • 물리적 메모리 주소(physical address)가 컴파일 시 알려짐
      • 시작 위치 변경 시 재컴파일
      • 컴파일로는 절대 코드(absolute code) 생성
      • logical address그대로 physical address
    • Load time binding
      • Loader의 책임 하에 물리적 메모리 주소 부여
      • 재배치가능코드(relocatable code) : 절대 주소 바꿀 수 있음
      • Loader가 작동할 때 묶어버림
      • 내부적 주소는 상대적
    • Execution time binding(=Run time binding)
      • CPU가 주소 참조할 때마다 binding 점검(address mapping table)
      • 수행이 시작된 이후에도 프로세스의 메모리상 위치 옮길 수 있음
      • 하드웨어적인 지원 필요 (ex. MMU, base and limit registers)
      • 실행 중에 주소와 묶음

  3. MMU(Memory-Management Unit) : logical address를 physical address로 매핑해주는 하드웨어 device(p43)

  • MMU scheme : 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값+base register(=relocation register)의 값을 더함 → physical address = logical address+relocation register값
  • user program : logical address만 다룸(실제 physical address는 모름)
  • 운영체제 및 사용자 프로세스 간의 메모리 보호를 위해 사용하는 레지스터(하드웨어)
    • Relocation register : 접근할 수 있는 물리적 메모리 주소의 최소값
    • Limit register : 논리적 주소의 범위(여기서 logical address가 범위밖으로 벗어나면 trap(software interrupt)
      • CPU-logical address→ limit register→relocation register-physical address→ memory

  1. Dynamic Loading : 프로세스 전체를 메모리에 미리 다 올려놓지 않고 해당 루틴이 불려질 때 메모리에 load함
  • memory utilization 향상 : 잘 쓰지 않는 라이브러리는 load하지 않음
  • 가끔씩 사용되는 많은 양의 코드의 경우에 적합(ex. 오류 처리루틴)
  • 운영체제의 특별한 지원 없이 프로그램 자체에서 구현 가능(OS자체의 기능은 아님. OS 도움없이 구현 가능), OS는 라이브러리 통해서 지원 가능
  • Loading : 메모리로 올리는 것
  1. Dynamic Linking : linking을 실행시간(execution time)까지 미룸
  • cf) static linking
    • 동일한 라이브러리를 각각의 프로세스가 메모리에 올리므로 메모리 낭비(속도는 빠름)
    • ex) printf 함수의 라이브러리 코드
  • Dynamic linking : 라이브러리가 실행시 연결(link)됨
    • stub : 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 작은 코드
    • 운영체제의 도움 필요
      • 라이브러리가 메모리에 이미 있는 경우 : 그 루틴의 주소로 감
      • 없는 경우 : 디스크에서 읽어옴
  1. Overlays (옛날 기술)
  • 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림
  • 프로세스의 크기 > 메모리의 크기 일 때 유용
  • 운영체제의 지원 없이 사용자에 의해 구현
  • manual overlay(수작업)
  1. Swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것
  • backing store(=swap area) : 디스크(충분히 빠르고 큰 저장공간)
  • swap in(필요한 애를) / swap out(필요하지 않은 애를)
    • swapper(중기 스케줄러)가 swap out될 거 선정
    • priority-based CPU scheduling algorithm : priority가 낮은 프로세스 swap out, 높은 프로세스를 메모리에 올려 놓음
  • Complie time binding+load time binding : 원래 메모리 위치로 swap in해야 함
  • Execution time binding : 빈 메모리 영역 아무 곳에나 올릴 수 있음
  • swap time=transfer time(swap되는 양에 비례)
  1. Allocation of Physical Memory
  • 메모리 영역
    1. OS 상주 영역 : interrupt vector와 함께 낮응 주소 영역 사용
    2. 사용자 프로세스 영역 : 높은 주소 영역 사용
  • 사용자 프로세스 영역 할당 방법
    1. Contiguous allocation : 각각의 프로세스가 연속적인 공간에 적재
      • 종류
        1. Fixed partition allocation(고정분할방식)
          • 물리적 메모리를 영구적 분할(partition)
          • 분할의 크기는 os설계 방법에 따라 모두 동일할 수도 있고 서로 다를 수도 있음
          • 분할 당 하나의 프로그램 적재
          • 융통성 없음
            • 동시에 메모리에 load되는 프로그램 수 고정적
            • 최대 수행 가능 프로그램 크기 제한
          • Internal / external fragmentation 발생
        2. Variable partition allocation(가변분할방식)
          • 프로그램의 크기를 고려해서 할당
          • 분할의 크기, 개수가 동적으로 변함
          • 기술적 관리 기법 필요
          • External Fragmentation 발생
          • Dynamic Storage-Allocation Problem : 가변 분할 방식에서 가장 적절한 hole 찾는 문제

            1. First-fit : size가 n 이상인 것 중 최초로 찾아지는 hole에 할당

            2. Best-fit : size가 n 이상인 것 중 가장 작은 hole 찾아서 할당

              • hole이 크기순으로 정렬되어있지 않다면 처음부터 끝까지 다해봐야 함
              • 많은 수의 아주 작은 hole들이 생성됨

            3. Worst-fit : 가장 큰 hole에 할당
              - 모든 리스트 탐색해야 함
              - 상대적으로 아주 큰 hole들이 생성됨

              ⇒ First-fit과 Best-fit 이 효과적

      • fragmentation : 노는 공간 발생
        1. External fragmentation(외부 조각)
          • 프로그램의 크기 > 분할의 크기
          • 빈 곳이지만 프로그램이 올라갈 수 없는 작은 분할
        2. Internal fragmentation(내부 조각)
          • 프로그램의 크기 < 분할의 크기
          • 하나의 분할 내부에서 발생하는 사용되지 않는 메모리 조각(특정 프로그램에 배정되었지만 사용되지 않음)
      • hole ; 가용메모리 공간(비어서 쓸 수 있는 공간)
        • 운영체제가 할당공간과 가용 공간(hole)에 대한 정보를 유지해야 함
      • Compaction : external fragmentation 해결하기 위한 방법
        • 사용 중인 메모리 영역을 한군데로 몰아 넣고 새로운 큰 hole을 만듦
        • 비용 매우 큼
        • 프로세스 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있음(execution time binding에서 사용 가능)
    2. Noncontiguous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산
      • 종류
        1. paging(p47)
        2. segmentation
        3. paged segmentation
      • paging : Process의 virtual memory(logical memory)를 동일한 사이즈의 page단위로 나눔
        • Virtual memory의 내용이 page단위로 noncontiguous하게 저장
        • 일부는 backing storage(안쓰는 것 → HDD, SSD, 느리지만 가격이 싼) 일부는 physical memory에 저장(당장쓰는 것들)
        • paging table을 이용하여 logical address→ physical address로 변환
        • external fragmentation 발생 안함(동일한 크기로 나누었기 때문)
        • internal fragmentation 발생 가능
      • Address Translation Scheme
        • Virtual address(p47)
          • Page number(p) : page table의 인덱스
          • Page offset(d) : base address와 더해져서 physical address
      • page table 구현(P48)
        • page table은 main memory에 상주
        • PTBR(Page-table base register)가 page table가리킴
        • PTLR(Page-table length register)가 테이블 크기를 보관
        • 2번의 memory access 필요(모든 메모리 접근 연산에)
          • page table 접근 1번
          • 실제 data/instruction 접근 1번
        • 속도 향상 위해 lookup hardware cache사용(associative register || translation look-aside buffer(TLB))
          • EAT(Effective Access Time)
      • Two-Level Page Table (p49)
        • page table 자체를 page로 구성(공간 낭비 막기위해)
        • outer page table(사용되지 않는 주소공간) : NULL 주고 할당 x
        • logical address (on 32bit machine with 4K page size)
          • page number : 20bit → page table자체가 page로 구성되기 때문에 또 나뉨
            • page number : 10bit = outer page table의 index
            • page offset : 10bit = outer page table의 page에서의 변위(displacement)
          • page offset : 12bit
      • Multilevel Paging and Performance(p50)
        • address space가 커짐에 따라 다단계 페이지 테이블 필요
        • multilevel 이 늘어나더라도 effective memory access time이 크게 늘어나진 않음
        • memory protection
          • Protection bit
          • Valid-invalid bit
            • invalid
              • 할당 x인 상태
              • 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우
      • Inverted Page Table : Page frame 하나당 page table 하나의 entry둔것(system-wide)
        • physical M에 대해 1:1로 page table 만듦(pid로 search함)
        • 단점 : 테이블의 전체를 탐색해야함 → 조치 : associative register 사용(cache, 비쌈)
      • Shared Page(P51)
        • Re-entrant Code (=Pure code) : 여러개의 process entrant 가능
          • 동일 코드, 데이터만 다름
        • read only
        • 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
        • cf) private code and data : 각 프로세스들은 독자적으로 메모리에 올림
          • private data는 logical address space의 아무곳에 와도 괜찮
      • Segmentation : 프로그램을 구성하는 의미 단위(덩어리 개념)
        • 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨(사이즈는 프로그램 전체, 이렇게 커질 수도 있고 함수 하나, 이렇게 작아질 수도 있다.)
        • logical unit
        • Segmentation Architecture (P52)
          • logical address : <segment-number, offset>
          • Segment table
            • table entry
              • base : starting physical address of the segment
              • limit : length of the segment(segment의 크기를 넘으면 안됨)
          • STBR(Segment-table base register) : 물리적 메모리에서 segment table위치
          • STLR : 프로그램이 사용하는 segment의 수(s<STLR)
          • Protection : 각 세그먼트 별로 protection bit
            • Valid bit =0 → illegal segment
            • Read/Write/Execution 권한 bit
            • ⇒ 의미 단위로 나눠놨기 때문에 가능
          • sharing : 의미 단위이기 때문에 공유와 보안에 있어서 paging보다 더 효과적
            • shared segment
            • same segment number
            • base 똑같이
            • 특히 code sharing 많이 함(변경 안해서)
            • 프로세스 별 독립적 활동은 여전히 가능하면서 메모리 공간 졀약
          • allocation
            • first fit/ best fit
            • external fragmentation 발생
            • segment의 길이가 동일하지 않기때문에 가변분할 방식에서와 동일한 문제점
        • segmentation with paging (P53)
          • segmentation과 달리 segment-table entry가 segment의 base address를 가지고 있지 않고, segment를 구성하는 page table의 base address를 가지고 있음

ch9. virtual memory (p54~)

  1. Demand Paging : 요구하는 page를 backing store에서 올려줌
    • 실제로 필요할 때 page를 메모리에 올리는 것
    • valid / invalid bit의 사용
      • invalid
        • 사용되지 않는 주소영역(아직 physical M에 올라오지 않음)
        • 페이지가 물리적 메모리에 없는 경우
      • 처음에는 모든 page entry invalid로 초기화 → p에 올라가면 v로 바꿈
      • page fault : invalid bit인 경우 → backing store에서 가져옴(physical memory에 올라오지 않았다는 것)
    • free frame이 없는 경우(p55)
      • page replacement : 어떤 frame을 빼앗아올지 결정해야 함
      • replacement Algorithm : page-fault rate 최소화
        • Optimal Algorithm(p56) : MIN, belady's, opt
          • offline algorithm
          • 실제 사용되는 것은 아니고 alg 평가 기준으로 사용
        • FIFO algorithm
          • 먼저 들어온 것을 먼저 내쫓음
          • FIFO Anomaly(Belady's Anomaly) 역효과 : frame 수가 늘어났는데 page fault가 줄지 않음 ⇒ 좋은 알고리즘 아님
        • LRU Algorithm(Least Recently Used)
          • LRU : 가장 오래전에 참조된 것을 지움
          • linked list 사용
          • O(1)
        • LFU Algorithm(Least Frequently Used)
          • 참조횟수(reference count)가 가장 적은 객체를 지움
          • 장점 : 장기적인 시간 규모, 인기도 좀더 정확히 반영
          • 단점 : 최근성 반영 못함, 구현 복잡
          • heap 사용
          • O(log n)
  2. 캐슁 환경(P57)
    • 캐슁 기법 : 한정된 빠른 저장공간, 요청되는 새로운 객체 저장공간에 읽어들임, 후속요청시 직접 서비스
      • paging system, cache memory, buffer caching, web caching 등에 사용
      • buffer caching, web caching = O(1)~O(logn)
      • paging system : 페이지 요청 너무 빈번 → O(1)도 부담
        • Clock Algorithm : LRU의 근사 알고리즘
          • second chance algorithm
          • NUR, NRU
          • circular list
          • reference bit가 사용되면 MMU로 인해 1로 바뀌는데 한바퀴(시계방향 돌아와서도 0이면 replace당함(2번의 기회: 첫번째 0일 수 있음 2번은 안됨)
          • 개선 : reference bit + modified bit(dirty bit)
            • reference bit=1 : 최근에 참조
            • modified bit=1 : 최근에 변경
    • page frame의 allocation(p58)
      • allocation problem : 각 process에 얼마만큼 page frame 할당?
        • loop 구성하는 page들은 한꺼번에 allocate되는 것이 유리함
      • allocation scheme
        • equal allocation : 똑같은 크기로 할당
        • proportional allocation : 프로세스 크기에 비례해서 할당
        • priority allocation : priority에 따라서 할당
    • replacement : 빈공간 없으면 빼앗아 오는 것
      • global replacement : 다른 process에 할당된 frame을 빼앗아 올 수 있음
        • 할당량 조절 방법
        • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용
        • working set, pff 알고리즘
      • local replacement : 자신에게 할당된 frame 내에서만 replacement
        • FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시
    • Thrashing : 최소한의 page frame 받지 못한 경우 → low throughput
      • page fault 매우 높아짐
      • multiprogramming 높아졌는데 CPU utilization 떨어지면 thrashing
      • multiprogramming(MPD)가 너무 높아지면 발생(줄여야함 왜냐면 너무 높아지면 프로세스 하나당 할당 받을 수 있는 page frame 못받음)
    • working-set model(p59)
      • locality : 일정장소만 집중적으로 참조
      • locality 기반하여 한꺼번에 메모리에 올라와 있어야하는 page들의 집합
      • thrashing 방지
      • multiprogramming degree 결정
      • working set 전체가 메모리에 올라와 있어야 하고 그렇지 않은 경우 swap out (suspend)
      • working-set algorithm
        • working set size의 합 > page frame의 수 : swap out → MPD 줄임
        • < : swap out 되었던 프로세스에게 working set 할당(MPD 키움)
        • working size 너무 작으면 locality set 모두 수용 x
        • 너무 크면 불필요한 거까지 수용
      • PFF Scheme(p60)
        • page fault rate 상한값, 하한값
          • 상한값 넘으면 : page frame 더 할당
          • 하한값 이하면 : page frame 줄임
        • 빈 frame 없으면 swap out
      • page size 감소
        • 페이지 수 증가
        • 페이지 테이블 크기 증가
        • internal fragmentation 감소
        • disk transfer효율성 감소
        • 필요한 정보만 메모리에=메모리 이용 효율(Locality 활용은 bad)

ch10. file system(p61)

  1. File : 주로 비휘발성 보조기억장치에 보관
    1. metadata : 데이터 위한 데이터(file attribute)
    2. file system
  2. Directory and Logical Disk
    • Directory : 메타데이터 중 일부 보관
    • Partition(=logical disk) : file system, swapping 등 다양한 용도로 사용 가능
  3. open() (p62) : retrieves metadata from disk to main memory
    • open("/a/b/c") : 디스크로부터 파일c의 메타데이터를 가져옴 → directory path search
    • read와 write 와 별도 → 한번 open 한 파일은 read와 write 시 directory search 불필요(directory path search 하는데 오래 걸려서)
    • open file table : 현재 open된 파일들의 메타데이터 보관소 (in memory)
      • 오픈한 프로세스 수
      • file offset 표시
    • file descriptor(file handle, file control block) : open file table에 대한 위치정보(프로세스별)
    • PCB
  4. file protection
    1. Access control Matrix
      • access control list
      • capability
    2. Grouping : unix
      1. user를 owner, group, public 세 그룹으로 구분
    3. Password
  5. Mounting 통해 파일 시스템 무한 확장 가능
  6. Access Methods(p63) : 시스템이 제공하는 파일 정보의 접근 방식
    • 순차 접근(sequential access) : HDD
      • 카세트 테이프 방식 처럼
      • 읽거나 쓰면 offset 자동 증가
    • 직접 접근(direct access, random access) : SSD, DRAM(휘발성)
      • lp레코드 판 같이
      • 임의의 순서로 레코드 접근

ch11. file system implementation

  1. Allocation of file data in disk

    • contiguous Allocation
      • 단점
        • external fragmentation
        • file grow 어렵
      • 장점
        • fast I/o : realtime file 용, swapping 용
        • direct access(random access)
    • Linked Allocation(p65)
      • 장점 : external fragmentation 발생 안함
      • 단점
        • no random access
        • reliability 문제
        • 공간효율성 떨어짐
      • 변형 : FAT(File-allocation table) = MS-DOS와 OS/2에서 사용
    • Indexed Allocation
      • 장점
        • external fragmentation 발생 안함
        • direct access 가능
      • 단점
        • small file → 공간 낭비
        • too large file → 공간 부족
      • 해결 방안
        • linked scheme
        • multi-level index

  2. UNIX (P66) : partition사용

    • boot block : 부팅에 필요한 정보(ex. bootstrap)
    • superblock : 파일 시스템에 관한 총체적인 정보(전체적인 큰 틀 metadata for metadata)
    • Inode : 파일 이름 제외한 파일의 모든 메타정보(인덱스 정보 포함)
      • Inode list → direct blocks(파일 내용 어떻게 인덱싱)
    • data block : 파일의 실제 내용

  3. MS-DOS : partition 사용

    • FAT(File Allocation Table)

  4. Free space management(p66~67)

    1. bit map or bit vector :ㄱ부가적인 공간 필요
      • 연속적인 n개의 free block 찾는데 효과적
      • bit[i]=0 → 빈곳
      • =1 → 쓰는 곳
    2. Linked list : 모든 free block을 링크로 연결(free list)
      • 연속적인 가용공간 찾기 어렵
      • 공간 낭비 없음
    3. Grouping
      • linked list 변형
      • n-1 번째 포인터가 free data block 가리킴
    4. Counting : 여러개의 연속적인 block 할당하고 반납
      • first free bloc, # of contiguous free blocks

  5. Directory Implementation

  • Linear list: <file name, file의 metadata>의 list
    • linear search(time-consuming)
  • Hash table : linear list+hashing
    • search time 없앰
    • collision
  • metadata 보관 위치
    • 직접보관
    • 포인터 두고 다른 곳에 보관(inode, FAT)
  1. VFS and NFS
  • VFS(Virtual File System) : API(동일한 시스템 콜 인터페이스) 통해 접근할 수 있게 해줌
  • NFS(Network File System) : 분산 시스템에서 네트워크 통해 파일 공유
  1. Page Cache and Buffer Cache : 보는 관점이 달라
  • Page cache : virtual memory의 paging system에서 사용하는 caching 관점, 사용자 메모리 영역
  • Memory-Mapped I/O : file 일부 virtual memory에 mapping(page cache랑 연결)
  • Buffer Cache : 파일 시스템 통한 I/O연산할때 사용
    • 커널 메모리 영역
    • locality 사용(한번 읽어 온 블록은 후속 요청시 buffer cache에게 즉시 전달)
    • 모든 프로세스가 공용으로
    • replacement algorithm 필요(LRU, LFU 등)
  • Unified Buffer Cache : Page cache + Buffer Cache(p69 그림)
    • page cache가 buffer cache로 통합됨

ch12. disk management and scheduling

  1. Disk Structure
    1. logical block : 외부에서 는 관점, 1차원 배열 처럼
    2. Sector : logical block이 물리적 디스크에 매핑된 위치
  2. Disk Management
    1. physical formatting( Low-level formatting) : 섹터 나누는 과종
      • 섹터 = header+실제 data(512B)+trailer
      • header, trailer = sector number, ECC 등의 정보, controller가 직접 접근 운영(사용자는 신경 x)
    2. Partitioning
      • 디스크를 하나 이상의 실린더 그룹으로 나눔
      • OS는 이걸 독립적 disk로 취급(logical disk)
    3. Logical formatting
      • 파일 시스템 만듦
      • FAT, inode, free space 등의 구조 포함
    4. Booting
      1. ROM에 있는 small bootstrap loader의 실행
      2. sector 0 (boot block)을 load하여 실행
      3. sector 0은 full Bootstrap loader program
      4. OS를 디스크에서 load하여 실행

3, Disk scheduling

  • Access time = Seek time + Rotational latency + Transfer time ⇒ seek time 줄이기
  • Disk bandwidth : 단위 시간 당 전송된 바이트 수
  • Disk scheduling : seek time 줄이기
  • disk scheduling algorithm(p71~)
    1. FCFS : 순서대로
    2. SSTF : 헤드의 현재 위치와 가까운 거 부터( starvation)
    3. SCAN : 한쪽 끝에서 다른 쪽으로 이동하며 처리(실린더 위치에 따라 대기시간 다름)
    4. C-SCAN : SCAN보다 균일한 대기시간
    5. 기타
      1. N-SCAN
      2. LOOK : 무조건 제일 끝까지 가는 게 아니라 더이상 없으면 즉시 반대로 옴
      3. C-LOOK
    • 결정 방법 : 일반적으로 SCAN, C-SCAN, LOOK, C-LOOK 이 효율적
      • File의 할당 방법에 따라 디스크 요청이 영향을 받으므로 유동적으로
      • OS와 별도의 모듈로 작성하는 게 바람직(교체할 수 있게)
  • Swap-Space Management(p73)
    • disk 사용 이유
      1. memory(DRAM)의 휘발성(volatile) → file system을 저장용으로 사용
      2. memory 공간 부족 → swap space(swap area) : 저장공간 확장
    • Swap-Space : 속도 효율성 중요
      • 일반 파일보다 짧은 시간만 존재하고 자주 참조
      • block의 크기 및 저장 방식이 일반 파일시스템과 다름
  • RAID : 여러개의 디스크를 묶어서 사용

    • RAID0 : 디스크 처리 속도 향상(분산저장, 병렬적, interleaving, striping)

    • RAID1 : 신뢰성 향상(중복저장, mirroring, shadowing, parity 저장(공간효율성))

      ** 디스크 관리를 위한 절차는 physical formatting → partitioning → logical formatting의 순서

profile
밈무
이전 포스트

맥북 파일명 한글 안 깨지게

다음 포스트

암호 - 대칭 암호화에 대해서

0개의 댓글