문제링크

Continue reading

Memory Management

Continue reading

Memory Management

Continue reading

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