메모리 관리
  • 주기억장치는 운영체제(상주 모니터, 커널)를 위한 곳과, 현재 수행중인 프로그램을 위한 공간으로 구분된다.
  • 멀티프로그래밍 시스템에서는 주기억장치의 사용자 영역이 다수의 프로세스들을 수용하기 위해 더 여러개로 나뉘게 된다. 이와 같은 분할 작업은 운영 체제에 의해서 동적으로 이루어지며, 이를 메모리 관리라고 한다.


메모리 관리 관련 용어
  • 프레임 (Frame) : 주기억장치의 고정 길이 블록
  • 페이지 (Page) : 보조기억장치에 있는 데이터의 고정 길이 블록. 한 페이지의 데이터는 한 프레임의 주기억장치에 임시로 복사될 수 있다.
  • 세그먼트 (Segment) : 보조기억장치에 있는 데이터의 가변 길이 블록. 전체 세그먼트는 주기억장치의 사용 가능한 공간에 임시로 복사될 수 있거나 (세그먼테이션), 주기억장치로 일일이 복사될 수 있는 페이지들로 분할 될 수 있다. (세그먼테이션과 페이징의 결합)




메모리 관리기법 종류
  • 반입 정책(전략)
        - 언제 메모리로 적재할 것인지 결정하는 전략
        - 메인메모리에 적재할 다음 프로세스의 반입시기를 결정
        - 기법 : 요구반입기법, 예상반입기법

  • 배치 정책(전략)
        - 어디로 위치시킬 것인지 결정하는 전략
        - 디스크에서 반입한 프로세스를 메인 메모리의 어느 위치에 저장할 것인지를 결정하는 방법
        - 기법 : 최초적합(first-fit), 최적적합(best-fit), 최악적합(worst-fit), 순환적합(next-fit)
        - 최초적합: 메모리의 처음부터 검사해서 크기가 충분한 첫 번째 사용 가능한 메모리 블록을 선택한다.
        - 최적적합: 요청한 크기와 가장 근접한 크기의 메모리를 선택한다. 가용 공간들에 대한 목록이 그 공간들의 크기 순서대로 정렬되어 있지 않다면 최적인 곳을 찾기 위해 전체를 검색해야 한다.
        - 최악적합: 사용 가능한 공간들 중에서 가장 큰 것을 선택한다. 할당해주고 남는 공간을 크게하여 다른 프로세스들이 그 공간을 사용할 수 있도록 하는 전략. 최적 적합과 마찬가지로, 가용 공간들에 대한 목록이 그 공간들의 크기 순서대로 정렬되어 있지 않다면 최적인 곳을 찾기 위해 전체를 검색해야 한다.
        - 순환적합: 가장 최근에 배치되었던 메모리의 위치에서부터 검사를 시작해 크기가 충분한 다음 위치의 사용 가능한 메모리 블록을 선택한다.

  • ​교체 정책
        - 메모리의 어느 영역을 교체하여 사용할 것인지 결정하는 전략
        - 재배치 기법으로 메인 메모리에 있는 어떤 프로세스를 제거할 것인가를 결정
        - 기법: 프로세스 Swap In/Out



연속 메모리 할당 방식

  • 연속 메모리 할당
        - 메모리의 영역을 사용자를 위한 공간과 운영체제 상주를 위한 공간으로 구분하는 기법
        - 메모리를 운영체제 루틴이 들어있는 부분(모니터)과 사용자 프로그램이 들어있는 부분, 사용되지 않는 부분으로 구분
        - 사용자가 모든 메인 메모리에 대한 제어권을 가짐
        - 사용자 프로그램이 주소를 잘못 지정하면 운영체제 파괴
        - 운영체제 파괴 방지를 위한 프로세서 내 경계 레지스터를 둠
        - 사용자 프로그램이 메모리 참조할 때마다 경계 레지스터 검사 이후 실행

  • ​고정 분할
        - 메모리를 여러 개의 고정된 크기로 분할. (partition)
        - 고정된 크기의 분할 영역에 프로세스가 각각 할당됨.
        - 물리주소는 분할 기준 레지스터(PBR) 값에 논리 주소를 더하여 생성됨
        - 강점 : 구현이 간단하다 = 운영체제에 오버헤드가 거의 없다.
        - 약점 : 내부단편화로 인한 비효율적인 사용. 최대 활성 프로세스의 수가 고정됨
           


  • 가변 분할(동적 분할)
        - 메인메모리의 사용자 공간 전체를 하나의 분할 영역으로 설정하고, 이후 프로세스의 움직임에 따라 분할 형태를 동적으로 변화시키는 기법
        - 강점 : 내부단편화가 없고, 주기억장치를 보다 효율적으로 사용할 수 있다.
        - 약점 : 외부 단편화를 해결하기 위한 메모리 집약(Compaction)이 요구된다. 따라서 처리기 효율이 나빠진다. (오버헤드 발생)




 분산 메모리 할당 방식
  • 페이징 기법
        - 동일 크기의 프레임 분할.
        - 페이지라고 불리는 프로세스 영역들이 프레임(페이지 프레임)이라고 불리는 고정크기 블록의 메모리 영역에 할당.
            => 즉, 주기억장치를 고정 사이즈 파티션으로 나누고 각 프로세스 또한 같은 크기의 고정 조각으로 나눈다!
        - 내부 단편화 발생, 외부 단편화 없음
        - 각 페이지를 연속된 공간에 넣을 필요가 없지만, 프로세스의 각 페이지들에 해당하는 프레임의 위치를 저장하기 위해 운영체제는 각 프로세스마다 하나의 페이지 테이블(page table)을 유지한다.
        - 페이지 테이블 : 논리메모리 페이지 번호와 물리메모리 프레임 번호를 매핑.


  • 세그먼트 기법(세그먼테이션)
        - 분할되는 프로그램 블록들을 세그먼트라 하며, 각 세그먼트들의 크기는 서로 다르게 되어 있다.
        - 크기가 다르기 때문에 주기억장치 영역을 페이징 시스템에서와 같이 미리 분할해 둘 수 없으며, 주기억장치에 적재될 때 빈 공간을 찾아 할당하는 방법.
        - 단점 : 프로그래머가 세그먼트의 최대 크기를 알고 있어야한다.
                    논리주소와 물리주소 간에 복잡한 관계가 존재한다.
                    외부 단편화 문제 발생.
        - 동적 할당과 차이점은 세그먼테이션의 경우 프로그램이 하나 이상의 파티션을 차지할 수 있고, 이 파티션들이 연속적일 필요는 없다는 점.


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

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

CPU Scheduling (CPU 스케줄링)  (0) 2018.08.30
커널(Kernel), 마이크로 커널&모놀리식 커널  (0) 2018.08.28
캐시 메모리(Cache Memory)  (0) 2018.08.28
교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26


CPU Scheduling
  • Process 작업수행을 위해 언제, 어느 Process에 CPU를 할당할 것인지를 결정하는 작업.




CPU Scheduling 요건 (Scheduling Criteria)
  • 처리 능력(Throughput) 최대화 : 주어진 시간에 최대한 많은 작업을 처리
  • 반환시간(Turnaround time) 최소화 : 프로세스가 시스템으로 진입한 후부터 종료할 때까지 걸린 시간의 최소화
  • 대기시간(Waiting time) 최소화 : Ready queue에서 기다리는 시간 최소화
  • 응답시간(Response time) 최소화 : 대화형 프로세스가 시스템에 요구를 한 후 이에 대한 시스템으로부터의 첫 번째 응답이 올 때까지의 시간의 최소화
  • CPU 이용률(Utilization) 극대화





Process 상태전이도와 Scheduler의 종류 및 역할

  • 프로세스 상태 전이도
    
    <출처 : ilifo >

  • 스케줄러의 종류 및 역할
        - 장기(Job) Scheduler : 프로세스 선택, 주기억장치 할당 (보류-준비)
        - 중기(Process) Scheduler : 프로세스 수에 따라 디스크에 보냄(대기-보류) , 프로세스들이 CPU를 서로 차지하려고 할 때 프로세스를 기억장소(main memory)에서 잠시 빼내고 다시 메인 메모리에 들여보내 실행시킬 수 있는 교체(Swapping) 기법을 사용한다.
        - 단기 Scheduler : 실행 준비된 프로세스에 CPU 할당 (준비-실행)





CPU Scheduling 기법
  • 선점(Preemptive) 스케줄링 
        - 개념 : 어떤 프로세스가 CPU를 할당 받아 실행 중에 있어도 다른 프로세스가 실행 중인 프로세스를 중지시키고 CPU를 강제로 점유할 수 있다.  (우선순위에 따라 CPU를 빼앗을 수 있다.)
                    높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유리
        - 장점 : 비교적 빠른 응답
                   대화식 시분할 시스템에 적합
        - 단점 : 높은 우선순위 프로세스들이 들어오는 경우 오버헤드 초래

  • 비선점(Non-Preemptive) 스케줄링
        - 어떤 프로세스가 CPU를 할당 받으면 그 프로세스가 종료되거나 입출력 요구가 발생하여 자발적으로 중지될 때까지 계속 실행되도록 보장한다. (CPU를 빼앗지 못한다.)
        - 일괄처리 시스템에 적합.
        - 장점 : 응답시간 예상이 용이
                   모든 프로세스에 대한 요구를 공정하게 처리
                   스케줄러 호출 빈도가 낮고 Context switching에 의한오버헤드가 적다.
        - 단점 : CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시킬 수 있으므로, 처리율이 떨어질 수 있다.







비선점(Non-Preemptive) 스케줄링 알고리즘
  • FCFS(First-Come-First-Served)=FIFO(First-In-First-Out)
        - 프로세스가 대기큐(준비큐)에 도착한 순서대로 CPU 할당하는 스케줄링 알고리즘.
        - Convoy Effect 발생 가능 (Burst time이 긴 프로세스가 CPU 독점)
        - 단독적 사용이 거의 없으며, 다른 스케줄링 알고리즘에 보조적으로 사용 (우선순위 스케줄링, RR 스케줄링 등)

  • SJF (Shortest Job First)
        - 준비 큐 내의 프로세스 중 CPU 점유시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 스케줄링 알고리즘.
        - 주어진 프로세스 집합에 대해서 평균 대기시간이 최소가 되는 최적 알고리즘
        - CPU 요구시간이 긴 작업과 짧은 작업간의 불평등이 심하여, CPU 요구시간이 긴 프로세스는 Starvation(기아상태) 발생 가능.

  • HRN (Highest Response ratio Next)
        - 프로세스 처리의 우선순위를 CPU 처리 기간과 해당 프로세스의 대기 시간을 동시에 고려해 선정하는 스케줄링 알고리즘
        - Response ratio = (대기시간 + 서비스 시간) / 서비스 시간
        - 대기중인 프로세스 중 현재 Response Ratio가 가장 높은 것을 선택
        - SJF의 약점을 보완한 기법으로 긴 작업과 짧은 작업간의 불평등을 완화

  • 우선순위 스케줄링
        - 각 프로세스에 우선순위가 주어지고 우선순위에 따라 CPU 할당하는 스케줄링 알고리즘
        - 동일한 우선순위간은 FCFS 처리
        - 우선순위 결정 : 관리자에 의한 결정, 자원요구량에 의한 결정, CPU처리 시간에 의한 결정, 시스템에서 보낸 시간에 의한 결정 등 사용
        - 우선순위가 높은 작업이 계속적으로 들어오게 될 경우 우선순위가 낮은 프로세스는 starvation 발생 -> Aging 기법으로 해결







선점(Preemptive) 스케줄링 알고리즘
  • RR(Round Robin)
        - 시분할 시스템을 위해 설계된 선점형 스케줄링의 하나로서, 프로세스들 사이에 우선순위를 두지 않고, 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 스케줄링 알고리즘
        - 시간 단위동안 수행한 프로세스는 준비 큐의 끝으로 밀려나게 됨
        - 문맥 전환의 오버헤드가 큰 반면, 응답시간이 짧아지는 장점이 있어 실시간 시스템에 유리하다.
        - 시간 단위가 크면 FCFS와 같게 된다.

  • SRT(Shortest Remaining Time)
        - 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 실행.
        - 남은 처리 시간이 더 짧다고 판단되는 프로세스가 준비 큐에 생기면 언제라도 프로세스가 선점됨
        - 긴 작업은 SJF 보다 대기 시간이 길다.

  • 다단계 큐(Multilevel Queue)
        - 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘.

  • 다단계 피드백 큐(Multilevel Feedback Queue)
        - 다단계 큐 스케줄링에서 한 단계 발전된 방식으로, 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 영구적으로 할당되지만, 다단계 피드백 큐 스케줄링에서는 프로세스들이 큐를 갈아탈 수 있다.
        - 작업들이 서로 다른 유형의 작업들로 분류될 경우 사용.
        - 새로운 프로세스는 높은 우선순위, 프로세스의 실행시간이 길어질수록 점점 낮은 우선순위 큐로 이동 (맨 마지막 단계에서는 RR 처리)

        - 하위단계일수록 할당시간은 증가 (공평성 부여)
        <출처 : ilifo >

















    

저작자표시

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

메모리 관리  (0) 2018.09.01
커널(Kernel), 마이크로 커널&모놀리식 커널  (0) 2018.08.28
캐시 메모리(Cache Memory)  (0) 2018.08.28
교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26

커널 (Kernel)
  • 커널은 컴퓨터의 운영체제의 핵심.
  • main memory에 상주하며, 시스템에 존재하는 자원을 효율적으로 관리하는 자원 관리자.
                        <General UNIX Architecture, Traditional UNIX kernel>



커널의 역할
  • 보안 - 컴퓨터 하드웨어와 프로세스의 보안을 책임진다.
  • 프로세서 관리 - 처리 속도를 향상시키기 위해 여러 프로세서를 병렬로 연결하여 사용한다. 시스템에서 동작하는 프로세스도 커널에서 관리해야할 자원이고, 운영체제의 처리 요구에 맞춰 동작할 수 있도록 각 프로세스에 필요한 프로세서를 효율적으로 할당하고 수행하도록 관리한다.
  • 프로세스 관리 - 여러 프로세스가 동작할 수 있도록 각 프로세스를 생성하고 제거하며, 외부환경과 프로세스를 연결하고 관리한다. (스케줄링)
  • 메모리 관리 - 각각의 프로세스가 독립적인 공간에서 수행할 수 있도록 가상 주소 공간을 제공한다.
    이외에도 파일 시스템 관리, 디바이스 제어, 네트워크 관리가 있다.



모놀리식 커널(Monolithic Kernel,단일형 커널)과 마이크로커널(Micro Kernel)

  • 모놀리식 커널
        - 입출력 기능, 네트워크 기능, 장치 지원 등 운영체제의 일반적인 기능을 커널과 동일한 메모리 공간에 적재, 실행하는 기법.
       - 속도가 빠르고 디자인도 편리하지만, 잠재적 안정성 문제와 커널의 크기도 무지막지하게 커진다. 
        - Monolitic Kernel 방식을 따르는 운영체제 : 리눅스, 보통의 UNIX, 맥OS, MS-DOS





  • 마이크로 커널
        - 낮은 수준의 주소 공간 관리, 스레드 관리, 프로세스 간 통신(IPC)를 포함하고, 시스템 콜 같은 서비스, 디바이스 관리 등을 제외하여 안정성을 높이고, 커널 크기도 줄인 방식.
        - 안정성이 높고 보안도 높아지지만, 전반적인 퍼포먼스는 저하된다.
        - 이 방식을 따르는 운영체제 : AmigaOS, Minix, Mach, GNU hurd









     
     


저작자표시

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

메모리 관리  (0) 2018.09.01
CPU Scheduling (CPU 스케줄링)  (0) 2018.08.30
캐시 메모리(Cache Memory)  (0) 2018.08.28
교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26


캐시 메모리 (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


병행성의 주요 용어 정리
  • 경쟁 상태 (Race condition)
- 두개 이상의 쓰레드나 프로세스가 공유 자원을 동시에 접근하려는 상태.
  • 상호 배제 (Mutual exclusion)
     - 특정 프로세스가 공유자원을 사용하고 있을 경우 다른 프로세스가 해당 공유자원을 사용하지 못하게 하는 조건
  • 임계 영역 (Critical Section)
- 공유 자원을 접근하는 프로세스 내부의 코드 영역. 다른 프로세스가 이 영역에 있을 때, 이 프로세스 또한 이 영역을 수행할 수 없다.       
  • 기아 (Starvation)
     - 특정 프로세스가 수행 가능한 상태임에도 불구하고 매우 오랜 기간 동안 스케줄링 되지 못하는 경우.
  • 교착 상태 (Deadlock)
 - 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상.
  • 원자적 연산 (Atomic operation)
- 하나 또는 여러 개의 명령어들로 구성된 함수 또는 액션으로 더 이상 분할할 수 없는 단위. 따라서 다른 어떤 프로세스도 중간 상태를 볼 수 없으며, 연산을 중단 시킬 수 없다. 이 명령어들은 모두 수행되거나 하나도 수행되지 않음이 보장된다. 원자성은 병행 프로세스들에게 고립(isolation)을 보장한다.

    



 Critical Section 문제의 해결을 위한 필요조건
  • Mutual Exclusion
- 한 프로세스가 임계영역(Critical section)을 수행하고 있으면, 다른 프로세스는 그 임계영역을 수행 할 수 없다.
  • Progress
- 임계영역을 수행하고 있는 프로세스가 없고, 한 프로세스가 임계영역에 진입하려고 하면 즉시 임계영역에 들어갈 수 있어야 한다.
  • Bounded Waiting
- 임계영역에 접근하고자 하는 프로세스의 수행이 무한히 미루어져서는 안된다. 즉, 교착상태 및 기아가 일어나지 않아야 한다.





Mutual Exclusion 문제의 해결방안

  • 소프트웨어적 해결 알고리즘
    • 데커(Dekker) 알고리즘 - 두 프로세스가 동시에 임계 영역에 들어가려고 할 때 하나만 들어가게 하는 알고리즘. 한 프로세스가 이미 임계 영역에 있다면, 다른 프로세스는 전 프로세스가 끝나기를 기다린다. (busy waiting)
    • 피터슨(Peterson) 알고리즘 - 데커 알고리즘과 유사하며, 두 프로세스가 동시에 임계영역에 진입하려고 하면 turn 변수가 늦게 수행된 프로세스가 기회를 양보한다.
    • 빵집(Bakery) 알고리즘 - 데커/피터슨 알고리즘은 2개의 프로세스에 대해서만 가능하지만,  Bakery 알고리즘은 2개 이상의 프로세스에 대해서 사용 가능한 알고리즘이다.

  • 하드웨어적 해결 방법
    • Test & Set 
    • Compare & Swap
            - 하드웨어적 해결방법의 장점 : 단순하다. 사용하기 쉽다. 여러개의 임계 구역에서 사용 가능하다.
            - 하드웨어적 해결방법의 단점 : Busy-waiting이 발생(CPU 활용도 저하), Deadlock이 발생 할 수 있다.



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

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

교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26
Thread  (0) 2018.08.24
Context Switch (문맥 교환)  (0) 2018.08.23
프로세스 (개념, 상태, PCB)  (0) 2018.08.23

  1. 프로세스 & 쓰레드

프로세스의 특징
  • 자원 소유권 - 프로세스는 자신의 이미지를 위한 가상주소 공간을 포함
  • 스케줄링/실행 - 프로세스 수행은 하나 이상의 프로그램을 통과하는 수행 경로를 따른다. 한 프로세스는 다른 프로세스들과 번갈아 가면서(interleave) 수행될 수 있다. 따라서 프로세스는 프로세스 수행 상태와 디스패칭 우선순위를 가지며, 운영체제에 의해 스케줄되고 디스패치되는 개체

 쓰레드
  • 프로세스 안에서의 실행 단위
  • 실행 상태를 가진다

 CPU 디스패칭 단위는 쓰레드 또는 경량 프로세스라고 하며,
자원 소유권의 단위는 프로세스 또는 task라고 한다.





  2. Resources of Process and Thread - 프로세스와 쓰레드의 자원
 
  • 프로세스는 Code, Data, Stack, Memory for registers context(program counter, register etc.)로 구성된다
  • 쓰레드는 Stack, Memory for registers context(program counter, register etc.):thread control blcok로 구성된다
  • 프로세스 내의 모든 쓰레드들은 그 프로세스의 상태와 자원을 공유한다. 



     <한 프로세스 내부 모습(각 쓰레드는 각각 registers, stack을 가지며 code,data,files를 공유)>



   3. 멀티쓰레딩 (Multithreading)
  • 멀티쓰레딩이란 운영체제가, 하나의 프로세스 내에서 수행되는 여러 개의 쓰레드를 지원하는 기능이다.
  • 멀티쓰레딩에서 프로세스는 동시에 실행될 수 있는 쓰레드로 분할된다.
  • 단일 쓰레드 OS로는 MS-DOS, Original UNIX가 있다.
  • 멀티 쓰레드 OS로는 Windows, Solaris, Linux. Mach 등이 있다.

                                < Multithreading Example on a Uniprocessor >





   4. 멀티쓰레딩의 이점
  • 새로운 프로세스를 생성하는 시간보다, 기존 프로세스 내에서 새로운 쓰레드를 생성하는 시간이 더 짧다.
  • 프로세스 종료시간보다 쓰레드 종료시간이 더 짧다.
  • 프로세스들 간 교환보다 같은 프로세스에 있는 두 쓰레드 간 교환이 효율적이다.
  • 프로세스 간의 통신보다 한 프로세스 내에서 쓰레드 간의 통신이 더 빠르다. 
            -> 같은 프로세스 내에 쓰레드들은 메모리와 파일을 공유하기 때문에 커널을 호출하지 않는다.
            -> 프로세스 간 통신 (IPC) : 커널 호출 시간 필요 = 큰 오버헤드 필요




    5. Thread 유형
  • 사용자 수준 쓰레드
             - 쓰레드 관리와 관계된 모든 일은 응용이 수행하며 커널은 쓰레드의 존재를 알지 못한다.
             - 사용자 영역에서 쓰레드 연산을 수행
             - 사용자 수준 쓰레드의 장점
                    + 스케줄링 결정이나 프로시저 동기화를 위해 커널을 호출하지 않으므로 오버헤드가 적다.
                    + 운영체제에서 쓰레드를 지원 할 필요가 없으므로,어느 OS든 실행 할 수 있다. (즉, 이식성이 높다)
                    + 기존 OS 스케줄링을 방해하지 않고 응용에 맞춘 사용자 수준 쓰레드 스케줄링 알고리즘이 가능하다.
             - 사용자 수준 쓰레드의 단점
                    + 한 개의 사용자 수준 쓰레드가 블록되면, 그 프로세스의 모든 쓰레드가 블록된다.
                    
             
                                           

  • 커널 수준 쓰레드
            - 쓰레드 관리와 관련된 모든 작업이 커널에 의해 이루어진다. 
            - 응용 영역에는 쓰레드 관리를 위한 코드가 없고, 단순히 커널 쓰레드 기능에 대한 API가 있다. (ex. Windows, Linux)
            - 커널 수준 쓰레드의 장점
                + 커널이 각 쓰레드를 개별적으로 관리 할 수 있다.
                + 응용 프로그램은 입출력 작업이 끝날 때까지 다른 쓰레드를 사용해 다른 작업을 할 수 있다.
            - 커널 수준 쓰레드의 단점
                + 스케줄링과 동기화를 위해 커널을 호출해야하므로 오버헤드가 증가된다.
                + 이식성이 떨어진다.
                + 시스템이 달라지면 해당 운영체제에서 제공하는 쓰레드 API를 사용해 프로그램을 수정해야 한다.

                                           





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

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

교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26
병행성과 상호배제&상호배제 알고리즘  (0) 2018.08.26
Context Switch (문맥 교환)  (0) 2018.08.23
프로세스 (개념, 상태, PCB)  (0) 2018.08.23




문맥 교환 (Context Switch)
  •  문맥 교환(Context Switch)이란 하나의 프로세스가 CPU를 사용 중인 상태에서 다른 프로세스가 CPU를 사용하도록 하기 위해, 실행중인 프로세스의 상태(문맥)를 보관하고 새로운 프로세스의 상태를 적재하는 작업.
  •  한 프로세스의 문맥은 그 프로세스의 프로세스 제어 블록(PCB)에 저장되어 있다.






Context Switch는 언제 일어나는가?
  • Termination of a process (프로세스의 종료)
            ☞ 에러,예외가 나타나거나 보통의 프로세스의 종료
  • Expiration of time slice ( time slice 만료 )
            ☞ 가능한 CPU 점유 시간이 만료되었을 경우
  • Blocking system calls (also called supervisor call)
            ☞ I/O 요청, 파일 오픈과 같은 시스템 콜의 경우
            ☞ Page fault  - 메모리 주소가 가상 메모리에 있으므로 main memory로 가져와야 한다
  • I/O 인터럽트
            ☞ I/O가 완료되면 Block 상태의 프로세스를 Ready 상태로 바꾼다.
            


Steps of Context Switch  - Context Switch 단계

  1. 프로그램 카운터와 다른 레지스터들을 포함한 프로세스의 문맥을 저장
  2. 현재 실행 중인 프로세스(Running 상태에 있는)의 PCB를 갱신
  3. PCB를 적당한 Queue로 옮긴다. ( Queue - Ready or Blocked or ready/suspend)
  4. 실행 할 다른 프로세스를 선택
  5. 선택 된 프로세스의 PCB를 갱신
  6. 메모리 관리 데이터 구조 갱신
  7. 선택 된 프로세스의 문맥 복원



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

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

교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26
병행성과 상호배제&상호배제 알고리즘  (0) 2018.08.26
Thread  (0) 2018.08.24
프로세스 (개념, 상태, PCB)  (0) 2018.08.23

Process : 프로세스
  • 실행중에 있는 프로그램
  • 프로세서에 할당되어 실행 될 수 있는 entity
  • 프로세스 제어 블록(PCB : Process Control Block)을 할당 받는 개체
  • 컴퓨터에서 실행되는 프로그램의 인스턴스



Reasons for Process Creation : 프로세스의 생성 이유
  1. OS에 의해 생성
  2. Interactive login  - 터미널에서 사용자가 시스템에 로그인
  3. 존재하는 프로세스에 의해 생성 - 사용자 프로그램은 OS에게 자식 프로세스를 생성하라고 요청 할 수 있다.
  4. user command에 의해 생성 
 ☞ foreground (interactive) mode에서 프로그램 실행   
 ☞ background (batch) mode에서 프로그램 실행





Process States : 프로세스 상태   

  • Dispatcher(kernel function)은 PC(Program Counter)에 있는 주소값을 가져와서 한 프로세스로부터 다른 프로세스로 switch 해준다. ( 다른 프로세스로 자원을 할당해준다)
  • 프로그램 카운터(Program Counter,PC)는 중앙처리장치 내부에 있는 레지스터 중의 하나로서, 다음에 실행될 Process의 주소값이 저장되어있다. (=명령어 포인터)

<Five-State Process Model>
  • Ready : Process가 CPU를 점유 할 준비가 된 상태
  • Running : Process가 CPU를 점유하고 있는 상태
  • Blocked (= wait state, sleep state) : Process가 event가 나타나는 것을 기다리는 상태 (ex. I/O completion)




프로세스 제어 블록 ( PCB : Process Control Block) = (TCB : Task Contol Block)
  • 특정한 프로세스를 관리할 필요가 있는 정보를 포함하는 운영체제 커널의 자료구조
  • 프로세스가 생성될 때마다 고유의 PCB가 생성되고, 프로세스가 Terminated 되면 PCB는 제거
  • OS에 의해 만들어지고 관리
  • PCB가 가지고 있는 정보
             ☞ 프로세스 식별자(Process Identifier)
            ☞ 프로세스 상태 (Process State) 
            ☞ 프로그램 카운터 (PC:Program Counter)
            ☞ 메모리 관리 정보 : 해당 프로세스의 주소 공간 등
            ☞ CPU 레지스터 및 일반 레지스터
            ☞ CPU 스케줄링 정보 : 우선순위, 최종 실행시각, CPU 점유시간 등
            ☞ 프로세스 계정 정보 : 페이지 테이블, 스케쥴링 큐 포인터, 소유자, 부모 등
            ☞ 입출력 상태 정보



 프로세스 문맥 ( Process Context )
  • Context : 프로그램의 실행 환경
  • User Context 
             - Code : 실행 될 사용자 프로그램 코드 (instructions) 
             - Data : 프로세스의 전역 변수
             - User Stack
                   ☞ LIFO 구조
                   ☞ 사용자 기능을 호출하는 정보를 저장하는 데 사용 (  함수의 지역 변수, 함수의 인자, register value )
  • System Context
            ☞ System stack ( kernel stack) : 커널 함수를 호출하기 위한 정보를 저장하는 데 사용
            ☞ Process Control Block (PCB) : 프로세스를 제어하기 위해 운영 체제에 필요한 데이터



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

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

교착상태(Deadlock)  (0) 2018.08.28
세마포어와 뮤텍스 (Semaphores&Mutex)  (0) 2018.08.26
병행성과 상호배제&상호배제 알고리즘  (0) 2018.08.26
Thread  (0) 2018.08.24
Context Switch (문맥 교환)  (0) 2018.08.23

+ Recent posts

티스토리툴바