Developer Ahn

• Race Condition
  : 여러 프로세스가 공통된 데이터를 조작할 때 결과가 접근 순서에 의해 결정되는 현상
  
  

• Critical section
  : 프로세스의 코드의 일부분으로서, 다른 프로세스와 공동으로 사용하는 변수, 테이블, 파일 등을 변경하는 부분
  : 해결 방안
   1. 상호 배제(mutual exclusive) : 한 프로세스가 임계 구역에서 실행하고 있으면 어떤 프로세스도 임계 구역에 진입할 수 없어야 한다. SW로 가능하지만, 매우 복잡하여 HW로 대부분 보조
   2. 진행(progress) : 임계 구역을 실행하고 있는 프로세스가 없을 때, 몇 개의 프로세스가 임계 구역에 진입하고자 하면 이들의 진입 순서는 이들에 의해서만 결정되어야 한다. 또한 이 선택은 무한정 연기되어서는 안된다. 
   3. 한계 대기(bounded waiting) : 한 프로세스가 자신의 임계 구역에 진입하고자 요청을 한 후부터 이 요청이 허용될 때까지 다른 프로세스가 그들의 임계 구역에 진입할 수 있는 회수가 제한되어야한다.
  
   - Peterson's Solution (Dekker) : flag를 이용
   - Baker algorithm: 가게에 들어오는 손님들은 번호를 하나 받으며, 가장 낮은 번호를 받은 손님 순으로 서비스를 받는다. 그런데 모든 손님이 다른 번호를 받도록 보장할 수 없다. 만약 두 손님이 같은 번호를 받으면 이름 순으로 서비스를 받는다. 모두 다른 번호를 받도록 하기 위해서는 변호를 받는 것 자체가 임계 구역.
  
   - Bounded-Buffer problem
    

   - Readers and Writers problem
    
  

   - Dining-philosopher problem : 다익스트라가 제안, 다섯명의 철학자가 있다. 이들은 생각에 잠기거나 먹는 것 외에는 아무것도 하지 않는다. 철학자들은 원형 테이블에 앉아 있으며, 테이블 중앙에 밥이 있다. 그런데 젖가락이 다섯개 밖에 없다. 배가 고프면 철학자는 가장 가까이 있는 두개의 젖가락을 집는다. 철학자는 한 번에 하나의 젖가락만 집을 수 있으며, 옆 사람이 집고 있는 젖가락은 집을 수 없으며, 두 개의 젖가락을 모두 집어야 식사를 할 수 있다. 식사를 한 후에는 다시 두 개의 젖가락을 모두 내려놓고 생각에 잠긴다. -> 데드락 발생
  
   - Mutex
   : MUTual EXclusion으로 상호배제라고도 한다. Critical Section를 가진 스레드의 Running Time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술이다. 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 locking과 unlocking를 사용한다. 두 스레드가 동시에 사용할 수 없다는 의미.
  
   - Semaphore
   : 리소스의 상태를 나타내는 간단한 카운터

   
    ■ Busy waiting
     : 한 프로세스가 임계 구역에 있는 동안 다른 프로세스들은 임계구역에 진입하는 지속적인 loop 코드를 돌려야 한다.
     : 

  Busy waiting 을 하는 세마포어를 spinlock이라 한다.
     : spinlock은 문맥 전환이 필요없어 오래 동안 busy waiting을 하지 않는다면 효과적인 방법이다.
     : 성능저하를 초래할 수 있다 -> Semaphore
  
    ■ Blocking & Wake-up
     : 각 세마포어가 waiting queue에 할당
     : wait()로 block, signal()로 wake up 
     : wait와 signal을 반드시 원자적으로 수행
  
  - Mutex vs Semaphore 출처: http://ninako21.tistory.com/500
    : 세마포어는 뮤텍스가 될 수 있지만 뮤텍스는 세마포어가 될 수 없다.
    : 세마포어는 소유할 수 없는 반면 뮤텍스는 소유가 가능하며 소유주가 이에 대한 책임을 진다.
    : 뮤텍스의 경우 뮤텍스를 소유하고 있는 스레드가 이 뮤텍스를 해제할 수 있다. 하지만 세마포어의 경우 이러한 세마포어를 소유하지 않는 스레드가 세마포어를 해제할 수 있다.
    : 세마포어는 시스템 범위에 걸쳐 있고 파일 시스템상의 파일 형태로 존재한다. 반면 뮤텍스는 프로세스 범위를 가지며 프로세스가 종료될 때 자동으로 clean up 된다.
    : 가장 큰 차이점은 관리하는 동기화 대상의 갯수이다.
     뮤텍스는 동기화 대상이 오직 하나 뿐일 때, 세마포어는 동기화 대상이 하나 이상일 때 사용한다.
  
  - 모니터
    : 세마포어의 부적절한 사용으로 발생하는 에러를 해결하기 위한 높은 수준의 추상화 데이터 타입으로, 편리하고 효율적인 프로세스 동기화 메커니즘을 제공.
    

  
  

• CPU Scheduler
  : 다중 프로그래밍의 목적은 항상 실행할 수 있는 프로세스가 있도록 하여 CPU 사용 효율을 극대화하는데 있다.
  : CPU 스케줄러는 CPU가 유휴 상태가 되면 Ready queue에 있는 프로세스를 하나 선택해서 실행
  
  - CPU-I/O 버스트 주기
   : 프로세스는 실행되는 동안 CPU 실행과 입출력 대기 두 주기를 반복한다.
   : 계산 중심 프로세스는 적은 수의 매우 긴 CPU 버스트를 가지며, 입출력 중심 프로세스는 많은 수의 짧은 CPU 버스트를 가진다.
   
  

  
  
  - 비선점(Nonpreemptive) vs 선점(Preemptive)
  

    ■ 선점형 스케줄링
     : 어떤 조건이 만족되면 현재 실행중인 프로세스의 의사와 상관없이 그것의 실행을 중단하고 다른 프로세스를 CPU에 할당
      1. 프로세스가 실행중 상태에서 대기중 상태로 전환 (ex. 입출력 요청)
      2. 프로세스가 실행중 상태에서 준비 완료 상태로 전환 (ex. 인터럽트 발생)
      3. 프로세스가 대기중 상태에서 준비 완료 상태로 전환 (ex. 입출력 완료)
      4. 프로세스가 종료 
  

    ■ 비선점형 스케줄링
     : 프로세스가 CPU에 할당되면 그 프로세스가 종료되거나 대기중 상태로 전환될 때까지 CPU를 점유. 1, 4에서 스케줄링이 일어나면 비선점.
  
  - Dispatcher
   : 스케줄러가 선택한 프로세스를 CPU에 할당해주는 요소를 디스패처(Dispatcher)
   : 문맥 전환, 모드 전환
   : 디스패처가 하나의 프로세스를 중단하고 다른 프로세스를 실행하기까지 소요되는 시간을 디스패치 지연(dispatch latency)
  
  - 스케줄링 기준
   : CPU 사용 효율, 처리율, 반환시간, 대기시간, 응답시간
  
  - 스케줄링 알고리즘
   ■ FCFS(First-Come First_Serverd)
     : 먼저 요청한 프로세스 순으로 스케줄링, FIFO 큐를 이용하여 쉽게 구현
     : 비선점 방식
     : Convoy effect 발생 (하나의 큰 프로세스가 CPU를 양보할 때까지 다른 모든 프로세스가 기다리는 현상)
  
   ■ SJF(Shortest-Job-First) = SRTF
     : CPU 버스트 시간이 가장 짧은 프로세스 순으로 스케줄링
  
   ■ Priority Scheduling
     : 우선순위가 높은 프로세스에게 먼저 CPU를 할당
     : SJF도 우선순위 스케줄링 중 하나
     : indefinite blocking, starvation 현상 발생, 우선순위가 낮은 프로세스는 평생 실행 안되는 현상 -> aging 기법으로 해결
  
   ■ RR(Round-Robin)
     : 시분할 시스템에서 사용하는 알고리즘
     : time slice 단위로 시간이 경과될 때마다 현재 프로세스를 중단하고 다음 프로세스를 실행
     : Ready queue를 순환버퍼로 만들어 구현
     : 선점 방식
     : time slice 단위가 너무 크면 FCFS, 너무 작으면 Context switching 오버헤드가 큼
  
   ■ Multilevel Queue
    : 다중레벨 큐 스케줄링에서는 준비완료 큐를 여러 개의 큐로 나누어 사용한다.
    : 각 큐는 독자적인 스케줄링 알고리즘을 사용
    : 큐 간에는 별도 스케줄링 알고리즘을 사용

• 스레드
  : 프로세스와 마찬가지로 CPU의 작업 단위, 경량 프로세스
  : 텍스트 부분, 데이터 부분, 다른 운영체제 자원은 같은 프로세스에 속한 다른 스레드와 공유, 스레드는 스레드 식별자, 프로그램 카운터, 레지스터 집합, 스택(함수 호출 처리에 필요한 메모리)
  : 모든 프로그램을 다중 스레드를 사용하도록 바꾼다고 하여 성능이 향상되는 것은 아님

- 프로세스 vs 스레드
 : 성능적인 관점의 차이
 : 프로세스처럼 독립적인 구조가 아니고 스레드들 사이에 공유하는 요소가 있다. -> 동기화 처리가 필요함
 : context switching 걸리는 시간이 프로세스보다 짧고, 오버헤드 저렴
 : 프로세스에 비해 생성 비용 저렴 (공유 영역은 제외하고 만드므로)
 : 캐시 메모리 활용 측면으로 넘어가면 그 비용 차이는 더 커짐

- 유저 스레드 vs 커널 스레드
 ■ 유저 스레드
  : 사용자 공간에서 스레드 라이브러리를 통해 제공
  : 커널의 지원 없이 스레드의 생성, 스케줄링, 관리를 제공 (모드변경 x)
  : 프로세스마다 자체적 스케줄링 알고리즘을 가질 수 있으나, 커널은 스레드 단위로 시분할 하지 않음
  : 커널이 단일 스레드일 때 프로세스의 하나의 스레드가 블록되면 전체 프로세스가 블록 -> 비동기식을 이용하여 극복

 ■ 커널 스레드
  : 운영체제가 직접 지원
  : 커널이 스레드의 생성, 스케줄링, 관리 담당 (모드변경 필요)
  : 하나의 스레드가 블록되어도 같은 프로세스에 있는 다른 스레드를 계속 실행

- 다중 스레드 모델


- 스레드 풀
 : 스레드 풀은 프로세스가 생성할 수 있는 스레드의 수를 적절하게 관리하기 위해 사용되는 메커니즘
 : 스레드를 필요할 때마다 생성하지 않고 프로세스가 시작될 때 적정한 수의 스레드를 생성하여 스레드 풀에 대기하도록 한다. 스레드가 필요하면 이 풀에 있는 하나 스레드를 활성화하여 실행되며, 실행이 끝나면 다시 스레드 풀에서 대기한다. 만약 스레드 풀에 더 이상 활성화할 스레드가 없으면 처리 요청은 있을 때까지 대기하게 된다.