캐시 메모리 (Cache Memory)
        
  <출처 : wikipedia >
  • CPU 칩 안에 포함되는 빠르고 작은 메모리.
  • 속도가 빠른 장치와 느린 장치간의 속도차에 따른 병목 현상을 줄이기 위한 범용 메모리
  • 프로그램에서 직접적으로 읽거나 쓸 수 없고, 하드웨어 메모리 관리 시스템이 내부적으로 제어한다.
  • 데이터 지역성을 활용해서 메인 메모리에 있는 데이터를 캐시 메모리에 불러와 두고, CPU가 필요한 데이터를 캐시에서 먼저 찾도록 하면 시스템 성능을 향상시킬 수 있다.




캐시 메모리의 설계 목표
  • Cache 적중율(Hit Rate)의 극대화로 Cache Access 시간 최소화
  • Cache 실패율(Miss Rate)에 따른 지연시간(Miss Penalty)의 최소화
  • 공유 메모리와 Cache 간의 일관성 유지






캐시 메모리의 특징
  • Locality(지역성) : 블록 단위의 메모리 참조 (시간, 공간)
  • Mapping(매핑) : 주기억 장치와 캐시 메모리 간의 메모리매핑 적용 (직접, 연관)
  • Coherence(일관성) : 병렬 처리시 Local Cache와 공유 메모리간 데이터 일관성 유지 (공유 Cache)





캐시 메모리 적중률 극대화 원리 : Locality
  • 시간적 지역성 : 최근 사용된 데이터의 재 이용율이 높음. (ex. Loop, Stack, Sub Program)
  • 공간적 지역성 : 최근 사용된 데이터의 인접 데이터의 사용율이 높음 (ex. Array, 순차코드)
  • 순차적 지역성 : 데이터가 기억장치에 저장된 순서대로 순차적으로 인출되고 실행될 가능성이 높음




캐시 미스가 나는 경우
  • Compulsory miss : 해당 메모리 주소를 처음 불렀기 때문에 나는 캐시 미스. 
  • Conflict miss : 캐시 메모리에 A데이터와 B데이터를 저장해야되는데, A와 B가 같은 캐시 메모리 주소에 할당되어서 나는 캐시 미스.
  • Capacity miss : 캐시 메모리에 공간이 부족해서 나는 캐시 미스.





 캐시 메모리와 주기억장치 Mapping
  • 캐시 메모리 Mapping 목적
        - Cache의 용량이 주기억장치의 용량보다 적기 때문에 주기억장치의 일부분만 캐시로 적재될 수 있음.
        - 제한된 캐시 용량으로 최고의 적중률을 얻을 수 있는 방법 필요.

  • 캐시 메모리 Mapping 기법의 종류
            - Direct Mapping 
             개념 : 메인 메모리를 일정한 크기의 블록으로 나누고 각각의 블록을 캐시 위 정해진 위치에 매핑하는 방식
              장점 : 가장 쉽고 간단
              단점 : 비어 있는 라인이 있더라도 동일 라인의 메모리 주소에 대하여 하나의 데이터밖에 저장 할 수 없음. 캐시의 성능을 저하시킴

            - Full Associative Mapping
             개념 : 직접매핑 방식의 단점을 개선하기 위해 태그 필드를 확장하여 캐시의 어떤 라인과도 무관하게 매핑 시킬수 있는 매핑 방법
             장점 : 캐시를 효율적으로 사용하게 하여 캐시의 히트율 증가
             단점 : 구성과 과정이 매우 복잡

            - Set Associative Mapping
             개념 : 위의 두 매핑방식의 장점을 취하고 단점을 최소화한 절충안. 캐쉬를 N개의 세트들로 나누고 각 세트들은 L개의 라인들로 이루어지게 구성. 전체 메인 메모리는 각 세트의 크기인 32Kbyte 단위로 나뉘어 태그 값이 매겨지고(Direct Mapping) 각각 4Kbyte 단위의 라인 사이즈로 다시 나뉘어져 각각의 세트에 매핑(Associative Mapping)







캐시 메모리 교체 알고리즘

  • FIFO (First-In-First-Out) : 캐시 내에 가장 오래 머물러 있었던 블록 교체.
  • LRU (Least Recently Used) : 사용되지 않고 가장 오래 캐시에 머물러 있던 블록 교체.
  • LFU (Least Frequently Used) : 캐시 내에 있는 블록 중 가장 사용빈도가 낮은 블록을 교체.
  • Optimal : 향후 가장 참조되지 않을 블록 교체.




저작자표시

'운영체제' 카테고리의 다른 글

CPU Scheduling (CPU 스케줄링)  (0) 2018.08.30
커널(Kernel), 마이크로 커널&모놀리식 커널  (0) 2018.08.28
교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26
병행성과 상호배제&상호배제 알고리즘  (0) 2018.08.26


교착 상태(Deadlock)
  • 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상
  • Multi processing 환경에서 다수의 프로세스가 특정 자원의 할당을 무한정 기다리고 있는 상태




교착 상태(Deadlock)와 기아(Starvation)

 

교착상태 (Deadlock) 

기아(Starvation) 

정의

 다수의 프로세스가 아무일도 하지 못하고 특정 사건 무한대기

특정 프로세스가 자원을 할당 받기위해 무한정 대기 상태 

 발생 원인

상호배제, 점유와 대기, 비선점, 환형 대기 

자원의 편중된 분배정책 

해결방안

예방, 회피, 발견, 회복 기법

Aging 기법 

( ※ Aging 기법 : 대기 시간 등에 따라 우선순위를 높여줌으로써 기아현상을 해결하는 방법)




교착상태 발생 조건
  • 교착상태는 다음 4가지 조건이 모두 성립시에 발생한다.
  1. 상호배제 (Mutual Exclusion) - 한 시점에 한 프로세스만이 자원을 사용 할 수 있다. 즉 한 프로세스에 의해 점유된 자원을 다른 프로세스들이 접근할 수 없다.
  2. 점유와 대기 (Hold-and-wait) - 프로세스가 어떤 자원을 할당 받아 점유하고 있으면서 다른 자원을 요구.
  3. 비선점 (No Preemption) - 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없으며, 점유하고 있는 프로세스 자신만이 해제 가능
  4. 환형 대기 (Circular wait) - 프로세스들 간에 닫힌 연결(closed chain)이 존재한다. 즉 자원 할당 그래프에서 환형이 만들어지는 것.






교착상태 해결 방안
  • 교착상태 예방
        교착상태이 발생하기 위한 4가지 필요충분조건 중에 하나를 배제하는 것
        - 상호배제 : 상호 배제 조건은 공유 자원의 일관성을 유지하기 위해 반드시 필요하기 때문에, 상호 배제 조건을 없앨 수는 없다.
        - 점유와 대기 : 프로세스가 자신이 사용할 모든 자원을 할당 요청하고, 모든 자원을 할당받을 수 있으면 계속 수행, 하나의 자원이라도 할당받을 수 없다면 할당 받지 않은채 대기한다. 이 방법은 가능하지만 자원의 비효율적이다.
        - 비선점 : 자원임시 할당해제 및 원상복구, but 비효율적
        - 환형 대기 : 자원들의 할당 순서를 정한다. but 환형대기 조건을 없애는 것은 프로세스의 수행 지연과 불필요한 자원 할당 거부를 야기할 수 있다.

  • 교착상태 회피
        교착상태 회피를 위한 2가지 기법
            1. 프로세스 시작 거부
                새로운 프로세스와 기존 프로세스들이 요구하는 자원의 개수가 그 자원의 전체 개수보다 적을 경우에 수행을 허용하는 것이다. 이 정책은 최악의 경우, 즉 모든 프로세스들이 동시에 최대 자원을 요구하여 사용함을 가정하고 있으며, 따라서 효율적이지 않다.

            2. 자원 할당 거부 (Banker's algorithm)
                OS는 자원의 상태를 감시하고, 프로세스는 사전에 자기 작업에서 필요한 자원의 수를 제시한다. OS는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태인지 면밀하게 분석해서, 안전한 상태를 유지할 수 있는 요구만을 수락, 그  외의 요구는 만족될 때까지 계속 거절.

  • 교착상태 발견
        - 시스템의 상태를 감시하는 알고리즘을 통하여 교착상태를 검사하는 알고리즘
        - 시스템의 자원할당 그래프로 교착상태 검출
        - 교착상태 발생 시 자원할당 소거

  • 교착상태 회복
        - 교착상태에 포함되어 있는 모든 프로세스들을 중지시킴.
        - 교착상태에 포함되어 있는 각 프로세스의 수행을 롤백시킴
        - 교착상태게 없어질 때까지 교착상태에 포함되어 있는 프로세스들을 하나씩 종료.
        - 교착상태가 없어질 때까지 교착상태에 포함되어 있는 자원을 하나씩 선점시킴.





 교착상태 해결을 위한 전체 시스템 설계
  1. 내부 시스템 자원을 순서화
            - PCB, 버퍼, Semaphore 등의 자원 순서화
  1. 사용자 작업에 대한 주기억장치 선점
            - 선점은 Paging, Segmentation, Swapping 시스템에서 가장 효율적인 접근법
  1. ​작업이나 작업단계의 자원필요량 산정
  2. 교체 가능 공간 사전 할당 - 요구된 기억장치를 사전에 할당


저작자표시 비영리 변경금지

'운영체제' 카테고리의 다른 글

커널(Kernel), 마이크로 커널&모놀리식 커널  (0) 2018.08.28
캐시 메모리(Cache Memory)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26
병행성과 상호배제&상호배제 알고리즘  (0) 2018.08.26
Thread  (0) 2018.08.24


세마포어
  • 병행처리를 위한 프로세스 동기화 기법
  • 운영체제의 자원을 경쟁적으로 사용하는 다중 프로세스에서, 행동을 조정하거나 동기화하는 기술
  • 다익스트라가 제안
  • 세마포어는 Busy-waiting을 피한다.

세마포어를 이용한 상호배제(Mutual Exclusion)

                    <세마포어 함수 정의>

  • semWait 연산 : 세마포어 값을 확인한다. 세마포어 값을 확인해서 0이면, semWait를 호출한 프로세스를 세마포어 큐에 넣고 블록상태로 전이시킨다.
          만약 세마포어 값이 1이면, 값을 0으로 변경시키고 프로세스는 
          계속 수행된다.
  • semSignal 연산 : 블록되어 있는 프로세스가 존재하는지 확인한다. 만일 블록되어 있는 프로세스가 존재하면 그 프로세스를 깨운다. 반면 블록되어 있는 프로세스가 존재하지 않으면 세마포어 값을 1로 설정한다.

    
            < 세마포어를 이용한 상호배제 >

강성 세마포어 & 약성 세마포어
  • 강성 세마포어 : 큐에 연결된 프로세스들을 깨울 때 선입선출(FIFO) 정책을 사용하는 세마포어.
  • 약성 세마포어 : 큐에 연결된 프로세스들을 깨울 때 순서를 특별히 명시하지 않은 세마포어.


세마포어의 유형
  • Binary Semaphore 
            목적 : 상호배제, 프로세스 동기화
            세마포어 변수: 0 or 1
  • Count Semaphore(general semaphore) 
            목적 : 초기에 동시에 진행가능한 프로세스 개수 정의 가능
            세마포어 변수 : 0,1,2 ....



세마포어와 Mutex의 차이
  • mutex는 객체를 얻거나 반납할 때 사용하는 프로그래밍 플래그이다. 사용하려는 데이터가 공유될 수 없거나 또는 연산이 동시에 수행될 수 없는 경우, mutex가 설정되고 접근/연산을 시도한 프로세스들은 블록된다. 데이터에 대한 접근이 더 이상 필요 없거나 또는 연산이 완료되면 mutex의 락은 해제된다.
  • mutex와 이진 세마포어의 핵심 차이는 mutex의 경우 락을 설정한(값을 0으로 설정한) 프로세스만이 락을 해제할 수 있다. 반면, 이진 세마포어의 경우 락을 설정한 프로세스와 해제하는 프로세스가 서로 다를 수 있다.




저작자표시 비영리 변경금지

'운영체제' 카테고리의 다른 글

캐시 메모리(Cache Memory)  (0) 2018.08.28
교착상태(Deadlock)  (0) 2018.08.28
병행성과 상호배제&상호배제 알고리즘  (0) 2018.08.26
Thread  (0) 2018.08.24
Context Switch (문맥 교환)  (0) 2018.08.23

+ Recent posts

티스토리툴바