list_elem

• ready-list, sleep-list 등에 어떻게 한 쓰레드당 하나의 값을 가지는 list_elem으로 그 모든 곳에 줄을 세우나 고민했었을 때
  • 쓰레드는 실행중이거나, ready-list 에 있거나 등 한 곳에 있을 수밖에 없다. 그래서 하나의 elem으로 그 모든 곳에 줄 세우기가 가능하다.
  • all_list(전체 쓰레드를 관리하기 위해 만들어줘야하는 list)에는 그래서 all_elem이라는 새로운 필드로 선언해준 후 줄 서게 했다.
• 어찌되었든 정리하면, 스레드는 실행 중이거나, ready quque에 줄 서 있거나 wait que에 줄 서 있는 등 한 곳에 줄 서 있게 된다.
• 줄 서 있게 되면서 스레드를 직접 prev, next 필드가 있는 list_elem을 줄세운다.
• thread 마다 각기다른 elem을 갖고 있어, elem 값으로 스레드로 찾아낼 수 있다.

OS의 time

• 코치님의 msg

  timer interrupt는 8254라는 hardware가 주기적으로 CPU에게 interrupt를 거는 것입니다.
  Kernel이 하는 게 아니라 hardware가 interrupt 하는 겁니다.
  timer interrupt를 사용해서 CPU 시간을 관리한다는 것이 느껴지셨으면 좋겠습니다.
  malloc library로 memory(공간)를 잘라서 관리했듯이 tick 단위로 나눠서 시간을 관리합니다.

• OS에서 시간이 결국 인터럽트가 걸리는 것으로 구현되었다는 것이 신기했다.

• 타이머 인터럽트가 걸리면 ticks가 증가한다. 일정 시간 마다 하드웨어가 인터럽트를 걸고 그에 따라 시간이 증가하는 개념
• 그렇기 때문에 intr_disable()을 하면 한 tick에 대한 절대적인 시간이 달라질 수 있다
  • 그러면 절대적인 시간을 구하는 방법은 real-time clock이 있어서 현실 세계의 시간을 표현하고, pc를 꺼 두어도 작동한다. pc를 다시 키면, 이 real-time-clock을 보고 시간을 관리한다고 한다. 출처 : https://husheart.tistory.com/78

Alarm Clock

• 기존에 구현된 것 Busy-Wait, Round-robin
  • Round Robin 각 프로세스는 동일한 크기의 할당 시간을 가짐, preempt 당하고 ready queue에 다시 줄 서기
• Busy-Wait와 Block-Wake에 대해서 코드를 보며 좀 더 확실하게 이해할 수 있었다.
  • Busy-Wait 프로세스가 조건이 참인지 계속 확인하게 되는 상황
• busy-wait로 구현된 timer_sleep 스레드는 잠들라고 명 받았던 시간보다 아직 시간이 안지났으면 yield()한다(reday-list로 간다)
  • 주의. 할당된 시간만큼 while문에 있는 것은 아님 yield 바로 함
• ready-list에 있기 때문에 다시 cpu를 할당 받으면 또 시간을 확인하고 시간이 아직 되지 않았다면 다시 yield
• busy-wait은 단일 쓰레드일 때 더 심각하다.
  • 멀티 쓰레드 일 때는 a에서 lock 잡았다고 b에서 try한다고 하면 a가 반납할 때까지만 기다렸다가 수행하면 된다. (critical section 부분의 수행 시간만큼만 기다리면 된다)
  • 단일 쓰레드일 때는 자기에게 할당 된 시간 만큼 while문을 (yield같은 코드가 아니라고 가정했을 때) 돌아야 한다.
• 그렇지만 block-wake는 오버헤드가 있다 cpu를 재우고, 다시 적당한 시점에 깨워서 ready로 하고. 그렇기 때문에 critical section의 코드 소요 시간이 매우 짧으면 busy-wait가 더 괜찮을 수 있다

미션 Block-Wake 로 구현하기

• 해결방법 : sleep-queue 도입해서 자기 차례가 아닌 애는 block 하고 timer_sleep()에 두면, timer interrupt가 발생시 (매틱마다)
  
• thread_awake해서 해당하는 스레드 깨우기 (sleep-list를 전부 순회)

Synchronization

동기화 : 공유 영역에 대해 동시접근이 발생하면 데이터의 불일치가 발생 (race condition : 여러 프로세스가 동시에 공유 데이터에 접근하는 상황, 공유 영역에 두 개 이상의 스레드가 동시 접근하면서 작업 중에 inturrpt를 당하는 등 중단 되면 다시 시작 되었을 때 (cpu 재선점) 공유영역이므로 다른 스레드에 의해 해당 영역이 변경되었음에도 실행 중단 전의 상태를 가정하고 연산을 마저 실행하게 되는 것)

• 공유데이터 접근하는 부분을 critical section이라고 칭한다. 한 ciritcal section에는 하나의 스레드만 접근 가능해야 한다.

쎄마포어

• P연산, V연산으로 이루어진다. 이 연산에 대해 atomic하게 접근 가능하게 한다. 조건을 체크하고 조건 값 까지 변경하는 것 까지 atomic하게
• 이런 자료형을 쓰는 이유는 조건을 확인하고 -> 그에 맞게 값을 바꿀 때 중간에 인터럽트 당했을 때 환경이 변하면 분명 조건을 확인하고 수행했지만 바뀐 조건을 확인하지 못하게 되는 여러 문제들이 발생한다.
  
• 만약 쎄마포어의 value를 자원의 개수라고 한다면 P연산이 일어나면 감소, V연산이 일어나면 자원 감소, P연산은 자원의 수가 0보다 클 때만 작동, 아니면 block
• V연산 시에 waiters에 기다리는 애가 있으면 그 중 우선순위가 가장 높은 애를 unblock해준다.
• 이 자원에 접근하려는 애들은 waiters에서 기다린다
  
  

쎄마포어의 value의 초기값

• 출처 : Three Easy Pieces
• 쎄마포어는 lock으로도 쓸 수 있고(잠그고, 안잠그고) condion variable로 쓸 수 있다 (특정 조건 만족되면 실행)
• 쎄마포어의 value의 초기값을 1로 한다면 1, 0 만 반복되어 lock처럼 작동한다
• 쎄마포어의 value의 초기값을 0으로 한다면 반드시 parent 쓰레드가 child 쓰레드가 한 번 수행된 다음에 수행되게 된다. https://velog.io/@bongf/Pintos-Priority-Scheduling-%EC%B1%85-%EC%A0%95%EB%A6%AC-Semaphore
• 이렇게 쎄마포어 value의 초기값이 쎄마포어의 성격을 결정한다.

Lock

• 락이 잠겨 있으면 실행을 못하고 잠금이 풀려있으면 실행이 가능한 형태

• 처음에 락이 잘 이해가 안갔는데 보호 하려는 코드 앞뒤로 자물쇠를 잠그는 느낌으로 이해했다.
  • lock acquire() 이라는 코드를 두는 것이 lock으로 잠궈두는 것. -> lock을 얻어야만 들어갈 수 있다.
  • lock release() 보호 영역을 나오며서 열쇠를 반납하고 기다리는 애를 한 명 깨운다.
  • 여기서 lock의 value는 1로 작용한다.
• 쎄마포어랑 다른 점은 정확히 하나의 쓰레드가 잠금을 유지할 수 있다는 점
  • 쎄마포어의 경우 자원을 여러 명이 가지고 있을 수 있다.
• 보호하려는 코드 주변에 lock을 설정해서 (lock acquire 체크 - 코드 - lock release) 해당 코드 부분에 오직 단 하나의 쓰레드만 접근 가능하게 설정
• 사실 이런 코드를 보호하는 방법은 단순하기 인터럽트를 disable하고 disable을 풀면서 보호할 수 있는데 멀티 프로세서에서는 동작을 하지 않고, 한 쓰레드가 특권을 남용할 수도 있고 (계속 lock 호출해서), 인터럽트가 손실되면 문제가 발생하고, 인터럽트가 마스크 되는 것은 비효율을 유발한다 (비용크다)
• 코드에서 sema를 쓴 것처럼 단순히 조건 값으로 lock을 풀고 조건 값을 확인하는 부분을 atomic하게 만들어야 중간에 thread를 빼앗겨도 에러가 발생하지 않는다.
  

Condition variable

• 조건이 참일 때까지 줄세우는 것. 여러 컨디션 x, y...하면 x.wait() y.wait()이런 식으로 조건별로 기다리는 쓰레드를 다르게 분배하고 적절한 애를 깨울 수 있다.
• 연산은 wait, signal.
  • wait하면 (쓰레드가 connd에 대한 lock을 가진 상태에서 wait를 해야 한다) condition variable에 줄서고, block 한다.
  • 이 때 block 되기 전에 lock을 반납해야 하는데 그 이유는 누군가의 signal을 받기 위함이다.
  • 누가 자원을 반납하면서 signal하면 그 중 우선순위가 가장 높은 애가 깨어진다.

• 기본 0으로 semaphore의 value가 초기화되므로 쎄마 다운을 하면 항상 0이 된다.
  
• lock을 거는 이유. 영원히 잠드는 것을 막기 위해서. 예를 들어. parent -> child 생성하고 조건을 거짓으로 초기화 하고 잠들려고 할 때(자식 먼저 실행하기 위해) 잠들기 딱 직전에 cpu를 뺏기면, 자식은 실행한 다음에 자원 반납이니까 signal을 보내서 깨울 것이다. 현재 부모가 잠자기 직전에 뺏겨서 잠든 애가 없어서 아무도 안깨어 나는데, 그 후 parent한테 다시 cpu가 돌아가면 부모는 실행되던 시점부터 시작하니까 다시 잠든다
• 이 역시 상황은 바뀌었는데 나는 하던 코드를 계속 수행(상황 체크x) 하는 것에서 발생하는 문제가 lock을 걸어서 상황이 바뀌지 않게 하는 것이다.
• 그래서 condition variable 쓰면 lock을 거는 것이 좋다. (필요 없는 경우도 아주 간혹 있지만)

모니터

• 쎄마포어 자체도 p연산, v연산 신경쓸 것이 많아서 자칫하면 큰 문제를 발생시킬 수 있다. 그래서 좀더 high level한 자료형을 만들었는데 그게 모니터
• 모니터 안에는 여러 condition variable이 올수 있다.
• 모니터 안에 공유되는 데이터 를 정의하고 모니터 내부의 procedure 통해서만 접근 가능하게 한다. 모니터 내부에서 동시에 여러 개가 실행될 수 없도록 원천적으로 봉쇄해서 프로그래머 입장에서는 그런 것들을 신경 안쓰고 단순하게 프로그래밍만.
• 모니터 자체에 애초에 한 스레드 밖에 접근 할 수 없도록
  • 출처 반효경 교수님 수업 자료
• 프로그래머가 직접 lock을 걸 필요가 없다는 것이 쎄마포어와의 중요한 차이
• 모니터는 쎄마포어의 value처럼 조건에 해당하는 부분이 condition variable,

Priority Scheduling

• 미션 : Priority 기반 스케줄링으로 바꿔라
• sol : ready_list에 들어갈 때, 넣을 때 우선순위가 높은 순으로 정렬되서 ready q에서 가장 먼저 나오는 애가 우선순위가 가장 높은 애가 나오도록 구현한다.

이해X

• condition variable이 이렇게 되어있다
• connd는 lock으로 보호되며 connd에 접근하는 작업은 lock으로 보호한다.
• connd에는 sema_elem의 elem, 즉, sema_elem들이 줄 서게 되는데, sema_elem은 자신이 줄 설 때 사용할 elem과 semaphore로 구성된다. semaphore에는 value와 waiters가 있어서 줄 설 수 있는데 여기에는 semaphore의 연산에 한 명만 넣을 수 있도록 (생성할 때 하나 만들고 block, 깨어나면서 sema_elem을 pop) 구성한다.
• 왜, thread로 줄 안세우고 sema_elem으로 줄 세울까 생각했는데
  • 1. 일단. semaphore로 줄 세운다면, 현재 쓰레드를 block 시키는 것을 semaphore의 함수를 사용해서 구할 수 있다
    • semaphore가 0으로 초기화 되니까, 항상 block
  • 2. 에서 thread의 elem을 직접 넣어주면 block 해야 하니까 lock을 release 못해줘서 sema로 감싸서 가짜를 넣어놓고 lock을 release 해 준 다음에 block 을 해준다고 (sema down에서 thread block) 생각했는데 생각해보니, elem을 넣어주고, block을 밖에서 넣어주면 된다.

• 질문방에서는 기존의 함수를 사용하기 위해서라고 한다.

Priority Inversion 문제

• Priorty 순으로 스레드가 선점 되야 한다는 조건 하에서 자신이 우선순위가 높으면에도 lock을 획득하지 못해 실행되지 못하는데 자신보다 우선순위가 낮으면서도 자신과 관련된 lock을 갖고 있지도 않는 애들이 실행되는 (자신보다 우선순위가 낮은 애들이 실행되는) 상황을 말한다.
• 그럼 출처 카이스트 os-lab
• 자신이 실행될 수 있도록 자신의 lock과 관련된 애들한테 자신의 우선순위를 준다 (자신의 우선순위가 제일 높기 때문에 애초에 실행 되었을 것)
• 이 주는 방식에는 multiple donation과 nested donation이 있다. multiple은 한 스레드가 여러 lock을 점유하고 있을 때 다양한 자신보다 우선순위가 높은 스레드들에게 priority를 기부받는다. 이 때 이들의 정보와 자신의 초기화된 정보를 저장하고 있다가 자신이 실행되면서 lock을 반환하면서 lock을 이전 우선순위로 갱신한다. (기부자가 실행되는 환경이라면 해당 기부자가 준 priority는 반환)
  
• nested는 내가 필요로 하는 lock을 보유한 holder 또한 어떤 lock을 기다리고 있는 상태다. 우선순위가 높으 나는 실행 되기 위해 타고타고 가서 실행 될 수 있도록 우선순위를 기부한다.