19. 디스크 스케쥴링4

4) SCAN 스케쥴링

 (1) SCAN 스케쥴링
    * 디스크 해드가 어느 한쪽 방향의 끝으로 이동하면서 요청한 트랙을 처리하고 다시 다른 방향으로 이동하면서 처리하는 스케쥴링이다.
    * 53 ---> 0 ---> 199 ---> 0     / 화살표시는 방향을 의미함

 (2) C-SCAN 스케쥴링
    * 디스크 해드가 어느 한쪽 방향의 끝으로 이동하면서 요청한 트랙을 처리하고 다시 반대 방향의 끝으로 한 번에 즉시 이동한 다음 다시  요청한 트랙을 처리하는 스케쥴링이다.
    *  53 ---> 199 =점프=> 0 ---> 199

 (3) LOOK 스케쥴링
    * SCAN 스케쥴링과 동일하지만 어느 방향을 끝까지 해드가 이동하지 않고 요청작업이 있는 곳까지만 이동한다음 다시 다른 방향으로 해드가 움직이는 스케쥴링이다.
    *  53 ---> 34 ---> 183 ---> 34

 (4) C-LOOK 스케쥴링
    * C-SCAN 스케쥴링과 LOOK 스케쥴링의 결합된 형태이다.
      어느 한족 방향으로 이동하면서 요청작업을 처리하지만 디스크의 끝까지 이동하는 것이 아니라 마지막 요청 트랙까지만 이동하고 반대방향의 최초 요청 트랙으로 즉시 이동한뒤 다시 해드가 디스크 요청을 처리하는 스케쥴링이다.
    *  53 ---> 183 =점프=> 34 --->183

참고) SCAN 스케쥴링은 이동 거리는 많을 수 있지만 탐색시간이 최소가 되어 빠른 처리가 가능하다.
      SCAN 스케쥴링은 엘리베이터 알고리즘이라고도 한다.
      엘리베이터와 흡사한 이동특성을 보이고 있기 때문이다.

19. 디스크 스케쥴링3

3) SSTF(Shortest Seek Time First, 최소 탐색시간 우선 스케쥴링)

  * 제일 가까운 트랙의 요청부터 처리하는 스케쥴링

  * 예시)
    디스크 트랙:  0 ~ 199
    현재 해드의 위치: 53 트랙
    디스크 요청 트랙:  98  183  37  122  14  124  65  67

    총 이동거리: 236 트랙

  * 기아(Starvation)이 발생할 수 있다.
  * 가장 효과적인 방법은 아니다.
   

19. 디스크 스케쥴링2

2) FCFS(First-Come, First-Served, 선입선처리 스케쥴링)

  * 제일 먼저 요청한 작업부터 처리하는 스케쥴링이다.

  * 예시)
    디스크 트랙:  0 ~ 199
    현재 해드의 위치: 53 트랙
    디스크 요청 트랙:  98  183  37  122  14  124  65  67

    총 이동거리: 640 트랙

  * 가장 단순하면서 공정하긴 하지만 성능이 좋지 않다.
    디스크 요청이 흩어져 있는 경우 탐색시간이 오래걸려 처리량이 감소한다.

19. 디스크 스케쥴링1

1) 디스크 스케쥴링이란?
  * 디스크 엑세스 시간
   : 탐색 시간(Seek Time) - 디스크 해드가 해당 트랙으로 이동하는 시간
   : 회전 시간(Rotational Delay) - 디스크 회전 시간
   : 전송 시간(Transfer Time) - 디스크의 데이타가 읽혀지고 메인메모리에 전달되는 시간

  * 멀티프로그래밍 환경에서는 많은 프로세스들이 디스크 서비스(I/O 처리)를 받기위해 I/O Queue(입출력 대기 큐)에 대기하게 된다.

  * 운영체제는 어떤 방식으로 I/O Queue를 처리할 것인가를 결정해야 한다.
    이를 처리하는 알고리즘을 디스크 스케쥴링이라고 한다.

  * 디스크 스케쥴링의 알고리즘의 종류
   : FCFS(First-Come, First-Served, 선입선처리 스케쥴링)
   : SSTF(Shortest Seek Time First, 최소 탐색시간 우선 스케쥴링)
   : SCAN 스케쥴링 (또는엘리베이터 알고리즘; Elevator Algorithm)
     - 순수 SCAN 스케쥴링
     - C-SCAN 스케쥴링
     - LOOK 스케쥴링
     - C-LOOK 스케쥴링

18. 파일 할당4

4) 색인 할당(Indexed Allocation)
  * 파일 1개당 1개의 인덱스 블럭을 지정한다.
  * 인덱스 블럭에 해당 파일에 대한 포인터 정보를 저장해 놓는다.
  * 디렉토리는 인덱스 블럭을 가리키고 있는다.
    (연결 할당에서는 최초 위치의 블럭을 가리키고 있음)
  * Unix, Linux 등에서 사용하고 있다.

  * 장점
   : 순차 접근(sequential access)이 가능하다.
   : 직접 접근(Direct access)이 가능하다.
   : 외부 단편화가 없다.

 * 단점
  : 파일 마다 인덱스 블록을 할당해야 하기 때문에 부수적 저장공간의 손실이 있다.
   1 byte 파일 저장하기 위해
    => 데이터 블록 1개 + 인덱스 블록 1개가 필요하다. 즉, 내부 단편화가 크다.

 * 파일의 최대 크기
   : 만약 1 block이 512 byte 이고 인덱스 1개가 4 byte 라면
     512 / 4 = 128개의 인덱스를 가질 수 있다.
    그렇다면 최대 파일 사이즈는 128 X 512 = 64 KB 가 된다.
   : 해결 방법: Linked, Multilevel index, Combined 등으로 인덱스 블럭을 다수개 두고 서로 연결 지어 놓는다.

18. 파일 할당3

2) 연결 할당(Linked Allocation)

  * 파일 => 데이터가 저장된 블럭들의 연결된 집함
  * 파일 디렉토리(directory)는 제일 처음(시작) 블록만 가리킨다.
   그리고 각 블록들은 다음 블럭의 위치(포인터)를 가지고 있다.

  * 장점
   : 새로운 파일 생성시 비어있는 임의의 블록을 첫 블록으로 결정한다.
   : 파일이 커지면 다른 블록을 할당하고 연결을 지어준다.
   : 따라서 외부 단편화가 없다.

  * 단점
   : 순차 접근(sequential access)만 가능하고 직접 접근(Direct access)은 불가하다.
   : 포인터 저장을 위해 4바이트 이상 손실이 있다.
   : 낮은 신뢰성 - 중간 블럭에 bad sector가 발생하여 포인터가 끊어지면 그 이하는 접근이 불가능 하다.
   : 느린 속도 - 디스크 헤더가 블럭들을 읽기 위해 많이 움직여야 한다.

 * FAT 시스템
   : MS사에서 연결할당을 응용하여 속도가 느리고 낮은 신뢰성을 보안하여 자체적으로개발한 파일 시스템이다.
   : MS-DOS, OS/2, Windows 등에서 사용
   : FAT = File Allocation Table
     즉, 파일의 pointer를 모아둔 테이블
   : 포인터들만 모은 테이블 (FAT) 을 별도 블록에 저장
   : 직접 접근(Direct access)이 가능하다.
     FAT의 포인터를 찾아서 해당 디스크위치로 해드를 이동해서 원하는 데이터를 읽는다.
   : FAT은 일반적으로 메모리 캐싱 즉, 부팅시에 FAT이 메모리에 로드된다.
    따라서 FAT을 읽는 속도는 빠르고 수시로 업데이트된다.
   : FAT 내용만 있으면 중간에 bad sector가 있어도 다 읽을 수 있습니다.
   : FAT이 소실될 것을 대비하여  FAT 복사 본을 따로 저장해 둔다.
     즉, 기본적으로 FAT은  2개 이다.
   : 파일을 디스크에서 읽는 속도는 느릴 수 밖에 없다. 그러나 외부 단편화는 해결된다.
   : FAT 을 위해 어느 정도 공간을 할당하느냐에 따라 FAT 12, FAT 16, FAT 32 로 구분

18. 파일 할당2

1) 연속 할당(Contiguous Allocation)

  * 각 파일에 대해 디스크 상의 연속된 블록을 할당
   즉, 같은 파일은 연속된 블럭에 저장이 되어진다.
  * 옛날 IBM 에서 사용

  * 장점
   : 디스크 헤더의 이동 최소화 = 빠른 i/o 성능
   : 동영상, 음악, VOD 등에 적합
   : 순차 접근 즉, 순서적으로 읽을 수 있음 (Sequential access)
   : 직접 접근 즉, 특정 부분을 바로 읽을 수 있음(Direct access)
     순서적으로 저장되어져 있기 때문에 바로 원하는 위치에 접근이 가능하다는 의미임.

 * 단점
   : First-fit, Best-fit, Worst-fit 문제 발생
   : 외부 단편화가 심하다. 사용할 수 없이 버려지는 공간이 많아지게 된다.
   : 압축(compaction) 가능하지만 시간이 오래 걸림(초창기 MS-Dos)
   : 파일의 사이즈가 계속 커질 경우 처리하기 어렵다.

 참고) 이러한 단점 때문에 대안으로 연결 할당 출현.

18. 파일 할당1

1) 파일 시스템 개요

 * 1 sector size = 512 bytes
 * cluster : 여러 개의 섹터(sector, 하드디스크의 물리적 최소 단위)를 묶은 단위
 * cluster = block
 * 1 block size
   : 보통 4 KB (= 8 sectors) : 디스크에 블럭 단위로 읽기/쓰기 실행함.
   : 4 MB (4,096 KB) File 저장 => 1,024개의 Block 사용
   : block device 의 특징 - sector 단위로 처리하면 너무 작아서 읽고/쓰기 어려움
                             - block 단위로 처리하면 저장 공간의 손실이 발생한다.
                             - 아래 이미지 => 1 byte 저장을 위해 1 block = 4 KB 디스크 할당

참고) NTFS에서는 700 byte 이하 작은 파일은 MFT(Master File Table) 엔트리에 직접 저장해서 디스크 할당이 0 byte가 된다. 700 byte 초과 부터 블럭(클러스터)을 할당한다.

 * Disk = pool of free blocks
 * directory

   파일 속성(File Attribute)
    < 보이는 정보 >
    - 파일 이름 : 사용자들이 이해할 수 있는 형태로 붙여짐.
    - 파일 타입 : 다양한 파일 형식을 지원하는 시스템의 경우 필요함.
    - 파일 크기 : 파일의 크기
    - 파일 소유자 : 파일에 대한 읽기, 쓰기, 실행 권한(액세스)의 제어
    - 저장 위치 : 파일이 저장된 장치
    - 생성 날짜 : 파일이 만들어진 일시
   < 보이지 않는 정보 >
    - 시작 블록 번호: 파일이 저장된 블럭들의 시작 블럭 번호

17. 페이지 크기

* 가상 메모리의 요구 페이징에서 페이지 크기는 어느 정도가 적당한가?
  : 명확히 정해진 크기가 있지는 않다. 즉, 꼭 커야 좋다거나 작아야 좋다는 결론을 얻을 수는 없다.

  : 그러나 하나의 프로세스 크기가 점차 커지고 있기 때문에 오늘날 페이지 크기도 점차 크게 설정하는 경향이 있다. 즉, 프로세스가 커지면 페이지도 커지게 된다.
  : 512 byte, 1 Kb, 2 Kb, 4Kb → 4MB, 16 MB

 * 페이지 크기를 결정하는 기준
   : 내부 단편화(Internal Fragmentation)
   : Page-in, page-out 시간 - I/O Overhead
   : 페이지 테이블(Page Table) 크기
   : 메모리 해상도(Memory resolution) - 필요한 내용만 메모리에 담을 수 있는 정도
   : 페이지 부재(Page fault) 발생 확률

 * 페이지 크기가 작을 수록 좋은 기준
   : 내부 단편화
     - 페이지가 작을 수록 버려지는 메모리의 내부 공간(내부 단편화)도 작아진다.
   : 메모리 해상도
     - 페이지가 크면 불필요한 영역까지 함께 적재될 수 밖에 없다. 반대로 적을 수록 필요한 부분만 메모리에 적재되는 정밀도가 증가한다.

 * 페이지크기가 클 수록 좋은 기준
   : Page-in, Page-out 시간
     - I/O 시간은 대부분 디스크의 해드 이동시간이다. 페이지가 클 수록 한 번 이동해서 많은 데이타를 읽어 올 수 있는 장점이 있다.
   : Page Table Size
     - 페이지가 클 수록 페이지 테이블의 열수는 적게 된다.
   : Page Fault 발생 확률
     - 페이지가 클 수록 하나의 페이지 내에 많은 내용을 담고 있기 때문에 페이지 재사용 가능성이 높게 되고 메모리 국지성에 의해 페이지 부재도 덜 발생하게 된다.


* 페이지 테이블(Page Table)
  : 페이지 테이블은 뭘로 만들 것인가?
    - CPU의 레지스터로 구현한다면, 너무 비싸다
    - Memory내에 둔다면 너무 느려진다.
    - 따라서 별도의 Chip(TLB: translation look a side buffer)으로 만든다.


  : 따라서 페이지 테이블은 별도의 chip(TLB 캐시)으로 제작되었다.
  : 그러나 오늘날 반도체 기술의 발달로 CPU 내에 함께 내장되어져 있다.

16 프레임 할당4

 (2-2) 페이지 부재 빈도(PFF: pAGE Fault Frequency)
      * 각 프로세스에 대해 페이지 부재(Page Fault)가 발생할 때 마다 기록을 한다.
      * 페이지 부재율의 상한선과 하한선을 설정하고
       : 페이지 부재율이 상한선을 초과하면
           - 프레임 할당이 너무 적다는 것을 의미하므로 프레임을 추가하여 늘려준다.
       : 페이지 부재율이 하산선아래로 내려가면
         - 프레임 할당이 너무 많아서 메모리가 낭비되고 있다는 것이므로 프레임을 회수하여 줄여준다.

      * 페이지 부재(Page Fault)가 적당한 기준범위내에서 발생하도록 유지한다.

16 프레임 할당3

3) 동적 할당(dynamic allocation)
  * 프레임을 동적으로 요구되는 수 혹은 적당량 만큼 할당하는 방법

   (2-1) 작업 집합 모델(Working set model)
    * 가장 최근에 참조된 프레임은 이후에 또 참조될 가능성이 높다는 가정에서 출발한다. 이는 메모리의 지역성(국지성, Locality)에 기반한다. 따라서 가장 최근에 참조된 페이지 집합을 작업 집합(Working set)이라고 한다.
    * 최근에 참조된 페이지들(작업 집합)을 메인 메모리에 유지시켜 프로세스가 빠르게 실행될 수 있도록 하는 것이 작업 집합 모델이다.

    * 작업 집합 모델에서는 작업 설정 크기(WSS, Working Set Size)의 결정이 중요하다.
      : WSS는 과거 어느 시간까지를 그 범위로 할 것인가에 따라 달라지게 된다. 그 범위값을 델타(∆ or Working Set Window)라고 한다.
      : 시간에 따라 WSS는 그 크기가 급격히 변화하기도 한다.

    

      * 작업 설정 크기(WSS)에 따른 페이지 프레임 수와 페이지 부재율과의 관계

16 프레임 할당2

2) 정적 할당(static allocation): 균등 할당, 비례 할당
  (1-1) 균등 할당(Equal allocation)
    * 가용한 프레임을 모든 프로세스에 균등하게 할당하는 방법
      예1) 프레임: 120 이고 프로세스: 3개 (P1, P2, P3)
           P1: 40개, P2: 40개, P3: 40개
      예2) 프레임: 120 이고 프로세스: 4개 (P1, P2, P3, P4)
           P1: 30개, P2: 30개, P3: 30개, P4: 30개
    * 문제점: 각 프로세스마다 메모리 요구량이 다르기 때문에 프로세스에 따라서 프레임 낭비 또는 빈번한 페이지 부재가 발생한다.
      예) 알씨: 약 90 Mb / 카카오톡: 약 50 Mb / MS-Word: 약 500 Mb
          카카오톡은 메모리 낭비가 있고 MS-Word에서는 페이지 부재 빈도가 증가한다.

  (1-2) 비례 할당(Proportional allocation)
    * 균등 할당의 문제를 해결하기 위해 프로세스의 크기에 비례하여 메모리 프레임을 할당한다.
     예) 가용 프레임: 120개
        프로세스 크기: 알씨: 약 90 Mb / 카카오톡: 약 50 Mb / MS-World: 약 500 Mb
          알씨 => 120 * 90 / (90 + 50 + 500) = 17개
         카카오톡 => 120 * 50 / (90 + 50 + 500) = 9개
         MS-Word => 120 * 500 / (90 + 50 + 500) = 94개
    * 문제점 : 요구 페이징에서 처럼 프로세스의 모든 페이지가 다 메모리에 적재될 필요는 없다. 즉, 카카오톡 프로세스는 작은 프로그램이기 때문에 모든 페이지가 다 적재될 필요가 있을 수 있지만 MS-Word는 해당 프로세스의 많은 부분이 지금 당장 필요하지 않은 페이지들이다. 즉, 동적인 요구를 반영하고 있지 못하다.

16 프레임 할당1

1) 쓰레싱(Thrashing)이란?
  * CPU utilization (CPU 이용율)
    : CPU가 쉬지 않고 얼마나 잘 활용되었는가!
  * degree of multiprogramming(number of processes)
    : 멀티 프로그래밍의 정도. 즉,수행중인 프로세스의 수
  * 쓰레싱(hrashing)
    : 프로세스가 1개이거나 수가 적으면 I/O 처리가 있을 때마다 CPU는 대기 상태가되어 이용률이 낮아진다. 그러나 프로세스가 많아 질 수록 CPU 대기 시간이 줄어들고 이용률이 증가하게 된다.
    : 그러나 프로세스의 수가 어느 정도 증가하고 나면 CPU 이용률이 급격하게 감소하는 현상이 발생한다. 이를 쓰레싱(Thrashing)이라고 한다.
    :쓰레싱의 원인은 프로세스가 많아 질 수록 메모리에 빈 프레임이 줄어들게 되고 따라서 페이지 교체의 빈도가 증가하게 되기 때문이다. 페이지 교체로 인한 I/O처리로 인해 CPU의 대기 시간이 증가하는 것이다. (동시에 많은 프로그램을 실행하면 컴퓨터가 늦어지는 이유중의 하나이기도 하다.)

  * 쓰레싱 현상을 최대한 감소 시켜야 시스템의 성능을 높일 수 있다.
  * 쓰레싱을 줄이는 방법은?
    (1) Local Repleacement(지역 교체)를 한다.각 프로세스에 할당된 프레임의 수가 변동이 없게 되며, 다른 프로세스에 의해 영향을 받지 않는다. 즉, 다른 프로세스의 쓰레싱에 영향을 받지 않게 된다.
    (2) 프로세스에게 적당한 수의 프레임을 할당해 준다. 페이지 교체는 결국 프레임의 부족해서 발생하는 것이기 때문이다. 단, 문제는 어느 정도가 적당한가? 이것이 문제이다.

  * 프레임 할당이란?
   : 메모리를 프로세스에게 어떻게 분배할 것인가? 즉, 프레임을 어떻게 할당할 것인가?
   : 프레임은 프로세스의 페이지 크기와 같은 크기로 메인 메모리를 나눈 단위이다.
   : 프로세스에게 너무 적은 프레임이 할당되면 페이지 부재가 빈번하게 발생한다.
   : 프로세스에게 과한 프레임이 할당되면 페이지 부재는 적지만 메모리 낭비를 초래한다.

  * 프레임 할당 알고리즘
   (1) 정적 할당(static allocation)
      1-1) 균등 할당(Equal allocation)
      1-2) 비례 할당(Proportional allocation)
   (2) 동적 할당(dynamic allocation)
      2-1) 작업 집합 모델(Working set model)
       2-2) 페이지 부재 빈도(Page fault frequency)

15 가상 메모리4

4) 페이지 교체 알고리즘

  * 예시)
   : 페이지 참조열 = 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1
   : 프레임의 수 = 3

4-1) First-In-First-Out (FIFO) Algorithm
  * 메인 메모리에 제일 먼저 올라온 페이지를 Victim(희생양)으로 결정
  * 초기화 코드는 재사용되지 않을 것이라는 전제

  * Page Fault (페이지 부재) : 15회 발생
  * 이상 현상: Belady's Anomaly
      할당되는 프레임의 수가 증가해도 페이지 부재율이 증가하는 현상.

4-2) Optimal Algorithm
  * 앞으로 제일 사용이 늦게될 페이지를 Victim(희생양)으로 결정
  * 앞으로 한참동안 사용이 되지 않는 페이지는 제일 불필요할 것이다.

  * Page Fault (페이지 부재) : 9회 발생
  * 문제점: 미래에 어떤 페이지가 사용될 지 알 수 없다.


4-3) Least Recently Used (LRU) Algorithm
  * 가장 최근에 사용되지 않았던 페이지를 Victim(희생양)으로 결정
  * 통계적으로 최근에 사용되지 않았던 페이지는 앞으로도 사용되지 않을 가능성이 높다.

  * Page Fault (페이지 부재) : 12회 발생

5) 페이지 교체 알고리즘의 비교

6) Global vs Local Replacement
  * Global Replacement
    : 페이지 교체의 대상이 메인 메모리에 있는 모든 페이지를 대상으로 한다.
    : 다른 프로세스의 영향을 받게 되게 된다. 프로세스의 실행이 늦어지거나 빨라질 수 있다.
    : 개별 프로세스의 동작 보다는 시스템 전반의 효율에 중점을 두기 때문에 대형 시스템에서 이용된다.

  * Local Replacement
    : 페이지 교체의 대상이 동일 프로세스의 페이지만 대상으로 한다.
    : 각 프로세스에 할당된 프레임의 수는 변하지 않으며, 프로세스의 상대적인 중요도에 따라 메모리 할당을 조정, 성능개선을 할 수 있다.

15 가상 메모리3

3) 페이지 교체(Page Replacement)
  * 페이지 부재 발생: 요구되는 페이지를 backing store에서 가져다가 메모리의 빈프레임에 적재한다.
  * 이것이 반복되면 언젠가는 메인 메모리가 가득차게된다(memory full).

  * memory full 이면 페이지 교체가 발생한다.
    : 요구되는 페이지를 메모리에 적재하기 위해서
      (1) 현재 메모리에 적재되어져 있는 특정 페이지를 backing store로 몰아낸다.
         (page-out)
      (2) 그 빈공간에 요구되는 페이지를 적재한다.(page-in)
   * Victim Page (희생 페이지)
     : 요구 페이지를 가져오기 위해 현재 메모리에 적재되어져 있지만 몰아내야 되는 페이지.
      : 수정(modified)되지 않은 페이지를 희생양으로 삼으면 I/O시간을 절약할 수 있기 때문에 처리 속도가 상대적으로 빨라지게 된다.(modified bit 를 두어서 구분)

  * 페이지 교체 알고리즘
    : 어떤 페이지를 Victim(희생양)으로 삼을 것인가에 대한 문제
      이에 따라서 이후 페이지 부재의 발생 빈도가 결정되고 처리 속도가 달라지게 된다.

  * 페이지 참조열(Page Reference String)
   : CPU 참조할 메모리 주소가: 100 101 102 432 612 103 104 611 612
   : Page Size = 100 Byte 라면
   : Page Number = 1 1 1 4 6 1 1 6 6
   : Page Reference String = 1 4 6 1 6

15 가상 메모리2

2-1) 페이지 부재(Page Fault)
  * 페이지 부재가 발생하면 해당 페이지를 HDD (혹은 Backing Store)에서 찾아서 메모리에 적재해야 한다.
  (1) 페이지 테이블 참조했을 때 페이지 부재가 발생하면
  (2) 인터럽트(trap)이 걸려서 O/S로 전달
  (3) O/S가 HDD에서 해당 페이지 찾음
  (4) O/S가 해당 페이지를 메모리의 빈 프레임에 적재함
  (5) 페이지 테이블 갱신 (Frame Number 추가, i => v)
  (6) 페이지 테이블 재참조

  * 요구 페이징은 메모리를 절약하는 장점이 있지만 페이지 폴트가 발생 함으로써 프로세스 처리 시간이 늦어지게 된다.
    HDD에서 페이지를 읽어오는 시간이 오래 걸리게 된다.


2-2) 유효 접근 시간(Effective Access Time)
  * 프로세스 전체 집합(모든 페이지)가 메모리에 적재되어져 있지 않고 일부만 적재되어져 있기 때문에 페이지 폴트가 일어날 때와 일어나지 않을 때가 있다.
  * 페이지 폴트의 빈도에 따라 메모리에 접근하는 접근 시간이 달라지게 된다.
  * 이는 페이지 폴트의 발생 확률과 밀접한 관련이 있으며 그 시간을 유료 접근 시간이라고 한다.
    Teff (유요 접근 시간) = (1-P)Tm + PTp
    P : 페이지 폴트 발생률(page fault rate)
    Tm : 메모리를 읽는데 걸린 시간
    Tp : 페이지 폴트가 발생하여 이를 처리하는데 걸리는 시간

    예제)
    Tm = 200 nsec
    Tp = 8 msec = 8,000,000 nsec
    Teff = (1 - P)200 + P8,000,000 = 200 + 7,999,800P
    만약 P = 1/1,000 이면 Teff = 8.2 usec (Tm에 비해 약40배 느려짐)
    만약 P = 1/399,990 이면 Teff = 220 nsec (Tm에 비해 약10% 느려짐)

  * 페이지 폴트가 너무 자주 일어나면 처리 속도가 느려지기 때문
   : (1) 페이지 폴트를 최소화 하도록 한다.
   : (2) backing store로 플래시 메모리(SSD)와 같은 속도가 빠른 보조기억 장치를 이용한다.

  * 지역성(Locality)
   : 시간적 지역성
      한 번 읽으면 곧 또 읽을 확률이 많다. 반복문과 같은 코드가 많이 있기 때문이다.
     한번 페이지 부재가 생겨서 가져 오면 그 시간 이후에는 자주 일어나지 않게 된다.

   : 공간적 지역성
     예를들어 지금 1,000번지를 읽고 있으면 1,000번지 부근을 또 읽을 확률이 높다.
     즉, 보통 그 인접한 구역을 읽게 된다.
     유사한 코드가 함께 근처에 블록단위로 있기 때문이다.
     한 번 페이지 부재가 생겨서 읽어 오면 그 영역을 계속 읽기 때문에 페이지 부재가 다시 일어나지 않게 된다.

15 가상 메모리1

0) 가상 메모리란?
  * 출현 계기
    : 물리 메모리(Physical Memory)의 크기에 따른 한계를 극복하기 위한 기술
      즉, 물리 메모리(Physical Memory)보다 큰 프로세스 실행이 가능하다.
      예) 100MB 메인 메모리에서 200MB 크기의 프로세스 실행가능
          원래는 100MB인 메인 메모리보다 큰 프로세스는 실행이 불가.
  * 적용 방법
    : 현재 실행에 필요한 부분만 메모리에 올린다!
     즉, 프로세스 이미지를 모두 메모리에 올릴 필요는 없다.
     오류 처리, 배열의 일부, 워드프로세스에서 정렬, 표 기능 등은 제외가능하다.
      동적 적재 (dynamic loading)와 비슷한 개념이다.

1) 요구 페이징(Demand Paging)

  * 대체로 "가상 메모리 = 요구 페이징"을 의미함.
  * 프로세스를 페이지 단위로 나누고 CPU가 처리하는데 필요한 페이지만 즉, 요구되는 페이지만 메모리에 적재하는 것이어서 "요구 페이징(demand paging)"이라고 한다.
  * 프로세스는 페이지의 집합이다.
  * 메모리에 적재되지 못한 프로세스의 나머지 페이지들은 backing store에 저장되어져 있다.

  * 위 그림의 경우 10 Mb 메인 메모리에 각각 5 Mb, 7 Mb, 4 Mb인 프로세스 3개를 모두 적재하였다. 단, 각 프로세스에서 필요한 페이지(3개, 4개, 1개)만 적재되어져 있다.

  * 페이지 부재(Page Fault)
    : CPU가 필요로 하는 Page가 메인 메모리에 적재되어져 있지 않은 경우를 의미한다.
    : 페이지 부재(Page Fault)가 발생하면 해당 페이지를 메모리에 적재해주어야 한다.

  * 순수 요구 페이징(Pure Demand Paging)
    : 순수하게 현재 시점에 필요한 페이지만 적재한다.
    : 장점 - 메모리 절약을 최대화 할 수 있다.
    : 단점 - 시작하자 마자 페이지 부재가 일어난다. 속도가 느려진다.

  * 프리페이징(Prepaging)
    : 당연히 사용될 페이지라고 예측되어지는 페이지는 미리 적재한다.
    : 장점 - 미리 적재되어져 있기 때문에 속도가 빠르다.
    : 단점 - 페이지 부재가 적다. 만약 사용되지 않으면 메모리 낭비가 된다.

  * Swapping vs Demand Paging
    : Swapping - 프로세스 단위로 이동
    : Demand Paging - 페이지 단위로 이동

14. 메모리 관리3

3) 세그멘테이션(Segmentation)
  * 프로세스를 논리적 내용(=세그멘트)으로 잘라서 메모리에 배치
    : 프로세스는 세그멘트(segment)의 집합
  * 동일한 크기를 갖는 페이징과는 달리 메모리를 프로그램을 구성하는 메인루틴, 서브루틴(Sub-Routine), 프로시저(Procedure), 함수(Function) 또는 모듈(Module), 전역 변수, 스택(Stack) 등의 각각 다른 크기를 갖는 세그먼트로 나눔.
    : 각 세그먼트는 연관된 기능을 수행하는 하나의 모듈 프로그램임으로 논리적 구조화가 쉬움.
    : 각 세그먼트가 페이징처럼 메모리에서 서로 인접할 필요는 없음.

 * 논리 주소 vs 물리 주소

  * 메모리 보호(Protection)
    : 모든 주소는 세그먼트 테이블을 경유하도록 한다.
    : 세그먼트 테이블 엔트리(각 열)마다 r(읽기), w(쓰기), x(시행) 비트를 둔다.
    : 논리적 단위로구분되어 있어서 페이징 보다 훨씬 수월하다.

  * 메모리 공유(Memory Sharing)
    : 같은 프로그램을 쓰는 여러 종류의 프로세스들은 Code를 공유할 수 있다.
      (단, pure code = reentrant code = non-selfmodifying code)
     즉, 프로세스의 세그먼트 테이블 코드 영역이 같은 곳을 가리키도록 한다.
    : 논리적 단위로구분되어 있어서 페이징 보다 훨씬 수월하다. 

  * 문제점
    : 연속 메모리 할당과 같은 메모리 할당 기법을 고려해야한다.
     이로 인해 외부 단편화 문제가 존재한다.
    : 따라서 세그멘테이션 보다는 페이징 기법이 더 일반화되어 사용된다.


4) 페이지드 세그멘테이션(Paged Segmentation)
 * 프로세스를 나눌 때 세그먼트 단위로 나눈다.
   그리고 각 세그먼트를 페이지 단위로 다시 일정하게 나눈다.
 * 장점은 보호와 공유가 용이하고 외부 단편화를 없앨 수 있다.
 * 단점은 세그먼트 테이블과 페이지 테이블이 필요하게 됨으로 주소 변환과정이 더 복잡해지고 시간이 오래 걸리게 된다.

14. 메모리 관리2

2) 페이징(Paging)

 * 프로세스를 일정한 크기로 잘라서 메모리에 할당한다.
   : 프로세스의 일정한 크기 => 페이지(page)
   : 메모리의 일정한 크기공간 => 프레임(frame)
 * 물리 메모리내에 하나의 프로세스가 연속된 메모리를 할당받을 필요 없이 여러 개의 페이지 조각으로 나누어져서 분산 할당된다.
 * 프로세스와 메모리가 동일한 크기로 규격화 됨으로써 외부 단편화가 발생하지 않는다.
 * 내부 단편화(Internal Fragmention)가 발생하지만 심각한 수준은 아니다.
   내부 단편화
    - 메모리 10 kb 프레임에 3 kb 페이지(23 kb 프로세스 였다면 3 kb 짜투리가 남음)가 할당되면 해당 메모리는 7 kb의 내부 단편화가 발생한다.

 * 논리 메모리 vs 물리 메모리 변환

< 논리 주소 50은 물리 주소로 몇 번지인가? >

   * 페이지 테이블의 크기는 프로세스 크기(160 kb) / 페이지 크기 (16 kb) = 10개
   * CPU는 50번지를 요청했지만, 실제 데이타는 98번지에 위치해 있게 된다.
     즉, CPU는 실제 메모리 주소는 고려하지 않고 자신이 원하는 주소를 제공하면 MMU (여기서는 Page Table)를 거치면서 자동 변환되어 처리된다.
   * CPU는 프로세스가 메모리에 연속된 주소에 있는 것으로 처리되기 때문에 문제 없이 처리되도록 하고, 실제 메모리는 페이지 단위로 할당해서 외부 단편화 문제를 해결하게 된다.

   * 메모리 보호(Protection)
    : 모든 주소는 페이지 테이블을 경유하도록 한다.
    : 페이지 테이블 엔트리(각 열)마다 r(읽기), w(쓰기), x(시행) 비트를 둔다.
   * 메모리 공유(Memory Sharing)
    : 같은 프로그램을 쓰는 여러 종류의 프로세스들은 Code를 공유할 수 있다.
      (단, pure code = reentrant code = non-selfmodifying code)
     즉, 프로세스의 페이지 테이블 코드 영역이 같은 곳을 가리키도록 한다.

   * 장점
    : 공유 페이지의 이용 가능
    : 외부 단편화가 발생하지 않으며, 압축이 불필요.
    : 메모리 활용을 통한 다중 처리 프로그래밍 실현.

   * 단점
    : 내부 단편화 발생 (but 외부 단편화에 비해 무시가능한 수준임)
    : 페이징 사상을 위한 하드웨어로 가격 상승과 속도 저하
    : 같은 크기의 메모리 프레임에 추가해야하기 때문에 Code와 Data의 경계가 특정 프레임에 함께 들어가는 문제가 있다.

14. 메모리 관리1

1) 연속메모리 할당(Contiguous Memory Allocation)

  * 하나의 프로세스는 연속된 메모리 공간에 할당을 받게 된다.

  * 부팅직후에는 메모리홀이 매우 크지만 시간이 지날 수록 프로세스의 생성과 소멸이 반복되면서 불연속적으로 단편화된 작은 홀들이 흩어 지게 된다.

   위 그림의 마지막에서 3칸을 차지하는 Process는 메모리에 진입할 수 없게 된다.

  * 외부 단편화(External Fragmentation)

    : 빈 메모리 공간이 있지만 이 공간이 여러개의 불연속적인 작은 공간으로 나뉘어져 있어서 프로세스를 할당할 수 없는 상태일 때 이 조각난 공간들에 대한 현상을 외부 단편화라고 한다. 외부 단편화는 심한 메모리 낭비의 원인이 된다.

 * 메모리 할당 방식

  : 메모리를 프로세스에게 어떻게 할당하는 것이 바람직한가?에 대한 문제.

  (1) First-fit (최초 적합)

     : 최초로 할당받을 수 있는 크기의 공간에 무조건 할당된다.(위 또는 아래 부터)

  (2) Best-fit (최적 적합)

     : 크기가 가장 근접한 공간에 할당된다.

  (3) Worst-fit (최악 적합)

      : 크기가 가장 많이 차이가 나는 공간에 할당된다.

  * 속도면에서는 "best-fit"이 최고이다.

  * 이용률 면에서는 "first-fit"과 "best-fit"이 좋은 편이고 "worst-fit"은 좋지 못함. 

  * 어떤 경우이든 외부 단편화는 존재하기 마련이다.

 * 압축(Compaction)

  : 외부 단편화의 해결방안으로 흩어져 있는 홀들을 하나의 커다란 홀로 통합하여 사용한다.

  : 문제는 어떤 방식으로 압축을 할 것인가가 큰 문제가 된다. 상대적으로 커다란 프로세스를 이동하여 압축을 하게 된다면 압축을 위한 비용이 많이 들어 비효율적이게 된다.

13. 주기억 장치의 이해2

2) 효율적인 메모리 사용을 위한 기법

 (1) 동적 적재(Dynamic Loading)
    : 프로그램이 실행될 때 프로그램의 모든 것이 다 한 번에 메모리에 적재(정적 적재, static loading)되는 것이 아니라 프로그램이 실행되는데 필요한 부분만 필요에 따라서 적재하는 방법이다. 사용되지 않거나 사용될 가능성이 낮은 내용은 애초에 메모리에 적재하지 않음으로써 메모리를 절약한다.
    : 모든 루틴(routine)이 다 사용되는 것은 아니다.
      예) 오류처리 - 예외가 발생했을 때만 필요하다.
    : 모든 데이터(data)가 다 사용되는 것은 아니다.
      예) 배열 - 배열의 어떤 일부는 필요할 때만 접근 하면 된다.
    : 모든 클래스가 다 사용되는 것은 아니다.
     예) 자바 - 특정 클래스는 필요할 때만 호출하면 된다.
        파워포인트 - 파워포인트를 실행했을 때 디자인 템플릿을 미리 메모리에 올려놓을 필요는 없다. 사용자가 디자인 템플릿 사용을 요청했을 때 메모리에 올리면 된다.

 (2) 동적 연결(Dynamic Linking)
    : 여러 개의 프로그램이 실행될 때 다수의 프로그램이 공통으로 사용하는 라이브러리를 사용하는 프로그램의 수 만큼 메모리에 적재하는 것이 아니라 한 번만 적재하고 각 프로그램이 공동으로 해당 라이브러리를 사용할 수 있도록 함으로써 메모리를 절약할 수 있게 된다.
    : printf() 함수와 관련된 라이브러리는 대부분의 프로그램이 사용줄이다. 다라서 처음 프로그램이 실행될 때 로드된 printf()함수와 관련된 라이브러리를 적재하고 이후의 프로그램들은 처음 적재된 printf()함수의 라이브러리를 공유해서 사용한다.
    : 동영상 실행과 음악 실행은 소리를 재생하는 라이브러리를 공유하도록 한다.
    : Email과 FTP 프로그램은 네트웍 라이브러리를 공유하도록 한다.
    : dll(Dynanic Linking Library) - link를 exe 파일을 만들 때 하지 않고 메모리에 적재할 때 link를 한다.

 (3) 스와핑(Swapping)
    : 메모리에 적재되어져 있으나 현재 사용되지 않는 프로세스에 대해 HDD로 추출(swap-out)하거나 추출되었던 프로세스가 재사용됨에 따라 다시 메모리로 적재(swap-in)하는 것.
     메모리 공간만 차지하고 사용되지 않는 프로세스를 추출함으로써 메모리를 절약할 수 있다.

   : 프로세스가 매우 클경우 스와핑(out / in)에 대한 부담이 커지게 된다.
   : backing store는 일반적으로 HDD의 일부 영역을 활용하지만 서버와 같은 특수한 환경에서는 별도의 전용 backing store를 사용하기도 한다.

13. 주기억 장치의 이해1

1) 실행파일, 메모리의 구조와 원리
  (1) 실행파일의 생성

  (2) 메모리에 프로그램 적재

  (3) 메모리 구조(Memory Structure)

    * 주소버스
      : CPU가 접근하고자 하는 메모리의 주소(논리 주소)를 전달하는 통로

    * 데이타 버스
     : CPU가 메모리의 프로세스 명령이나 데이타를 전달 받거나 CPU의 처리 결과를 메모리에 전달하여 그 내용을 업데이트하도록 하는 데이타 전송 통로

  (4) 논리 주소(Logical address)와 물리 주소(Physical address)

   * 논리 주소(Logical Address)
     : 하나의 프로그램이 만들어 질 때 메모리의 어떤 주소에 위치하게 될지 알 수 없다. 또한 CPU는 프로그램들이 연속된 메모리의 프로세스로 적재된다고 전제하고 있다. 따라서 CPU가 메모리를 접근하기 위해 임의의 연속된 메모리를 할당해 주게 되는데 이 주소를 논리 주소라고한다.

   * 물리 주소(Physical Address)
     : CPU가 논리 주소를 이용해 메모리에 접근하려 하면, CPU가 제공한 논리 주소와 매핑된 실제 메모리의 주소를 물리 주소라고 한다.

   * 재배치 레지스터(Relocation register)
     : 논리주소를 물리 주소로 변환시켜 주는 메모리 관리 장치(MMU)내의 레지스터

12. 교착상태(Deadlock)4

2-3) 교착상태 탐지 및 복구(Deadlock Detection & Recovery)
   * 교착상태 탐지(Detection)
     : 교착상태가 발생했는지 파악하기위해 시스템을 주기적으로 검사하는 알고리즘
     : 사전에 교착상태의 발생에 대해 염려하지 않고 탐지만 하고 있다가 교착상태가 탐지되면 이를 복구하도록 한다.
     : 얼마나 자주 탐지를 위한 검사를 해야할 것인가가 문제. 자주할 수록 탐지는 수월할 수 있지만 자원 이용률이 크게 감소된다.

   * 교착상태 복구(Recovery)
     a. 프로세스 중지 방법
       - 교착상태 프로세스를 모두 중지.
        교착상태의 순환대기를 확실히 해결하지만 자원 사용과 시간 면에서 비용이 많이 듬. 즉, 오랫동안 연산했을 가능성이 있는 프로세스의 부분 결과를 폐기하여 나중에 다시 연산해야 함.
       - 한 프로세스씩 중지.
         한 프로세스가 중지될 때마다 교착상태 탐지 알고리즘을 호출하여 프로세스가 교착상태에 있는지 확인. 이는 교착상태 탐지 알고리즘 호출에 대한 부담이 큼.

     b. 자원 선점 방법
       - 프로세스의 자원을 선점하여 교착상태가 해결될 때까지 선점한 자원을 다른 프로세스에 할당하여 이용.


2-4) 교착상태 무시
   * 교착상태는 일반적으로 자주 발생되는 현상은 아니다.
      따라서 이를 해결하기 위한 노력의 비용이 너무 과하며 시스템 효율도 떨어진다.
   * 일반 PC의 경우 교착상태를 고려하기 보다는 무시하는 것이 효용가치가 높다.
   * 교착상태가 발생해서는 안될경우 무시해서는 안된다.
     예) 우주 탐사 시스템, 미사일 로켓 시스템 등등

3) 기아상태(Starvation)
  * 교착상태의 예방을 위해 자원을 할당하다 보면 기아상태가 발생할 수 있음.
  * 식사하는 철학자 문제
   항상 2명만이 식사를 할 수 있음. 동시에 5명이 식사를 하려 하면 교착상태에 빠지게 됨.
   따라서 어떤 철학자가 기아상태가 될 가능성을 항상 내포하고 있음.
  * 기아상태인 프로세스가 없도록 계속 추적 관리해야 함.
   

12. 교착상태(Deadlock)3

2-2) 교착상태 회피(Deadlock Avoidance)
    * 프로세스들은 여러 자원을 필요로 한다. 프로세스가 자원을 사용 하기 위해서는 O/S에게 요청을 해야하고 O/S는 이를 승인하고 할당해 주어어야 하며 회수도 해야 한다. 따라서 교착상태란 O/S가 자원의 할당을 잘 못 했기 때문에 발생한다고 전제한다.
    * 교착상태 회피(avoidance) 기법은
      :  교착상태 방지(Prevention)에 비해 소극적이며 시스템의 효율을 높이는데 목적을 두고 있다.
      : 현재 가용자원을 프로세스 요청시 바로 할당해 줄 것인지(안정 상태), 기다리게 할 것인지(불안전 상태)를 결정하는 문제와 같다.
       - 안전 상태(safe state): 시스템이 교착상태를 일으키지 않으면서 각 프로세스가 요구한 최대 요구량만큼 필요한 자원을 할당해 줄 수 있는 상태이다.
       - 불안전 상태(unsafe state): 안정 상태와 달리 프로세스의 자원 할당 및 해제의 순서가 불명확하여 교착상태의 발생가능성이 있다

   * Banker's Algorithm(은행가 알고리즘)
     : 교착상태 회피 알고리즘
     : 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게
되는 지를 사전에 검사하여 교착상태의 발생을 회피하는 기법
      (마치 은행이 대출을 시행한 후에 파산하지 않고 정상 유지되지는를 검사하여 안전하다고 판단될 때만 대출을 시행하는 것과 같은 개념)
     : 각 프로세스가 실행되기 전에 필요로 하는 모든 자원 형태들의 최대수를 알아야 함.
     : 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지 검사.
     : 안정 상태에 있으면 자원을 할당, 그렇지 않으면 다른 프로세스들이 자원을 해제할 때까지 대기.

   * Banker's Algorithm(은행가 알고리즘)의 문제점
      : 할당할 수 있는 자원의 일정량을 상시 필요로 한다.
     : 사용자가 최대 필요량을 미리 알려주도록 요구하지만 자원 할당 방법이 점점 동적으로 변함에 따라 사용자의 최대 필요량을 파악하기 어려워 짐.
     : 교착상태 회피 알고리즘을 실행하면 시스템 과부하가 증가함.
     : 항상 불안정상태를 방지해야 함으로 자원 이용률이 낮아짐.

12. 교착상태(Deadlock)2

* 교착상태에 대한 대응 방안
  : 교착상태 방지(예방) (Deadlock Prevention)
  : 교착상태 회피 (Deadlock Avoidance)
  : 교착상태 탐지 및 복구 (Deadlock Detection & Recovery)
  : 교착상태 무시 (Don't Care)
 
2-1) 교착상태 방지기법(Deadlock Prevention)
 * 교착상태의 원인이 되는 4 가지 필요조건들 중 한 가지 이상이 발생되지 않도록 한다..
    (상호배타 / 점유와 대기 / 비선점 / 환형 대기)

 (1) 상호배타(Mutual exclusion) 방지
     : 자원을 공유 가능하게 하면 된다.
     : 문제 점 - 그러나 원천적으로 사용중인 자원을 공유하는 것은 불가능 하다.
                CPU, Memory, Print 등은 동시 공유가 불가능하다.

 (2) 점유와 대기(Hold & Wait) 방지
     : 어느 자원을 점유한 상태에서 다른 자원을 기다리지 않도록 한다. 즉, 점유하고 있는 자원이 없을 때만 요청한다.
      : 요청한 자원을 다른 프로세스가 점유하고 있다면 자신이 점유한 자원을 놓아 주도록 한다.
     : 필요한 자원을 동시에 요청하도록 한다(어느 하나만 점유 불가능).
     : 문제점 - 자원 활용률 저하, 특정 프로세스의 기아(starvation) 발생 가능성

 (3) 비선점 (No preemption) 방지
     : 자원을 선점 가능하게
     : 문제점 - 가능한 경우도 있지만 대체로 불가능 하다.
                CPU는 선점할 수 있어도 그 이외의 자원은 불가능 하다. 프린터를 사용중인데 강제로 빼앗아서 다른 인쇄물을 출력 할수는 없다.

 (4) 순환대기 (Circular wait) 방지
     : 자원에 번호를 부여하고 프로세스는 번호의 오름차순으로 자원을 요청하도록 한다.

< 식사하는 철학자: 순환대기 방지 > 

                         P0: R0 요청 후 R1 요청

                              P1: R1 요청 후 R2 요청

                         P2: R2 요청 후 R3 요청

                         P3: R3 요청 후 R4 요청

                         P4: R0 요청 후 R4 요청 <= 때문에 순환이 깨어짐

     : 문제점 - 자원 활용률 저하

12. 교착상태(Deadlock)1

1) 교착상태의 발생조건

 * 교착상태(Deadlock)이란?
   : 프로세스들이 자원의 사용을 위해 대안 없이 무한정 기다리게 되는 상태

 * 교착상태의 발생 현상
   : 프로세스의 자원 사용 절차
     O/S에 요청(Request) => 점유, 사용(Use) => O/S에 반납(Release)
   : 어떤 프로세스가 특정 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 다른 자원을 사용하기 위해 무한정 기다리게 됨으로써 교착상태가 발생하게 된다.

 * 교착상태의 발생 조건(필요조건,Necessary Conditions)
   : 항상 발생하는 것은 아니며 아래 4조건이 만족할 경우 발생할 수도 있게 된다.
  (1) 상호 배타(Mutual exclusion)
  (2) 점유와 대기(Hold and Wait)
  (3) 비선점 (No Preemptive)
  (4) 순환대기(Circular wait)

  예제) 식사하는 철학자 문제
  -- 상호배타 : 포크는 공유될 수 없다.
  -- 점유와 대기 : 모든 철학자들이 왼쪽의 포크를 쥐고 우측의 포크를 기다린다.
  -- 비선점 : 다른 철학자가 잡고 있는 포크를 강제로 빼앗을 수 없다.
  -- 순환대기 : 점유와 대기가 반시계 방향으로 순환되고 있다.

  * 자원할 당도(Resource Allocation Graph)
   : 어떤 자원이 어떤 프로세스에게 할당되어져 있는가?
   : 어떤 프로세스가 어떤 자원을 할당 받으려고 기다리고있는가?
   : 자원할당도를 통해 교착상태가 일어날지 아닐지를 알 수 있다.

< 식사하는 철학자 문제: 자원할당 그래프 => 교착상태 >
모든 철학자들이 왼쪽 포크를 할당 받고(점유하고) 오른쪽 포크를 기다리고 있음(요청중).