OS

[운영체제] 11강 - 16강 Concurrency; Concepts and Case Studies, Locks, Conditional Variables, Semaphore, Concurrent Data Structures, Deadlock

김치말이삼겹살 2024. 3. 29. 16:01

11강 Concurrency, Concepts and Case Studies

  • Thread : 여러개의 PC + 자체 레지스터로 구성 → 스택에 보관
  • Thread들은 서로 같은 주소 공간을 공유
  • Thread를 쓰는 이유
    • 병렬 처리 간단 → 하나의 작업 여러 스레드가 작업 → 시간 줄일 수 잇음
    • 느린 I/O로 프로그램 수행되는 것이 차단되는 것을 방지
  • TCD: thread register 상태 기록 (PCB와 유사)
  • Race Condition : 자원 사용하기 위해 두 스레드가 레이스를 하듯 경쟁; 예상과 다른 결과
  • Critical Section: 공유 변수에 접근하는 코드 부분 → Lock
  • 함수 내 지역 변수를 리턴값으로 쓰면 dealloc 될 수 있으므로, 함수의 인자를 통한 리턴값 전달
  • 모든 lock은 초기화 되어야 → 2가지 방식
    • PTHREAD_MUTEX_INITIALIZER 이용
    • pthread_mutex_init 활용
  • lock, unlock 시 오류 코드 확인 못할 수 있음 → trylock, timelock(일정 time 안되면 return)

상태 변수 (state variable)

  • while문 사용 → 다른 code에서 lock 풀어버리는 것 방지

12강. Locks

  • Lock: critical section 작동 시 atomicity 보장해주는 것이 가장 중요 → 시험에서도 atomic하게 작동되는지를 코드를 주고 물어볼 것
  • Lock의 평가 지표
    • Mutual Exclusion : 한 놈만 쓰게 해주나?
    • Fairness : 줄 선 순서대로 사용하게 해주나?
    • Performance : lock을 사용 전후로 시간 차이가 큰가? (작을수록 좋음)
  • interrupt control : lock의 원자성 구현하기 가장 쉬운 방법 → interrupt 차단해버리기
  • interrupt control의 문제점
    • 멀티 프로세서에서는 작동하지 않음
    • application에 너무 많은 신뢰를 줘버림 → user level에서는 사용 불가 → 무한루프 갈기면 어쩌게?
    • interrupt 끄면 disk I/O 완료 등의 옵션을 아예 차단해버리는데, 이럴 때도 문제가 생김
    • 효율성 : interrupt 끄고 켜는 것 속도가 썩 좋진 않아
  • flag : hardware의 도움을 받아서
    • lock 함수 내에서 flag가 1이면 spin lock, while 문 탈출 후 flag를 1로,
    • unlock 때 flag 0으로
    • spinlock에서 interrupt 발생하면 flag가 1인 thread가 2개가 생길 수 있게 됨
    • spinlock의 시간 손해 이슈
  • TestAndSet : 인자로 주어진 포인터(*ptr)가 가리키는 값을 인자로 주어진 값(new)으로 바꾸고, 이전에 인자로 주어진 포인터가 가리키던 값(old) 리턴
    • mutual exclusive 하나, 공정성을 보장할 수 없음. CPU 단일일 때 오버헤드 크다.
    • 명령을 작성하고, 실제 Spin lock울 구현하시오
  • Compare-And-Swap : 인자로 주어진 포인터(*ptr)가 인자로 주어진 기대하던 값(expected)와 같으면 인자로 주어진 새로운 값(new)로 바꾸고 1 리턴, 그렇지 않으면 냅두고 0 리턴
    • 명령을 작성하고, 실제 Spin lock을 구현하시오
  • Load-Linked and Store-Conditional
    • load-linked : 인자로 주어진 포인터(ptr)가 가리키는 값(*ptr) 리턴
    • Store-Conditional : 인자로 주어진 포인터가 가리키는 값 (*ptr)이 아무도 업데이트를 시키지 않았다면 인자로 주어진 값(value)로 (*ptr) 변경 후 1 리턴, 그렇지 않으면 0 리턴
    • Load-Linked와 Store-Conditional을 이용한 명령 작성하고, 실제 Spin lock 구현하시오
  • FetchAndAdd : 인자로 주어진 포인터가 가리키는 값(*ptr)을 1 증가시키고, 옛 값(원래 인자로 주어진 포인터가 가리키던 값) 리턴
  • Ticket Lock → FetchAndAdd 사용:
    • FetchAndAdd를 사용한 ticket lock 코드를 작성하시오.
    • lock에서는 FetchAndAdd를 load→ticket; unlock에서는 FetchAndAdd를 lock→turn에 걸기,, (12강 19p)
  • Hardward-based spin lock은 간단하지만, 도는 것으로 thread가 time slice 낭비해버려서 OS가 spinning을 방지하기 위해 도움
    • queue와 park(), unpark() system call 사용
    • lock에서 park()를 통해 다른 스레드가 사용을 마치면 깨워달라는 신호를 보내고 ready state로 변경, unlock에서는 unpark()을 통해 스레드를 threadID로 깨워줌.
    • lock에서 queue에 thread를 넣고 park()를 할 때 문제를 서술하시오
      • queue에 넣자마자 다른 thread에서 unpark() 해버리는 경우, 해당 스레드를 unpark()해줄 스레드가 없어짐. 무한대기 상태
      • 이의 해결책 setpark() → 곧 park()한다는 신호를 주는 것이다.

13강. Conditional Variables

  • Parent Waiting for child 코드에서, 조건 변수를 사용하고, 상태 변수까지 사용하는 이유?
    • join이 먼저 실행될지 보장할 수 없음; exit가 먼저 실행되어 깨울 스레드가 없음에도 signal 보내버리고 끝나면 자고 있는 thread를 깨워줄 수 있는 장치가 전혀 없게 됨
  • Producer/Consumer Thread에서, if를 써서 생기는 문제점
    • 소비자가 2, 생산자가 1인 상황에서, context switch 당시에 생산자 스레드가 일어날지, 소비자 스레드가 일어날지 알 수 없어 context switch이후 버퍼의 상태가 변경되는 상황이 생김.
    • while 사용
  • Bounded Buffer
  • Mesa Semantics
  • Hoare Semantics
  • 조건 변수가 1개일 때 생기는 문제점
    • 생산자를 깨워야 하는데, 소비자가 소비자를 깨우는 경우가 생길 수 있음. 결국에 모두가 sleep 해버리는 상황 존재
    • 생산자는 소비자만 꺠우고, 소비자는 생산자를 깨우도록 조건 변수를 2개 두어야 함
    • producer를 꺠울 떄는 signal 날릴 때 &emtpy(1st 인자),consumer를 깨울 떄는 signal 날릴 떄 &full(1st 인자)
  • 최종 final solution에서 빈칸 뚫는 문제
    • 생산자는 buffer 가득 찼을 때만 cond_wiat
    • 소비자는 buffer 쫄닥 굶었을 떄만 cond_wait
  • Covering Conditions(p.30)
    • 공간 allocate 할 때 조건 빈칸 뚫는 문제
      • allocate는 원하는 size보다 공간이 적을 때만 cond_wait
      • free는 반대

14강. Semaphore

  • Thread들 주고 semaphore 초기값이 얼마가 되어야 하는지 묻기
    • sem_wait() 하면 일단 semaphore 값 깎고 들어간다는 것 잊지 말길!
    • wake: sleeping state을 ready로 바꾸어 주는 것 의미
  • parent thread가 child thread를 기다릴 때 semaphore 초기값 어떻게 두어야 하겠는지 묻기
    • 0으로 두자
  • Semaphore mutex 범위를 어떻게 둘 것인가
  • Reader-Writer locks
    • reader lock get → 1일때 write lock도 얻어버려
    • reader lock release → 0일 때 write lock도 unlock 해버려
  • Zemaphore 함수 구성 다시 확인

15강. Concurrent Data Structures

  • 자료 구조 lock에 중요한 2가지 요건
    • correctness : mutual exclusive 보장
    • performance : 속도 보장
  • mutual exclusion 적용하기 위해 자료구조에 일일히 lock갈겨버리면 → 속도가 개느려져
  • Sloppy Counter: 그래서 local counter, global counter를 도입해버린다
    • local 에서 주기적으로 global 으로 합산
    • 임계값 S를 설정 → local counter가 S 이상이 될 경우 S를 global로 넘김 → local counter = 0으로 설정
    • S값에 따른 trade-off
      • S값 크면 성능 좋아지지만, lag 발생 가능 (update되는 값과 local 사이의 괴리 커짐)
      • S값 작아지면 concurrency는 증가하나, 성능이 나빠짐
  • Concurrent Linked List → lock 얻고 해제할 때, release를 두 군데에서 함 (에러 발생하는 부분에서 release 갈겨버리는 것
    • 이 문제를 해결하시오.
    • 새 노드를 리스트에 추가하는 부분만 lock하기
    • lookup 시에는 초기에 lock을 걸고, while 문 끝나는 부분에만 unlock걸기
  • queue에 lock걸어버리기
    • node 단위로 lock걸기 → 다음 노드의 lock 잡고, 현재 노드의 lock 해제

16강

  • Bug 종류 : Non-Deadlock >>> Deadlock
    • Non-Deadlock
      • 전체 non-deadlock bug의 97퍼가 아래 2개
      • atomicity violation → mutual exclusive 하게 만들어
      • order violation → 순서 지정 : lock + 조건 변수 + 상태 변수
    • Deadlock : 교착 상태
  • DeadLock이 발생하는 이유가 무엇인가?
    • complex dependency
    • encapsulation: 두 벡터 사이 덧셈 연산 시 두 벡터에 대한 lock을 모두 잡아야 하는데, 다른 thread/ process에서 한 벡터에 대한 lock을 쥐고 돌려주지 않는 경우
  • Deadlock의 발생 요건
    • circular wait : lock에 order 부여 → 개빡셈
    • hold-and-wait : trylock : lock 시도해보고 안되면 sleep → 동시에 trylock하는 경우 livelock problem → random delay로 해결
    • no preemption : 잡아야하는 lock 최상단에 lock을 또 둚으로써 해결
    • mutual exclusion : lock을 이용하지 않고**(wait-free)** compare and swap을 통해 해결 → hardware 도움으로 atomic한 task 가능
반응형