Unix Concurrency Mechanism

• Pipes
  • FIFO queue, 한 프로세스가 쓰고, 다른 프로세스가 읽음
  • 실제 구현은 circular buffer, producer-consumer 모델
  • ex) ls | more, ps | sort etc
• Messages
  • 유닉스는 메시지 패싱을 지원하기 위해 msgsnd, msgrcv 시스템콜을 지원함
  • 메시지는 바이트들의 block

Continue reading

Deadlock

• 하나 이상의 프로세스들이 다른 블락(blocked)된 프로세스가 trigger 할 수 있는 어떤 이벤트 혹은 리소스를 기다리고 있는 상황
• 리소스(resource)?
  • Reusable resource
    • 한번에 하나의 프로세스에서만 안전하게 사용될 수 있는 자원(소모되지 않음)
      • e.g) processors, memory, I/O devices, files, databases, semaphores
  • Consumable resource
    • 생성되거나 소모될 수 있는 자원
      • e.g) interrupts, signals, messages, data in I/O buffers

Continue reading

Message passing

• 가장 일반적이고 쉬운 방법
• Mutual exclusion, Synchroniztion 뿐만 아닌 Communication 또한 가능
• 실제 동작?
  • send(des, msg)
    • 프로세스가 des 프로세스에게 msg를 보냄
  • receive(src, msg)
    • 프로세스가 src로부터 msg를 받길 기다림
  • sender와 receiver는 blocking이 될수도, nonblocking이 될수도 있음
    • blocking send / blocking receive (rendezvous - 둘 다 기다림)
    • nonblocking send, blocking receive (가장 일반적임)
    • nonblocking send, nonblocking reveive
  • Addressing : sender와 receiver를 어떻게 특정할 것이냐?
    • Direct addressing : receiver의 id를 명시해둠
      • direct addressing일 때 receiver는 다음 두 가지 방식으로 처리 가능
        • Explicit addressing
          • sender가 본인을 명시적으로 보내도록 함 designate
          • cooperating 하는 concurrent process에서 효율적인 방식
        • Implicit addressing
          • receive 할 때 sender의 id가 반환됨
    • Indirect addressing : 특정 receiver에게 보내는 것이 아닌 mailbox에 넣어둠

Continue reading

Producer / Consumer problem ?

• 하나 이상의 Producer가 데이터를 생성하고 버퍼에 넣음
• 하나의 Consumer가 버퍼로부터 데이터를 가져와서 소비함
• 한번에 하나의 Producer 또는 Consumer만 버퍼에 접근이 가능함 (race condition이 가능하기 때문에)
• 문제점?
  • Producer가 이미 다 찬 버퍼에 데이터를 삽입하지 않도록 보장해야 함
  • Consumer는 빈 버퍼로부터 데이터를 가져오는 요청을 하지 않도록 보장해야 함
  • semaphore를 이용하여 이런 상황에서의 synchronization 또한 가능함

Continue reading

Competing Processes

• Sharing a global resources? 다음 문제가 발생 가능
  • Need for mutual exclusion
  • Deadlock
  • Starvation
• Mutual Exclusion?
  • 상호 배제
  • 한번에 한 프로세스만 리소스를 사용하도록 제한하는 것
  • Critical Section을 한 프로세스만 진입하도록 보장해야 함
  • 데커알고리즘
  • 간단하게 처리하는 방법?
    • 임계 영역에 들어갈 때 interrupt를 disable, 나올 때 enable
      • 프로세서가 한 개일 때만 가능
      • 멀티 프로세서일 때는 왜 안되냐?
        • 다른 프로세스가 다른 프로세서에 dispatch 되어서 critical section에 들어갈 수 있음
  • Key terminolody
    • Atomic operation
      • 여려 개의 명령어를 하나의 실행 단위로 묶음 (나눌 수 없음)
      • All or nothing
      • HW-level atomic operations
        • test-and-set, fetch-and-add, compare-and-swap, load-link/store-conditional
      • SW-level solutions
        • 크리티컬 섹션에서 명령어 실행
      • 결과는 success / failure
    • Critical Section
      • 공유 자원에 접근하는 프로세스의 코드 영역으로 반드시 한 프로세스만 해당 자원에 접근할 수 있도록 보장되어야 하는 영역
    • Mutual Exclusion
      • 어떤 한 프로세스가 공유 자원에 접근하는 크리티컬 섹션에 있을 때, 필요로 하는 자원을 다른 프로세스가 점유(크리티컬 섹션)하지 못해야 함
    • Race condition
      • 공유 자원에 대해 여러 프로세스가 read/write를 할 때 실행 결과가 프로세스들 간의 interleaving에 따라 달라짐
• 그러면 실제로 critical section을 어떻게 구현하냐?
  • Special machine instructions (하드웨어적으로 지원)
    • 두 개의 명령어를 하나로 처리함 (reading and writing on single memory location)
    • Test-and-set, fetch-and-add, compare-and-swap etc
      • Test-and-set이 대부분 일반적임
        • x86, IA64, SPARC, IBM z serices etc.
    • 멀티코어 환경에서도 사용될 수 있음
    • 문제점?
      • busy waiting
        • 자원이 release될 때까지 test-and-set 반복해야 함
      • deadlock and stravation 가능
    • 장점?
      • 프로세스, 프로세서의 개수와 상관 없이 크리티컬 섹션 구현 가능

Continue reading

Thread?

• User-Level Thread
  • 애플리케이션이 쓰레드를 관리(생성, 소멸, 스케줄링)
  • 커널은 쓰레드 존재 여부를 알지 못함
  • 장점
    • 커널 권한을 요구하지 않기 때문에 context switching이 빠름
    • 스케줄링 알고리즘을 커널과 독립적으로 구성 가능
    • 기존 OS와 상관 없이 작동 가능, 하위 커널에 독립적
    • 정리 : concurrent processing, fast response, multiprocessing, resource sharing
  • 단점
    • 특정 쓰레드가 시스템콜을 호출할 경우 block되어서 모든 쓰레드도 멈춤
    • 따라서 시스템콜을 호출할 땐 장점을 활용 못함
    • 또한 멀티 쓰레드라고 하더라도 한 프로세스엔 하나의 프로세서만 할당 가능, 따라서 장점을 완전히 활용은 불가능
• Kernel-Level Thread
  • 커널이 쓰레드 생성, 소멸, 관리
  • 장점
    • 하나의 쓰레드가 시스템콜을 호출해서 block되어도 다른 쓰레드는 실행 가능(concurrency & parallel)
    • OS Kernel 자체도 멀티쓰레딩 가능 - 효율이 좋아짐
  • 단점
    • Context switching 오버헤드가 큼 (커널 레벨로 계속 들어감)
    • 쓰레드 생성 오버헤드가 비교적 큼(커널 레벨로 들어가야 하기 때문) : 유저레벨 쓰레드의 10배

Continue reading

Interrupt / Exception : 둘 다 예외적인 상황

• Interrupt :
  • 외부적인 이벤트, 현재 CPU에서 실행되는 프로세스와 상관 없음
  • keyboard interrupt, Direct Memory Access 후 완료를 CPU에게 알리는 상황
  • asynchronous(언제 발생할지 모름), external events
  • 인테럽트가 발생하면 현재 프로세스의 상태를 저장, 인테럽트 핸들러 실행 후 복구
  • 프로세서의 인테럽트 핀이 설정됨
    • #INT
    • #NMI (Non-maskable interrupt) : 우선순위가 #INT 보다 높음 (interrupt disable도 무시)
  • examples
    • I/O interrupt
      • 키보드 ctrl + c 입력, 키보드 입력
      • 네트워크 패킷 수신
      • DMA(Direct Memory Accessing) 완료
    • Hard reset interrupt : reset 버튼 누르기
    • Soft reset interrupt : ctrl + alt + delete
  • 정리
    1. 명령어 실행
    2. interrupt 핀 확인
    3. system bus의 interrupt vector 확인
    4. interrupt vector code 실행 (control transfer)
    5. handler returns to next instruction

Continue reading

프로세스?

• 실행중인 프로그램의 한 인스턴스
  • 프로그램은 디스크에 저장된 실행 파일, 이게 실행이 되면 프로세스

Continue reading