ABOUT ME

Today
Yesterday
Total
  • (7) 데드락, (8) 메모리 관리, (9) 가상 메모리
    운영체제 2024. 11. 18. 22:39

    참고: 이화여대 반효경 교수님 운영체제 강의 

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

     

    데드락

    프로세스가 자원을 사용하는 절차

    요청 - 획득 - 사용 - 반납

     

    데드락: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block 된 상태

    자원: I/O 디바이스, CPU cycle, 메모리 공간, 세마포어 등

     

     

    예시: 시스템에 a, b 두 개의 프로세스가 있을 때, 각각이 하나의 자원을 보유한 채 다른 하나를 기다리고 있음.

     

    데드락이 발생하는 조건

    1. 상호 배제: 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

    2. 비선점: 프로세스는 자원을 스스로 내어놓을 뿐, 강제로 빼앗기지 않음

    -> 프로세스가 어떤 자원을 기다려야 하는 경우, 이미 보유한 자원이 선점되도록 함. 상태를 쉽게 저장하고 복구할 수 있는 자원에 사용

    3. 보유대기: 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음

    -> 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법으로 예방

    4. 순환대기: 자원을 기다리는 프로세스 간 사이클이 형성됨 (예: a는 b를 기다리고, b는 c를 기다리고, c는 a를 기다림)

    -> 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원 할당

     

    데드락 처리 방법

    (1) 데드락 예방: 자원 할당 시 데드락의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

    -> utilization 저하, throughput 감소, starvation(기아) 문제 = 총체적 비효율적

     

    (2) 데드락 회피: 자원 요청에 대한 부가적인 정보를 이용해서 데드락의 가능성이 없는 경우에만 자원 할당

    -> 자원 할당이 데드락으로부터 안전한지 동적으로 조사해서 안전한 경우에만 할당

    -> 자원 할당 그래프를 통해 사이클이 있는 경우, 데드락의 가능성이 있으니 미리 회피할 수 있음

    -> 사이클 생성 여부 조사 시 프로세스의 수가 n일 때 O(n^2) 시간 복잡도 소모

    -> 뱅커스 알고리즘을 쓰는 게 더 편함

     

    (3) 데드락 탐지 및 복구: 데드락 발생은 허용하되 그에 대한 탐지 루틴을 두어 데드락 발견 시 복구함

    -> 모든 데드락 프로세스를 없애거나, 데드락 사이클이 사라질 때까지 한 프로세스씩 없앰

     

    (4) 데드락 무시: 데드락을 시스템이 책임지지 않음 <- 대부분의 OS가 채택함

     

     

     

    메모리

    가상 주소(=논리 주소): 프로세스마다 독립적으로 가지는 주소 공간, 각 프로세스마다 0번지부터 시작

    물리 주소: 메모리에 실제 올라가는 위치

    cpu는 가상 주소를 바라봄

     

    컴파일 타임 바인딩: 가상 주소 = 물리 주소, 시작 장소 변경 시 재컴파일, 이 코드는 절대 코드임

    로드 타임 바인딩: 로더의 책임하에 물리적 메모리 주소 부여, 

    런타임 바인딩: 수행이 시작된 이후에도 프로세스의 메모리상 위치를 옮길 수 있음, CPU가 주소를 참조할 때마다 바인딩 점검(주소 매핑 테이블) < 현대 바인딩 기법 >

     

    MMU 메모리 매니지먼트 유닛: 가상 주소를 물리 주소로 바꿔주는 유닛

     

    트랩: 가상 주소가 할당된 범위를 초과했을 경우 발생하는 주소 에러

     

    동적 로딩: 프로세스 전체를 메모리에 미리 다 올리는 것이 아닌, 해당 루틴이 불려질 때 메모리에 load하는 것

    -> OS 라이브러리를 통해 지원하며 프로그램 자체에서 구현 가능, 메모리 utilization 향상

     

    동적 링킹: 프로그램 컴파일 과정에서의 링킹(실행 파일 만드는 과정)을 실행 시간까지 미루는 기법

    - 라이브러리가 실행 시 연결되며 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 작은 코드를 둠

    - 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴

    - OS의 도움이 필요함

     

    오버레이: 메모리에 프로세스의 부분 중 실제 필요한 정보만을 올림 (=동적 로딩)

    -> 프로세스의 크기가 메모리보다 클 때 유용, 프로그래머가 직접 구현해야 되며 예전 방식임

     

    스와핑: 프로세스를 일시적으로 메모리에서 backing store(하드 디스크)로 쫓아내는 것

    - 중기 스케줄러에 의해 swap out시킬 프로세스 선정

     

    연속 할당: 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

    불연속 할당: 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음 < 현대 할당 기법 >

    - 페이징, 세그멘테이션, paged segmentation

     

    1. 페이징: 프로세스의 물리 메모리를 같은 크기로 미리 잘라놓음(프레임) 

     

    (1) 물리 메모리를 같은 크기의 프레임으로 나눔

    (2) 가상 메모리를 동일 크기의 페이지로 나눔(프레임과 같은 크기)

    (3) 모든 가용 프레임들을 관리

    (4) 페이지 테이블을 이용해 가상 주소를 물리 주소로 변환

    (5) 외부 메모리 단편화는 발생하지 않지만 내부 메모리 단편화는 발생 가능

     

    페이지 테이블은 메인 메모리에 상주함

    모든 메모리 접근 연산에는 2번의 메모리 접근이 필요함

    1. page table 접근, 2. data/instruction 접근

    속도 향상을 위해 TLB(translation look-aside buffer)이라는 고속의 lookup hardware cache 사용

     

    Two-Level Page Table, Invertible Page Table, Shared Page 다양한 기법 존재

     

    2. 세그멘테이션: 물리 메모리를 의미 있는 단위로 자름(코드 세그먼트, 데이터 세그먼트, 스택 세그먼트 등), 크기가 균일하지 않음 (단점: 크기가 가변적이기 때문에 프로그램에 맞는 크기를 가진 세그먼트를 찾아야 함)

    세그먼트 별로 protection bit가 있어서 Read/Write/Execution 등에 따라 의미별 구분이 가능함 (페이징 기법과 다른 점)

    segment는 의미 단위이기 때문에 공유나 보안에 있어서 paging 보다 훨씬 효과적임

     

    Segment table - base, length register 사용

    Segment table base register: 물리적 메모리에서의  segement table의 위치

    Segment table length register: 프로그램이 사용하는 segment의 수(offset으로 사용)

     

    3. paged segmentation

     

    메모리 주소 변환에서 OS가 하는 일은 없으며 모두 MMU 같은 하드웨어가 수행함

     

     

     

    가상 메모리

    Demand Paging: 실제로 필요할 때 페이지를 메모리에 올리는 것

    - I/O 양 감소, 메모리 사용량 감소, 빠른 응답 시간, 더 많은 사용자 수용 등 유리함

     

    Valid/Invalid bit의 사용

    - Invalid란 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우

    - 주소 변환 시 invalid bit이라면 'page fault' 상태가 됨(MMU가 trap을 발생)

     

    page fault 처리 순서 (심각한 오버헤드 발생)

     

    1. Invalid 요청인가? (bad address, protection violation 등 -> abort)

    2. 비어 있는 페이지 프레임이 없으면 뺏어온다 

    3. 해당 페이지를 디스크에서 메모리로 읽어온다.

    - disk I/O가 끝나기까지 이 프로세스는 CPU를 선점당함(block)

    - 디스크 read가 끝나면 페이지 테이블 entry 기록 후 valid/invalid bit = "valid" 변경

    - 레디 큐에 프로세스를 insert -> dispatch later

    4. 이 프로세스가 CPU를 잡고 다시 running

    5. 중단되었던 instruction 재개

     

     

    page fault 시 replacement algorithm

    (1) optimal algorithm (미래를 안다고 생각하고 시행)



    (2) FIFO algorithm (현실적으로 사용 가능함)

     

    페이지 프레임이 많을수록 페이지 폴트가 많아져서 성능이 더 나빠지는 이상한 점 발생

     

     

     

     

     

     

     

     

     

     

     

    (3) LRU(Least Recently Used) algorithm (가장 많이 사용함) - 시간복잡도 O(1) 연결리스트

     

     

    (4) LFU(Least Frequently Used) algorithm - 시간복잡도 O(log n) 이진트리 힙 자료구조 

    - 참조횟수가 가장 적은 페이지를 지움

     

     

    다양한 캐싱 환경 

    캐싱 기법: 한정된 빠른 공간(=캐시)에 요청된 데이터를 저장되었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식

    버퍼 캐싱이나 웹 캐싱의 경우 O(1)~O(log n)까지만 시간 한계를 정해둠

     

    Clock Algorithm (=Second chance algorithm, NUR or NRU not recently used)

    - LRU의 근사 알고리즘

     

    Page Frame의 Allocation

    Allocation problem: 각 프로세스에 얼마만큼의 page frame을 할당할 것인가?

    명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음

    loop을 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함

    - 최소한의 allocation이 없으면 loop를 돌때마다 page fault

     

    Allocation Scheme

    Equal allocation: 모든 프로세스에 똑같은 개수 할당

    Proportional allocation: 프로세스 크기에 비례하여 할당

    Priority allocation: 프로세스의 priority에 따라 다르게 할당

     

    Global replacement (그때마다 다른 프로세스와 경쟁)

    - Replace 시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있음

    - FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시 할당

    - Working Set, PFF 알고리즘 사용

     

    Local replacement (미리 할당된 내 몫의 frame을 활용)

    -  자신에게 할당된 frame 내에서만 replacement 수행

    - FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영 시에 할당

     

     

    Thrashing: 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못했을 때 발생

    - Page fault rate가 매우 높아지고, CPU utilization이 낮아짐

     

    Thrashing을 해결해주는  알고리즘

     

    Working-Set Model

    - 지역성: 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다

    - 집중적으로 참조되는 해당 page들의 집합을 locality set이라고 함

     

    지역성에 기반해서 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 페이지들의 집합을 Working Set이라고 함

    프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 frame을 반납한 후 swap out함 -> suspended

    이를 통해 Thrashing을 방지함

     

     

    PFF(Page-Fault Frequency) Scheme

    - page-fault rate의 상한값과 하한값을 둔다

    - page fault rate가 상한값을 넘으면 frame을 더 할당한다

    - page fault rate가 하한값 이하이면 할당 frame 수를 줄인다

    - 빈 frame이 없으면 일부 프로세스를 swap out(suspended)시킴

     

     

    Page Size의 결정

    - Page size를 감소시키면 페이지 수 증가, 페이지 테이블 크기 증가, 내부 단편화 감소, 필요한 정보만 메모리에 올라와서 메모리 이용이 효율적이나 지역성 활용 측면에서는 좋지 않음

     

    큰 페이지 사이즈를 사용하는 것이 일반적임

     

     

     

     

Designed by Tistory.