운영체제 정리하기

1. 운영체제

목적

• 컴퓨터 시스템을 편리하게 사용할 수 있는 환경 제공한다.

  ex) 네트워킹, 사용자관리 ..

• 컴퓨터 시스템의 자원을 효율적으로 관리한다.

  ex) 프로세스 관리, 저장장치 관리 ..

• Q. 운영체제가 왜 필요할까요?

• Q. CPU 가상화(Virtualizing the CPU), 메모리 가상화(Virtualizing Memory)에 대해서 설명할 수 있나요?

  • 운영체제는 하나의 프로세스를 실행한 후, 얼마 후 중단시키고 다른 프로세스를 실행하는 작업을 반복하면서 여러 개의 가상 CPU가 존재하는 것처럼 보이게 한다. (이를 시분할 기법이라고도 함)
  • 각 프로세스는 자신만의 가상 주소 공간(virtual address space)을 갖는다. 운영체제는 이 가상 주소 공간을 컴퓨터와 물리 메모리로 매핑(mapping)한다. 실행 중인 프로그램의 입장에서는 자기 자신만의 물리 메모리를 갖는다고 생각하지만, 실제로 물리 메모리는 공유 자원이고. 운영체제에 의해 관리된다.

2. 프로세스와 스레드

개념

• 프로세스 : 실행 중인 프로그램을 의미한다.
• 프로세스는 운영체제로부터 독립된 주소 공간을 할당받는다.
• 독립된 주소공간은 다음의 영역으로 나뉜다.
  • Code 영역: 코드 자체를 구성하는 메모리 영역
  • Data 영역: 전역변수, 정적변수
  • Heap 영역: 동적할당 시 사용되는 영역
  • Stack 영역: 지역변수, 매개변수, 리턴 값
• 스레드: 프로세스 내에서 실행되는 흐름의 단위를 말한다.
• 특징
  • 하나의 프로세스는 여러 개의 스레드를 가질 수 있으며, 각 스레드는 동시에 실행될 수 있다.
  • 스레드는 각각 별도의 스택(Stack)메모리 영역을 가지지만, 코드, 데이터, 힙 영역 은 프로세스 내 모든 스레드가 공유한다.
• Q. 프로세스와 스레드의 차이점이 무엇인가요?
• Q. 프로세스의 독립적 공간을 여러 영역으로 나눔으로써 얻는 이점은 무엇인가요?
• Q. 프로그램이 어떻게 프로세스로 변형되는지 설명해보세요.
  1. 운영체제는 프로그램의 코드(code)와 정적 데이터(static data)를 메모리, 프로세스의 주소 공간에 탑재한다.
     • 초기 운영체제는 프로그램 실행 전 모두 메모리에 탑재하였지만, 최근 운영체제는 이 작업을 늦추고 필요한 부분만 메모리에 탑재한다(paging과 swapping)
  2. 운영체제는 일정량의 메모리를 프로그램의 실행시간 스택(runtime stack)용도로 할당시킨다. 운영체제는 스택을 주어진 인자로 초기화한다. (argc, argv 벡터를 사용한다)
  3. 운영체제는 힙(heap)을 위한 메모리 영역을 할당한다.
  4. 운영체제는 입출력과 관계된 초기화 작업을 시작한다. Unix 시스템에서는 표준입력(STDIN), 표준출력(STDOUT), 표준 에러(STDERR) 장치에 해당하는 세개의 파일 디스크립터를 갖는다.
  5. 운영체제는 프로그램의 시작 지점(entry point), main에서부터 프로그램을 시작한다.

상태

• 프로세스는 크게 3가지 상태가 있다.
  1. 실행(Running): 프로세스는 프로세서에서 실행중이다. 명령어를 실행하고 있다.
  2. 준비(Ready): 프로세스는 실행할 준비가 되어 있지만 운영체제가 다른 프로세스를 실행하고 있는 등의 이유로 대기 중이다.
  3. 대기(Blocked): 프로세스가 다른 사건을 기다리는 동안 프로세스의 수행을 중단시키는 연산이다. ex) 입출력 요청 시 입출력이 완료될 때까지 대기(blocked)상태가 된다.

자료구조

• 운영체제는 각 프로세스를 관리하기 위해 프로세스당 유지하는 정보(Process Control Block, PCB)를 둔다.
• 이는 OS 메모리 영역 중 Data부분에 저장된다.
• PCB가 관리하는 정보
  1. OS가 관리상 사용하는 정보
     • Process state(프로세스 상태), Process ID(프로세스 이름), scheduling information(스케줄링 정보)
  2. CPU 수행 관련 하드웨어 값
     • Program counter(현재 실행 중인 명령어의 주소를 가리키는 레지스터)
     • registers(CPU 내부에 위치한 작은 메모리 공간)
  3. 메모리 관련
     • code, data, stack의 위치 정보(stack pointer - 스택 최상단 가리키는 포인터)
  4. 파일 관련
     • open filde descriptors…
• Q. PCB가 왜 필요하고, 운영체제는 이를 어떻게 관리할까요?
• Q. 컨텍스트 스위치에 대해 설명해보세요.

3. CPU 스케줄링

스케줄링 평가 항목(scheduling metric)

• 반환 시간(turnaround time)
• 공정성(fairness)
• 응답시간(response time)

1. 선입선출 (First In First Out, FIFO)

• 먼저 들어온 것을 먼저 처리한다.
• 단순하고 구현하기 쉽지만, convoy effect가 발생할 수 있다.
  • convoy effect: 짧은 시간 동안 자원을 사용할 프로세스들이 자원을 오랫동안 사용하는 프로세스의 종료를 기다리는 현상을 말한다.

2. 최단 작업 우선(Shortest Job First, SJF)

• 가장 짧은 실행 시간을 작업을 먼저 실행시킨다.
• 모든 작업이 동시에 도착한다면 SJF가 최적(optimal)을 보장한다.
• 오래 걸리는 작업이 큐에 먼저 도착한 경우 이전의 convoy effect가 다시 발생한다.

3. 최소 잔여시간 우선(Shortest Time-to-Completion Fisrt, STCF)

• 언제든 새로운 작업이 시스템에 들어오면, 스케줄러는 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 스케줄한다.

4. 라운드 로빈(Round-Robin, RR)

• 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다.
• 시분할 컴퓨터의 등장으로 상호작용을 원할하기 위한 성능을 요구하게 되고, 응답 시간(response time)이라는 새로운 평가기준이 필요하게 되었다.
• 작업이 실행되는 일정 시간을 타임 슬라이스(time slice) 또는 스케줄링 퀀텀(scheduling quantum)이라 부른다.
• 타임 슬라이스가 짧을수록, 응답 시간 기준으로 RR의 성능은 더 좋아진다. 하지만 너무 짧게 하면, 문맥 전환 비용이 전체 성능에 큰 영향을 미치게 된다.

스케줄링의 두가지 접근법

1. 남아 있는 작업 중 실행 시간이 제일 짧은 시간을 수행하고, 반환시간을 최소화한다. (CPU-집중-작업들에 유리)
2. 모든 작업을 번갈아 실행시키고 응답 시간을 최소화한다. (대화형-작업들에 유리)

멀티 레벨 피드백 큐(MLFQ, Multi Level Feedback Queue)의 기본 작동방식

• Priority(A) > priority(B)이면 A가 실행된다.
• Priority(A) = priority(B)이면 RR방식으로 실행된다.
• 작업이 시스템에 들어가면 최상위 큐에 배치된다.
• 작업이 지정된 단계에서 배정받은 시간을 소진하면 작업의 우선순위는 감소한다.
• 일정 주기 S가 지난 후, 시스템의 모든 작업을 최상위 큐로 이동시킨다.

멀티프로세서에서 CPU스케줄링

• 캐시에 관해 먼저 살펴보자
  • CPU에는 하드웨어 캐시 계층이 존재한다. 자주 접근되는 데이터를 캐시에 임시로 가져다 둠으로써 크고 느린 메모리를 빠른 메모리처럼 보이게 한다.
  • 캐시는 지역성에 기반한다
    • 시간 지역성: 데이터가 한 번 접근되면 가까운 미래에 다시 접근되기 쉽다는 것이다.
    • 공간 지역성: 프로그램이 주소 x의 데이터에 접근하면 x 주변의 데이터가 접근되기 쉽다는 것이다

1. 캐시 일관성 문제(cache coherence)

• 멀티 프로세서 시스템에서 CPU마다 캐시를 가지고 있다면 CPU1 캐시에 존재하는 데이터가 CPU2 캐시에는 존재하지 않아서 데이터 불일치 문제가 생길 수 있다.

• 해결책

  → 여러 개의 프로세스들이 하나의 메모리에 갱신할 때에는 공유되도록 한다. 버스 기반 시스템에서는 이를 버스 스누핑(bus snooping)이라고 한다.

  → 캐시 데이터에 대한 변경이 발생하면, 자신의 복사본을 무효시키거나(자신의 캐시에서 삭제), 갱신(새로운 값을 캐시에 기록)한다.

2. 동기화 문제

- 캐시에 일관성이 보장된다고 하더라도, 프로그램 또는 운영체제는 공유데이터에 접근할 때 동기화 기법을 사용해야 한다.
- 해결책
    
    → 상호배제를 보장하는 기법인 락-프리(lock free)데이터 구조를 이용한다.

3. 캐시 친화성(cache affinity)

- 캐시 친화성이란 데이터 접근 패턴을 최적화하여 캐시 메모리를 효율적으로 활용하는 것이다. 프로세스가 실행될 때 해당 CPU 캐시와 TLB에 상당한 정보를 올려놓기 때문이다. 매번 다른 CPU에서 실행한다면 필요한 정보를 다시 탑재해야 하는 오버헤드가 발생한다.

4. 메모리 가상화

• 왜 메모리 가상화가 필요할까?

  프로그램 입장에서 어떤 명령어를 실행하기 전에 매번 자신의 메모리가 충분하게 있는지 살펴보는 건 비효율적이다. 프로그램이 자신의 전용 메모리를 소유하고 그 안에 자신의 코드와 데이터가 있다는 환상을 만들어줘야 한다.

• 하드웨어만으로 메모리 가상화를 구현할 수 있을까?

  주소 변환(가상 주소와 물리 주소 매핑)은 가능하지만, 정확한 변환을 위해선 운영체제의 지원이 필요하다. 그 이유는 운영체제만이 메모리의 빈 공간과 사용 중인 공간을 알고 있고, 메모리 사용 제어권이 있기 때문이다.

1) 정적 재배치와 동적 재배치

→ 정적 재배치

• 과거에는 로더(loader)라 불리는 소프트웨어가 실행하고자 하는 실행 파일의 모든 주소를 원하는 물리 오프셋으로 변경했다. 이 방식은 잘못된 주소를 사용하여 불법적인 메모리 접근을 할 위험성이 있었고, 주소 공간을 재배치하는 것도 어려웠다.

→ 동적 재배치

• 동적(하드웨어 기반) 재배치(dynamic relocation) 에서는 2개의 하드웨어 레지스터가 필요하다. 하나는 베이스 레지스터(base register)이고, 다른 하나는 한계 레지스터(limit register)이다.
• 프로세스에 의해 생성되는 모든 주소가 다음 방법으로 프로세서에 의해 변환된다.

physical address = virtual address + base;

• 이러한 주소 변환에 도움 주는 프로세서 일부를 메모리 관리 장치(MMU, Memory Management Unit)라고 한다.
• 이 주소의 재배치는 프로그램 실행 시에 일어나고, 프로세스가 실행을 시작한 이후에도 주소 공간을 이동할 수 있기에 동적 재배치라고 한다.
• 이 두 레지스터로 인해 간단하고 효율적인 메모리 가상화를 제공할 수 있게 되었다.

→ 운영체제의 역할

1. 프로세스가 생성될 때 운영체제는 주소 공간이 저장될 메모리 공간을 찾아야 한다. (빈 공간 리스트 자료 구조 검색)
2. 프로세스가 종료할 때 프로세스가 사용하던 메모리를 회수하고 다른 프로세스나 운영체제가 사용할 수 있게 한다.
3. 문맥 교환(context switch)가 일어날 때 추가 조치를 해야한다.
   1. 프로세스 전환 시 베이스와 리밋 쌍을 저장하고 복원한다.
   2. PCB에 값을 저장하고 실행한다.
   3. 현재 위치에서 새 위치로 주소 공간을 복사하고, 운영체제는 PCB에 저장된 베이스 레지스터를 갱신하여 새 공간을 가리키도록 한다.
4. 운영체제는 예외 핸들러 또는 호출될 함수를 제공해야 한다.

→ 동적 재배치의 문제점

1. 내부 단편화: 사용하지 않는 스택과 힙 공간이 단순히 낭비된다.
2. 고정 크기의 주소 공간: 충분한 물리 메모리가 있더라도 고정 크기에 주소 공간을 배치해야 하기에 내부 단편화 발생한다.

(즉, 이 기법에선 전체 주소 공간이 하나의 베이스-리밋 쌍을 가지므로 스택과 힙 사이의 공간이 사용되지 않더라도 물리 메모리를 차지하게 된다.)

2) 세그먼테이션(Segmentation)

• 가상 주소 공간을 여러 개의 세그먼트로 분할하는 기법이다. 논리적인 세그먼트마다 베이스와 리밋 쌍이 존재한다.
• 세그먼트 테이블을 통해 매우 많은 세그먼트를 만들 수 있다. 대표적으로 코드, 스택, 힙 영역으로 나누어 사용한다.
• 메모리를 절약하기 위해, 특정 메모리 세그먼트를 공유하는 것도 유용하다.

→ 세그먼테이션 기법의 문제점

1. 외부 단편화: 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워진다. 이는 기존 세그먼트를 정리하여 물리 메모리를 압축할 수 있겠지만, 세그먼트 복사는 메모리 부하가 굉장히 큰 연산이다.
2. 드문드문 사용되는 주소 공간(sparse address area): 크기가 매우 크지만 드문드문 사용되는 주소 공간을 지원할 만큼 유연하지가 않다. 이 힙에 접근하기 위해선 그 힙 전체가 물리 메모리에 존재하여야 한다.

3) 페이징(Paging)

• 프로세스의 주소 공간을 고정 크기의 단위로 나눈다. 이 각각의 고정 크기를 페이지(page)라고 부른다.

→ 장점

• 세그먼테이션에 비해 가장 중요한 개선은 유연성이다. 주소 공간을 사용하는 방식과 상관없이 주소 공간 개념을 지원할 수 있다. (힙과 스택이 어느방향으로 커지는지, 어떻게 사용되는지에 대한 가정)
• 굉장히 단순하다. 한 페이지가 8KB이고, 필요한 공간이 X일 때, X / 8만큼의 페이지만 있으면 된다.

페이지 테이블(page table)

• 각 가상페이지에 물리 메모리 위치 기록을 위하여 프로세스마다 페이지 테이블(page table)이라는 자료 구조를 유지한다.
• 주요 역할은 주소 공간의 가상 페이지의 주소 변환 정보를 저장하는 것이다.

가상 주소 변환 과정

• 작은 주소 공간(64바이트)을 가진 프로세스가 다음 메모리 접근을 수행한다고 가정하자. 한 페이지의 크기는 16바이트로 가정한다.

movl <virtual address, 21>, %eax

• 다음과 같은 변환 과정을 거친다.

  1. 프로세스가 가상 주소를 생성하면 운영체제와 하드웨어가 의미있는 물리 주소로 변환한다.
  2. 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소로 분할한다.
  3. 가상 주소 “21”을 이진 형식으로 변환하면 “010101”을 얻는다. 따라서 가상 주소 “21”은 가상 페이지 “01”의 5번째 바이트이다.
  4. 이 가상 페이지 번호를 가지고 페이지 테이블의 인덱스로 사용하여 가상 페이지 1이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다.

페이지 테이블은 어디에 저장될까?

• 4KB 크기의 페이지를 갖는 32비트 주소 공간을 상상해보자. 이 가상 주소는 20비트 VPN과 12비트 오프셋으로 구성된다.

4KB = 2^12 비트 정보를 나타낼 수 있다.
따라서 오프셋(offset)은 12비트이다.
가상페이지번호(VPN)는 32 - 12 = 20비트이다.

• 20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 페이지 번호가 2의 20승이라는 것을 의미한다. 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 가정하면 4MB의 메모리가 필요하다.
• 페이지 테이블이 매우 크기 때문에 이를 MMU안에 저장하지는 않을 것이다. 즉, 메모리에 저장한다.

페이지 테이블의 구성요소

1. Valid bit : 주소 변환의 여부를 나타낸다. 할당되지 않은 주소 공간을 표현하기 위해 반드시 필요하다.
2. Protection bit: 페이지를 읽을 수 있는지, 쓸 수 있는지, 또는 실행될 수 있는지 표시한다.
3. Present bit: 페이지가 물리 메모리에 있는지 혹은 디스크에 있는지(즉, 스왑아웃 되었는지) 표시한다.
4. Dirty bit: 메모리에 반입된 후 페이지가 변경되었는지 여부를 표시한다.
5. Reference bit: 페이지가 접근되었는지 추적하기 위해 사용된다. 이는 페이지를 교체할 때 매우 중요한 정보다.

문제점

• 물리 메모리 주소에 접근하기 위해선 반드시 페이지 테이블을 거쳐야 하기 때문에 느리다. 즉, 한 번의 추가적인 메모리 참조가 필요하다.

주소 색인 버퍼(Translation-Lookaside Buffer, TLB)를 활용

• 주소 변환을 빠르게 하기 위해서 TLB의 도움을 받는다.
• TLB는 가상 주소와 물리 주소 변환 정보를 저장하는 하드웨어 캐시다.
• TLB는 메모리 관리부(Memory-Management Unit, MMU)의 일부다.
• TLB를 도입함으로써 페이징이 사용 가능한 기법이 된다.

TLB의 동작과정

• 1. 먼저 가상 주소에서 가상 페이지 번호(VPN)을 추출한다.
• 1. 해당 VPN의 TLB 존재 여부를 검사한다.
     • 만약 존재하면 TLB 히트, 아니라면 TLB 미스
• 1. TLB 히트한 경우 TLB 항목에서 페이지 프레임 번호(PFN)을 추출한다.
• 1. TLB 미스한 경우 하드웨어가 변환 정보를 찾기 위해 페이지 테이블에 접근한다.
• 1. 프로세스가 생성한 가상 메모리 참조가 유효하고 접근 가능하다면, 해당 변환 정보를 TLB로 읽어들인다. (메모리 접근은 굉장히 느리다)
• 1. TLB가 갱신되면 하드웨어는 명령어를 재실행한. (TLB에 변환 정보가 존재하므로 TLB 히트)

Q. 문맥교환에서 성능저하를 TLB와 관련지어 생각해보자.

4) 멀티 레벨 페이지 테이블

• 기존 페이징 기법에선 프로세스마다 약 4MB(PTE)만큼의 메모리 부담을 안고 있었다. 이를 어떻게 해결할 수 있을까?

개념

• 멀티레벨 페이지 테이블에서는 선형 페이지 테이블을 트리 구조로 표현한다.
  1. 페이지 테이블을 페이지 크기의 단위로 나눈다.
  2. 페이지 테이블의 페이지가 유효하지 않은 항목만 있으면, 해당 페이지를 할당하지 않는다.
  3. 페이지 디렉토리(page directory)라는 자료구조를 사용하여 각 페이지의 할당 여부와 위치를 파악한다.
• 페이지 디렉토리(page directory)는 페이지 디렉토리 항목(PDE)들로 구성된다.
• valid bit를 가지고 있고, PDE가 유효하다면 그 PDE가 가리키고 있는 페이지들 중 최소한 하나가 유효하다는 것을 의미한다.

장점

1. 멀티 레벨 테이블은 사용된 주소 공간의 크기에 비례하여 페이지 테이블 주소 공간이 할당된다.
2. 페이지 테이블을 페이지 크기로 분할함으로써 메모리 관리가 매우 용이하다. (선형 페이지 테이블처럼 연속된 물리 공간이 필요하지 않다. 빈 공간이 산재되어 있더라도 페이지 디렉터리를 이용하여 그 위치를 파악할 수 있기 때문이다)

단점

1. TLB 미스 시 주소 변환을 위해 추가 비용이 발생한다.
   • TLB 히트 시 성능은 동일하지만, TLB 미스 시 두 배의 시간이 소요된다.
   • 페이지 디렉터리와 PTE 접근을 위해 각각 한 번씩 메모리 접근이 필요하다. (선형 페이지 테이블에서는 한 번의 접근만으로 주소 정보를 TLB에 탑재했다)
2. 페이지 테이블 검색은 단순 선형 페이지 테이블의 경우보다 복잡하다.

페이지 교체 알고리즘

• 지역성의 원칙: 어떤 페이지가 여러 차레 접근 되었다면 분명 어떤 가치가 있는 것이다.
• LRU(Least-Frequently-Used): 가장 적은 빈도로 사용된 페이지를 교체한다.
• LFU(Least-Recently-Used): 가장 오래 전에 사용하였던 페이지를 교체한다.
• LRU를 완벽하게 구현하기 위해선 모든 메모리 참조 정보를 기록해야 하고, 가장 오래된 페이지를 검색하는 것은 매우 고비용의 연산이다. LRU처럼 효율적으로 동작하지만, 유사하게 구현하기 위해 시계 알고리즘(Clock Algorithm)을 사용한다.

시계 알고리즘(Clock Algorithm)

1. 시계 바늘이 특정 페이지를 가리키고 있을 때, 현재 바늘이 가리키고 있는 페이지의 use bit가 1인지 검사한다.
2. 1이라면 최근에 사용되었으므로 use bit은 0으로 설정되고 시계 바늘은 다음 페이지(P + 1)로 이동한다.
3. 최근에 사용된 적이 없는 페이지를 찾을 때 까지 반복된다.
   • 변형된 시계 알고리즘: 교체할 때 페이지들을 랜덤하게 검사한다. reference bit가 1로 설정되어 있는 페이지를 만나면 그 비트를 지운다. reference bit가 0으로 설정되어 있는 페이지를 만나면 그 페이지를 교체 대상으로 설정한다.
   • 갱신된 페이지(dirty page)를 교체 대상으로 결정했다면 디스크에 변경 내용을 기록해야 하기에 비싼 비용을 지불한다. 따라서 이를 고려하여 변경되지 않은 페이지를 우선적으로 찾도록 한다.

쓰레싱(thrashing)

• 메모리 사용 요구가 과도하게 많고, 가용 물리 메모리 크기를 초과할 때 시스템은 끊임없이 페이징을 할 수 밖에 없는 상황을 말한다.

5. 병행성

주요 용어

1. 임계 영역(critical section): 변수나 자료 구조와 같은 공유 자원을 접근 하는 코드의 일부분을 말한다.
2. 경쟁 조건(race condition): 여러 쓰레드가 거의 동시에 임계 영역을 실행하려고 할 때 발생한다. (공유 자료 구조를 모든 쓰레드가 갱신하려고 하면 의도치 않은 결과가 생긴다)
3. 상호 배제(mutual exclusive): 하나의 쓰레드만이 임계 영역에 진입할 수 있도록 보장하는 것을 말한다.
4. 락(lock): 락은 공유 자원에 대한 동시 접근을 조절하기 위한 동기화 기법이다.
   1. 임계 구역에 진입하는 스레드나 프로세스의 수를 제어하여 동시접근을 방지한다.
   2. 스레드 간 동기화에 사용된다(특정 스레드가 락을 소유하고 있을 때 다른 스레드는 대기한다)

락의 종류

1. 뮤텍스(Mutex): 한 번에 하나의 스레드만 뮤택스를 소유하고 사용할 수 있도록 한다. 즉, 임계영역에는 뮤택스를 소유한 스레드만 접근할 수 있다.
   1. lock을 통해 임계영역에 사용한 후 unlock을 통해 다른 스레드가 뮤텍스을 획득할 수 있도록 한다.
2. 세마포어(Semaphore): 정해진 개수의 스레드가 임계 영역에 진입할 수 있도록 하는 동기화 기법이다.
   1. wait을 통해 세마포어 카운터 값을 1 감소 시키고, 0보다 작아지면 스레드를 대기 상태로 만든다.
   2. signal을 통해 세마포어 카운터 값을 1증가 시키고, 대기 중인 스레드가 있다면 깨운다.

데드락

• 두 개 이상의 프로세스 혹은 스레드가 서로가 가진 자원을 영원히 기다리는 상태를 말한다.

데드락 발생조건

1. Mutual Exclusion(상호 배제): 자원을 공유해서 사용할 수 없다.
2. Hold And Wait(점유 및 대기): 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기한다.
3. No Preemption(비선점): 자원을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없다.
4. Circular Wait(순환대기): 프로세스들이 순환(circular)형태로 서로의 리소스를 기다린다.

참고 자료

• 운영체제: 아주 쉬운 세 가지 이야기