크래프톤정글 8주차; WIL - PintOS Project 1 Threads

2022-12-16, 2022-12-17

PintOS 프로젝트 - 쓰레드와 동시성

참고: https://omscs.gatech.edu/cs-6200-introduction-operating-systems-course-videos

무엇?

1. 쓰레드는 무엇인가?
   • 쓰레드는 장난감 샵의 일꾼!
     1. 이 일꾼은 능동적인 주체다
        • 장난감 주문을 위한 일을 한다 = 쓰레드는 프로세스를 수행한다
     2. 다른 일꾼들과 동시에 일한다 = 많은 쓰레드는 동시에 일한다(동시성의 개념)
     3. 다른 일꾼들과 동시에 일할 때 협업이 필요하다
        • 효율적으로 일하기 위해, 도구, 일하는 공간, 부품 등을 서로 공유한다 == I/O 기기, CPU, 메모리 등을 공유한다
          → 어떤 쓰레드가 이러한 자원에 접근할 수 있는지 어떻게 결정할까?
2. 스레드와 프로세스는 어떻게 다른가?
3. 어떤 자료구조가 쓰레드를 관리하기 위해 사용되는가?

운영체제의 큰 그림

참고: https://www.youtube.com/watch?v=BoJ1eaE5F-I&list=PLVsNizTWUw7FCS83JhC1vflK8OcLRG0Hl&index=27

왜?

운영체제는 왜 존재할까?
운영체제는 어떤 역할을 할까?
운영체제를 왜 배워야 할까?

무엇?

• 커널이란?
  • 운영체제의 핵심 서비스를 담당하는 부분
  • UI는 운영체제에는 속하지만 커널에는 속하지 않음
• 시스템 콜과 이중 모드란?
  • 시스템 콜(=시스템 호출)
    • 사용자가 실행하는 프로그램은 자원에 직접 접근할 수 있을까? NO! 자원에 직접 접근은 위험하다!
    • 응용 프로그램이 자원에 접근하려면 운영체제에 도움을 요청(=운영체제의 코드를 실행)해야 함
  • 이러한 자원 접근 제한은 이중모드로 구현이 된다
    • 이중모드: CPU가 명령어를 실행하는 모드를 크게 사용자 모드와 커널 모드 두 가지로 구분하는 방식
    • 사용자 모드:
      • 운영체제 서비스를 제공받을 수 없는 실행모드
      • 커널 영역의 코드를 실행할 수 없는 실행 모드
      • 자원 접근 불가
    • 커널 모드:
      • 운영체제의 서비스를 제공받을 수 있는 실행 모드
      • 자원 접근을 비롯한 모든 명령어 실행 가능
    • 어떤 모드인지 CPU가 어떻게 알 수 있을까?
      • 플래그 레지스터에 슈퍼바이저 플래그 → 1인 경우 커널 모드, 0일 경우 사용자 모드
    • 언제 커널 모드, 사용자 모드로 바뀔까?
      • 시스템 호출을 하면 커널 모드로 전환 됨 → 일종의 소프트웨어 인터럽트
• 운영체제의 가장 핵심적인 서비스는?
  1. 프로세스 관리
     • 프로세스(or Task) == 실행 중인 프로그램
     • 수많은 프로세스들이 동시에 실행 → 동시다발적으로 생성/실행/삭제되는 다양한 프로세스를 일목요연하게 관리
     • paging, swapping을 통해 모든 프로세스를 메모리에 다 올리지 않고서도 실행할 수 있음
  2. 자원 접근 및 할당
     • CPU
     • 메모리(페이징, 스와핑)
     • 입출력장치(인터럽트 서비스 루틴 )
  3. 파일 시스템 관리
     • 보조저장장치의 정보 덩어리를 파일이라는 단위로 묶어서 저장
     • 파일을 묶은 단위를 폴더, 디렉토리

CPU 인터럽트란?

참고: https://www.youtube.com/watch?v=V4lp6iGoUFY&list=PLXvgR_grOs1DGFOeD792kHlRml0PhCe9l&index=5

무엇?

왜?

인터럽트 개념 개요 잡기.

2022-12-18

프로세스와 스레드

참고: https://www.youtube.com/watch?v=2i3dInwVeUM&list=PLXvgR_grOs1DGFOeD792kHlRml0PhCe9l&index=10
https://www.youtube.com/watch?v=x-Lp-h_pf9Q

무엇?

1. 프로세스와 스레드의 차이
   

왜?

프로세스와 쓰레드는 어떻게 다르고, 어떤 맥락에서 등장하는 걸까?

프로세스 상태(휴식, 보류)와 문맥 전환(context switching)

참고: https://www.youtube.com/watch?v=a2GDsaReFEA&list=PLXvgR_grOs1DGFOeD792kHlRml0PhCe9l&index=11

무엇?

• 프로세스의 대기 상태
  • 휴식 sleep: 자발적. 나 자러 갈게.
    • 인수로 정해준 시간 이후에(e.g.: 10ms) 대기열에 재진입 → 앞 애들이 끝나야 얘가 다시 실행 됨 ⇒ 실제로 걸리는 시간은 인수로 정한 시간 + α
  • 보류 suspend: 외부 요인(OS나 다른 프로그램)에 의해 의도 되지 않게 대기하는 상태. 너 비켜봐봐.
    • e.g.: 스왑 날때(메모리에 있던 거를 디스크로 옮길 때 )
• 휴식, 보류가 되면 ready-queue에서 이탈하게 됨 -> CPU 쓸 생각 없다는 것

왜?

프로세스의 상태 변화는 어떻게 이루어질까?
그리고 그 때 어떤 일이 발생하는지.

프로세스 생성과 복사 fork()와 exec()

참고: https://www.youtube.com/watch?v=RzN18na94Wc&list=PLXvgR_grOs1DGFOeD792kHlRml0PhCe9l&index=12
https://woochan-autobiography.tistory.com/207

무엇?

• fork() : 부모 프로세스를 복사하여 자식 프로세스를 생성
• exec() : 새로운 프로세스를 생성하지 않으며, exec()를 호출한 프로세스가 새로운 프로세스의 코드로 덮여 쓰어지며 대체 됨. 프로세스 아이디가 같음. (fork보다 더 효율적)

왜?

가상메모리 할 때 한번 노트했던 부분.
프로세스 개념을 공부하다보니 fork와 exec 함수가 자주 나오는데 정확히 어떤 개념인지 궁금해졌다.

멀티스레딩과 동기화 기본

참고: https://www.youtube.com/watch?v=y60nIDJAyJQ&list=PLXvgR_grOs1DGFOeD792kHlRml0PhCe9l&index=13
Process Explorer 다운로드

무엇?

• 프로세스와 쓰레드의 구분 (※ 프로세스와 스레드 노트 참고 )
  • 다중 프로세스 = 멀티 태스킹
  • 다중 쓰레드 = 멀티 쓰레딩
• 멀티 쓰레딩 vs 멀티 프로세스?
  • 효율 측면에서 멀티 쓰레딩이 더 효율적일 수 있음 → 멀티 프로세스 조건은 각각 VMS를 부여해주어야 하므로
• 동기화 이슈
  • 쓰레드는 연산의 단위 → CPU는 쓰레드가 선점한다. (다만 권한은 OS가 프로세스에게 부여함 )
  • 쓰레드들은 각기 다른 연산을 하면서 흐름이 다르기 때문에, 동기화가 중요한 이슈임
  • 동기화란?
    • CPU 스케줄링에서 동기화란 경쟁 조건을 막고 프로그램의 정확한 작동을 보장하기 위해 다양한 쓰레드나 프로세스를 조정하는 것을 말한다. 다양한 동기화 메커니즘을 통해 달성될 수 있는데, 예를 들면 lock, 세마포어, 조건 변수 같은 것이다.
  • 한 프로세스의 쓰레드들은 VMS 안의 공유 자원을 두고 경쟁한다 ∴멀티쓰레딩을 얘기할 때 전역 변수 등에 대해서 접근할 때 race condition 등이 발생하면서 예측이 어려워짐. → 우연에 기대게 된다. → 이러한 예측 불가능, 우연에 맡기는 코드는 그렇게 좋지 않다.
    • race condition (경쟁조건, 프로세스 안의 공유 자원을 선점하려는 상황; e.g. 프로세스 가구 내의 화장실을 선점하려는 상황)
  • 쓰레드도 프로세스처럼 상태가 존재. 슬립, 대기 모드 → 모든 프로세스는 적어도 1개 이상의 스레드를 가지고 있으며, 사실은 스레드가 대기, 실행 되는 것.
  • 쓰레드의 종료 이벤트를 대기하는 방식으로 동기화를 다룰 수 있다 (리눅스, 유닉스에서는 시그널, 윈도우에서는 이벤트)
• 그 외
  • 쓰레드는 각자 따로 논다
  • 단순 대입 연산은 코어가 서로 섞이지 않음. (atomic한 연산을 보장)
  • sleep(0) -> 대기열에 빠져서 뒤로 가겠다

왜?

PintOS의 project 1의 주요한 구현 과제 중 하나인 동기화.
동기화는 왜 필요할까?

2022-12-19

CPU 스케줄링 개요

참고: https://www.youtube.com/watch?v=DK_tugBjxj8

무엇?

• OS와 프로세스(스레드)는
  • 식당 관리자 = OS
  • 손님 = Process(thread)
  • 식당 관리자(OS)는 유저 프로그램이 잘 돌아가도록 도와주기 위해 존재함.
• CPU 스케줄링의 목적 : 시스템 과부하 상태를 막겠다
• 스케줄링의 단계
  • 고수준: 작업 스케줄링 = job 스케줄링, 프로세스를 묶은 단위, 손님 수 조절(정원을 벗어난 애들 대기세우기 )
  • 중간수준
  • 저수준 : 각 손님의 주문, 요리 제공 순서를 미세하게 조절하는 단계(프로세스와 쓰레드가 CPU를 선점해서 작동하게 하는 것 )
• 스케줄링 시 고려사항 (스케줄링 알고리즘)
  • 선점형 스케줄링 preemtive: 일반적인 경우. (e.g. 엑셀이 시작해도 워드를 써야할 때가 되면 OS가 엑셀을 웨잇시킬 수 있음)
  • 비선점형 스케줄링 non-preemtive: 일단 일이 시작되면 되돌릴 수 없음. (e.g. 엑셀이 끝날때까지 워드는 기다려야 함) 이런 건 언제 사용하지?
• 프로세스/스레드의 우선순위
  • 쓰레드별로 우선순위를 정함 - 보통의 경우 5단계
  • 일반적으로 프로세스 띄우면 보통으로 출발
• 우선 순위를 적용한 스케줄링은?
  • 압축 해제 같은 경우, 20분 걸리나 25분 걸리나 차이 없으므로 우선순위 낮게 됨(운영체제, 입출력 중심, 백그라운드)
  • 미디어 플레이어(동영상 플레이어)는 우선순위 높게해서 안 끊기게.(포어그라운드, 전 프로세스. 눈에 잘 보이는 GUI가 끊기거나 하면 굉장히 화가 많이 난다!)
  • 서버같은 경우, 백그라운드 서비스에 우선순위를 더 줌(입출력이 기본이라 )

왜?

CPU 스케줄링과 우선순위 개념이 궁금.

스핀락(spinlock) 뮤텍스(mutex) 세마포(semaphore) 각각의 특징과 차이

참고: https://www.youtube.com/watch?v=gTkvX2Awj6g

무엇?

• 락
• 임계구역critical section: 단독의 쓰레드, 혹은 프로세스만 접근할 수 있는 영역 (락을 얻어야 접근할 수 있고, 할일이 끝나면 락을 반환(언락)하여 다음 쓰레드, 프로세스가 사용할 수 있게 함 )
• atomic 명령어란; 실행 중간에 간섭받거나 중단되지 않음. 같은 메모리 영역에 대해 동시에 실행되지 않음.
• 스핀락: 락을 가질 수 있을때까지 반복해서 시도 -> CPU 낭비 -> 뮤텍스
• 뮤텍스: 락을 가질 수 있을때까지 휴식 (큐를 이용)
• 세마포어: 시그널 메커니즘을 가진, 하나 이상의 프로세스 .스레드가 임계 구역에 접근 할 수 있도록 하는 장치
  • 뮤텍스 코드와 거의 동일.
  • lock -> wait
  • unlock -> signal
  • wait과 signal 사이의 일이 실행된다 ! -> wait과 signal이 서로 다른 프로세스에서 실행될 수 있고, 그러면 프로세스간의 일의 순서를 정해줄 수 있음.
  • -> 시그널 메커니즘을 가진다

왜?

세마포어의 개념에 대해서 궁금.

2022-12-20, 2022-12-21

PintOS - Thread; Alarm Clock

참고: https://oslab.kaist.ac.kr/pintosslides/
https://www.youtube.com/watch?v=myO2bs5LMak

무엇?

• 슬립 리스트 정렬하기
  1. 슬립 리스트를 불러올 때마다 local_tick 값에 따라 오름 차순 정렬 확인할 때마다 정렬하면 비효율적… → list_inserted_ordered를 이용해서 sleep_list에 원소 삽입
• 리스트 원소 비교하는 함수 cmp_wakeup_tick (Returns true if A is less than B, or false if A is greater than or equal to B.) 리스트의 필드를 인자를 받아 인자에 따라 비교하게 만들면? (e.g. t->{필드변수명})→ 조금 구현이 복잡할 거 같다!
  • 변수
    • A의 local tick
    • B의 local tick
  • 알고리즘
    1. 리스트가 비어있거나 원소 하나면 ?→ 이미 기본 코드에 에러 처리가 되어 있음
       1. 어떡하지?
    2. 아니면
       1. A < B : true
       2. A >= B : false
• modified thread_sleep
  1. list insert ordered
  2. 최소 wake_up tick 찾기
  3. 최소 웨이크업 틱을 next_tick_to_awake로 업데이트
     처음에 아래 1,2 를 하나의 함수로 묶으려고 했으나, 일단 ppt대로 해봄
• 최소 틱을 가진 스레드 저장하는 함수 (update_next_tick_to_awake)
  1. 틱을 받아서 next_tick_to_awake 변수에 저장
• global tick→ next_tick_to_awake 반환하는 함수 (get_next_tick_to_awake)
  1. sleep list의 맨 앞 요소의 local tick을 반환→ 현재 next_tick_to_awake 값을 반환
• global tick → next_tick_to_awake(ticks) 을 이용한 wakeup
  1. next_tick_to_awake와 현재 ticks 비교
  2. cpu 인터럽트 off (슬립 리스트에 원소 추가 되는거 방지? → 바로 실행할 애가 아니기 때문에 굳이 할 필요가 없다 )
  3. while ntta <= 현재 tick
     1. 슬립 리스트의 맨 앞 요소의 상태를 블럭에서 레디로 바꾸기
     2. 다음 요소의 tick = global tick
  • ▽ 수정한 거(기본 코드의 else 절만 바꿈 )
    1. 슬립 리스트의 마지막 원소에 도달할 때까지
       1. 만약 쓰레드의 틱이 현재 틱보다 작거나 같다면
          1. 슬립 리스트에서 제거
          2. 스레드 언블락
       2. 아니라면
          1. 깨울 시간이 되지 않은 해당 쓰레드의 틱을 최소 틱으로 저장
          2. 브레이크하여 while문 탈출
  4. cpu 인터럽트 on

왜?

list front, list head, list begin, list entry의 차이는 뭘까 …?
→ list front, flist begin은 리스트가 empty일때 사용할 수 있는지 없는지 에러 처리에 차이가 있었다.

PintOS - Thread; Priority Scheduling

참고:https://www.youtube.com/watch?v=myO2bs5LMak

무엇?

1. 현재의 핀토스

   • fifo 스케줄링 → 우선순위에 따라 cpu를 선점하지 못함!

2. 중요한 키워드

   • priority inversion : 높은 우선순위를 가진 프로세스가 낮은 우선 순위를 가진 프로세스를 기다리고 있는 것
   • → priority donation: priority inversion을 해결할 하나의 방법. 프로세스의 우선순위를 락 홀더에게 물려줌. 더 높은 프로세스가 락을 요청했을 때, 실행중인 프로세스에게 그 높은 우선순위를 물려줌. 따라서 실행중인 프로세스는 계속 실행되고, 그 이후에 그 다음 요청했던 프로세스가 실행 됨.
   • Nested Donation: 우선순위를 연속적으로 물려 받게 되는 것.
   • multiple donation : 여러개의 락을 T1이 갖고 있을 때, C가 락을 가지면서 나머지 락을 요청하는 프로세스 중 높은 우선순위로 T1의 우선순위가 업데이트 되어야 함.
   • Multiple Donation을 위한 자료구조(Donations : list of donors): 쓰레드가 donors의 리스트를 유지해야 한다! lock을 해제시킬 때마다, 자신의 donor 중에 가장 큰 우선권을 가진 애를 찾아야 함. (list max 이용하면 될까?, 자신의 원래 프라이어리티를 저장할 필요가 있음)
   • nested donation을 위한 자료구조(wait_on_lock : lock that it waits for): 각 쓰레드가 기다리고 있는 lock을 표시함. 일단 우선순위를 누군가에게 물려주면, 현재의 우선순위를 자식에게 물려줘야 하는지 체크해야 함. 구현 완전히 이해 안 됨

3. 요구사항

   1. 레디 리스트를 우선순위로 정렬하여, 레디 리스트에서 쓰레드를 꺼낼 때 우선순위가 높은 것을 꺼낼 수 있도록 하기
   2. preemtion (선점) 구현
      • 새 쓰레드를 레디 리스트에 넣을 때(타이머 인터럽트가 호출될 때마다 말고 ), 실행 중인 쓰레드의 우선순위와 새 쓰레드의 우선순위를 비교한다
      • 실행중인 스레드보다 새로 레디 리스트에 들어온 스레드가 더 높은 우선순위를 갖고 있으면, 새롭게 삽입된 스레드를 스케줄링한다.
   3. 동기화 primitive - lock, 세마포어, condition variable
      • 동기화 primitive를 위해 wait 리스트 정렬 (세마포어, condition variable )
      • lock, semaphore, condition variable을 기다리고 있는 쓰레드들의 대기 리스트에서 쓰레드를 선택할 때, 가장 높은 우선순위를 가진 쓰레드를 선택하여 CPU를 사용하도록 한다.
   4. 동기화 이슈 - priority inversion
      • Priority donation 구현
      • Multiple donation 구현
      • Nested donation 구현

4. 기존 존재하는 함수들

   • thread_set_priority
   • thread_get_priority

5. todo

   1. 레디 리스트를 우선순위로 정렬하여, 레디 리스트에서 쓰레드를 꺼낼 때 우선순위가 높은 것을 꺼낼 수 있도록 하기
      • cmp_priority() 함수 추가 ① bool cmp_priority (const struct list_elem *a_, const struct list_elem *b_, void *aux UNUSED) -> 첫 번째 인자의 우선순위가 높으면 1을 반환, 두 번째 인자의 우선순위가 높으면 0을 반환 list_insert_ordered() 함수에서 사용
      • 새로운 thread가 생성 되거나(thread_create()) block 되었던 thread가 unblock 됐을때(thread_unblock()), ready_list에 thread가 추가되는데 우선 순위에 맞춰 들어가야 한다. ①
        • thread_unblock() 함수 수정 : ready_list를 우선순위로 정렬 하기 위해. list_insert_ordered() 함수에 사용되는 cmp_priority() 함수를 추가한다 ①
        • thread_yield() 함수 수정 : ready_list를 우선순위로 정렬 하기 위해. list_insert_ordered() 함수에 사용되는 cmp_priority() 함수를 추가한다 ①
        • thread_unblock() 함수 수정 : Thread가 unblock 될때 우선순위 순으로 정렬 되어 ready_list에 삽입되도록 수정 ①
        • thread_yield()함수 수정 : 현재 thread가 CPU를 양보하여 ready_list에 삽입 될 때 우선순위 순서로 정렬되어 삽입 되도록 수정 ①
   2. preemtion (선점) 구현
      • thread_set_priority()함수 수정 : 현재 쓰레드의 우선 순위와 ready_list에서 가장 높은 우선 순위를 비교하여 스케쥴링 하는 함수 호출 ②
        • 슈도코드
          1. cpu 인터럽트 on/off 필요한가? → 포인터로 현재 쓰레드를 받아오는거기 땜에 안해도 될거 같다고 함
          2. 러닝 쓰레드의 우선순위를 새로운 우선순위로 지정
          3. cmp_priority를 쓴다면 a = 러닝 쓰레드의 우선순위, b = 새로운 우선순위
          4. 러닝 쓰레드의 우선순위가 ready_list의 가장 높은 우선순위보다 높다 (return 이 1이다 )
             1. return
          5. 러닝 쓰레드의 우선순위가 더 낮다 → 실행 중지 후 레디 리스트로 넣음
             1. 러닝 쓰레드 yield (이 안에서 do schedule)
      • test_max_priority()함수 추가 : void test_max_priority(void) -> ready_list에서 우선 순위가 가장 높은 쓰레드와 현재 쓰레드의 우선 순위를 비교. 현재 쓰레드의 우선순위가 더 작다면 thread_yield() ②
      • thread_create() 함수 수정 : 새로 추가된 thread가 실행 중인 thread보다 우선순위가 높으면, CPU를 선점하게 한다. thread_create() 함수 수정 : Thread의 unblock 후, 현재 실행중인 thread와 우선순위를 비교하여, 새로 생성된 thread의 우선순위가 높다면 thread_yield()를 통해 CPU를 양보. ②
        • 슈도 코드
          1. thread_unblock
          2. test_max_priority 함수 추가
   3. 동기화 primitive - lock, semaphore, condition variable
      • sema_down 함수 수정
        • Semaphore를 얻고 waiters 리스트 삽입 시, 우선순위대로 삽입되도록 수정
      • sema_up 함수 수정
        • waiter list에 있는 쓰레드의 우선순위가 변경 되었을 경우를 고려하여 waiter list를 정렬 (list_sort)
        • 세마포어 해제 후 priority preemption 기능 추가 -> test_max_priority
      • cond_wait 함수 수정
        • condition variable의 waiters list에 우선순위 순서로 삽입되도록 수정
      • cond_signal 함수 수정
        • condition variable의 waiters list를 우선순위로 재 정렬 - 대기 중에 우선순위가 변경되었을 가능성이 있음
      • cmp_sem_priority 함수 추가
        • 첫번째 인자로 주어진 세마포어를 위해 대기 중인 가장 높은 우선순위의 스레드와 두번째 인자로 주어진 세마포어를 위해 대기 중인 가장 높은 우선순위의 스레드 비교
        • semaphore_elem으로부터 각 semaphore_elem의 쓰레드 디스크립터를 획득.
        • 첫 번째 인자의 우선순위가 두 번째 인자의 우선순위보다 높으면 1을 반환 낮으면 0을 반환
   4. 동기화 이슈 - priority inversion 방지를 위한 Priority donation, Multiple donation, Nested donation 구현
      • lock_acquire 함수 수정: lock을 점유하고 있는 스레드와 요청 하는 스레드의 우선순위를 비교하여 priority donation을 수행하도록 수정
      • lock_release 함수 수정 : donation list 에서 스레드를 제거하고 우선순위를 다시 계산하도록 remove_with_lock(), refresh_prioriy() 함수를 호출
        • lock을 헤제한 후, 현재 쓰레드의 대기 리스트 갱신 (구현하게 될 remove_with_lock() 사용)
        • priority를 donation 받았을 수 있으므로 원래의 priority로 초기화 (구현하게 될 refresh_priority() 사용)
      • thread_set_priority 함수 수정 : 스레드 우선순위 변경시 donation의 발생을 확인 하고 우선순위 변경을 위해 donation_priority()함수 추가
        • refresh_priority() 함수를 사용하여 우선순위의 변경으로 인한 donation 관련 정보를 갱신
        • donate_priority(), test_max_priority() 함수를 적절히 사용하여 priority donation을 수행하고 스케줄링
      • donate_priority() 함수 추가 : Nested donation을 고려하여 구현.
        • 현재 쓰레드가 기다리고 있는 lock과 연결된 모든 쓰레드들을 순회하며 현재 쓰레드의 우선순위를 lock을 보유하고 있는 쓰레드에게 기부, (현재 쓰레드가 기다리고 있는 락의 holder -> holder가 기다리고 있는 lock의 holder)
        • nested depth는 8로 제한
        • 슈도코드
          1. 러닝 쓰레드 불러옴
          2. 러닝 쓰레드가 기다리고 있는 락 선언
          3. 그 락의 홀더 → 홀더의 wait_on_lock
          4. 반복문으로 우선순위 도네이션
      • remove_with_lock 함수 추가 : donation list에서 스레드 엔트리를 제거
        • lock을 해지 했을 때, waiters 리스트에서 해당 엔트리를 삭제 하기 위한 함수를 구현
        • 현재 쓰레드의 waiters 리스트를 확인하여 해지할 lock을 보유하고 있는 엔트 리를 삭제
      • refresh_priority() 함수 추가 : 스레드의 우선순위가 변경 되었을 때, donation을 고려하여 우선순위를 다시 결정하는 함수
        • 현재 쓰레드의 우선순위를 기부 받기 전의 우선순위로 변경
        • 현재 쓰레드의 waiters 리스트에서 가장 높은 우선순위를 현재 쓰레드 의 우선순위와 비교 후 우선순위 설정
      • struct thread 자료 구조 수정 : struct thread에 prioriry donation관련 항목 추가
        • donation 이후 우선순위를 초기화하기 위해 초기 우선순위 값을 저장할 필드(스레드가 두 개 이상의 lock 보유 시, 각 lock에 의해 도네이션이 발생가능 → 이전 상태의 우선순위를 기억하고 있어야 함) → origianl_priority
        • 해당 쓰레드가 대기하고 있는 lock자료구조의 주소를 저장할 필드
        • multiple donation을 고려하기 위한 리스트 추가
          • 해당 리스트를 위한 elem도 추가
      • init_thread() 함수 수정 : Priority donation관련 자료구조 초기화 코드 삽입

6. 테스트 케이스

   • semaphore TC
   • donation TC

쓰레드와 프로세스의 차이 & 쓰레드를 사용하는 이유

참고:

왜?

리눅스는 프로세스 단위로 실행되고, 윈도우 OS는 스레드 단위로 실행된다고 한다.
이는 OS 설계 철학의 차이이며, 무엇이 좋고 나쁘고가 없다고 한다.
각 디자인의 목적이 뭘까? (왜 프로세스 단위 대신 스레드 단위를 사용할까?)

무엇?

스레드와 프로세스는 모두 컴퓨터가 여러 태스크를 동시에 실행할 수 있는 메커니즘이다. 그러나 이들은 여러 가지 면에서 다르다.

1. 생성과 파괴: 일반적으로 새 스레드를 생성하는 것이 새 프로세스를 생성하는 것보다 더 빠르고 더 적은 리소스를 필요로 한다. 반면에, 프로세스를 파괴하는 것은 보통 스레드를 파괴하는 것보다 더 비용이 많이 든다.
2. 메모리 관리: 프로세스에는 별도의 메모리 공간이 있는 반면 스레드는 생성된 프로세스의 메모리 공간을 공유한다. 이는 스레드가 동일한 메모리 위치에 있는 데이터에 더 쉽게 액세스하고 수정할 수 있음을 의미하지만, 한 스레드가 다른 스레드의 메모리를 잠재적으로 방해할 수 있음을 의미하기도 한다.
3. 통신: 프로세스는 일반적으로 스레드보다 서로 통신하는 데 더 어려움을 겪는다. 스레드는 공유 메모리나 다른 메커니즘을 사용하여 동일한 프로세스 내에서 서로 통신할 수 있는 반면 프로세스는 일반적으로 파이프나 소켓과 같은 더 복잡한 통신 메커니즘을 사용해야 한다.
   전반적으로 스레드는 프로그램이 여러 작업을 동시에 수행해야 하고 작업이 리소스를 공유하거나 서로 자주 통신해야 할 때 프로세스보다 일반적으로 선호된다. 프로세스는 일반적으로 태스크가 서로 완전히 독립적이며 리소스를 공유하거나 서로 통신할 필요가 없는 경우에 사용된다.

lock, semaphore, condition variables

참고:

Q. 락, 세마포어, 조건 변수의 차이
락은 동기화 메커니즘으로, 다양한 쓰레드에 의한 공유 자원에 대한 접근을 통제한다. 이는 한번에 한 쓰레드만 자원에 접근할 수 있게 해주며, 그 외 다른 쓰레드가 자원에 접근하려고 하면, 락이 해제될 때까지 block된다.

세마포어는 동기화 메커니즘으로 다양한 쓰레드가 공유 자원에 접근할 수 있게 한다. 하지만 제한된 개수의 쓰레드만 동시에 접근할 수 있다. 세마포어는 쓰레드의 숫자를 나타내는 특정한 값을 가지는데, 이는 동시에 자원에 접근할 수 있는 쓰레드의 개수를 의미한다. 그리고 그 값이 0일 때 자원에 접근하려 하는 쓰레드는 값이 0이 아니게 될 때까지 block된다.

조건 변수는 동기화 메커니즘이다. 조건 변수는 쓰레드로 하여금 특정 조건이 만족될때까지 기다리게 한다. 조건 변수는 보통 락과 연관되어 사용된다. 그리고 쓰레드로 하여금 락을 해제하게 하며, busy waiting 없이 또 다른 쓰레드에 의한 조건 시그널을 받게끔 한다.

락과 세마포어의 가장 중요한 차이는 공유 자원에 대한 접근권을 통제하기 위해 얼마나 세분화되어 있는가의 차이다. 락은 한번에 한 쓰레드만 자원에 접근할 수 있고, 반면 세마포어는 다양한 쓰레드가 동시에 자원에 접근할 수 있게 한다.

또 다른 차이점은 락은 보통 mutual exclusion을 위해 사용된다. 이는 한번에 한 쓰레드만 임계 구역의 코드를 실행할 수 있다는 개념이다. 반면 세마포어는, 다양한 동기화 목적으로 사용될 수 있다. 예를 들어 쓰레드 간의 시그널링이나, resource counting, implementing barriers 같은 것들이 있다.

Q. lock 없이 세마포어만 사용하면 되지 않나?
일반적으로 락 없이 세마포어를 사용하여 여러 스레드에 의한 공유 리소스에 대한 액세스를 동기화할 수 있습니다. 그러나 세마포어를 사용하는 것만으로는 충분하지 않을 수 있으며 프로그램의 올바른 동작을 보장하기 위해 락이 필요할 수 있습니다.

세마포어 외에 락을 사용하는 한 가지 이유는 코드의 중요한 섹션을 한 번에 하나의 스레드만 실행할 수 있는 속성인 상호 배제(mutual exclusion)를 보장하기 위해서이다. 세마포어만으로는 여러 스레드가 동시에 세마포어를 획득하고 임계 섹션을 동시에 실행할 수 있기 때문에 상호 배제를 보장할 수 없다.

세마포어 외에 락을 사용하는 또 다른 이유는 여러 스레드가 공유 데이터에 액세스할 때 발생할 수 있는 경합 조건(race condition)을 방지하기 위해서입니다. 락은 공유 데이터 구조를 동시 액세스 및 수정으로부터 보호할 수 있지만, 세마포어만으로는 이러한 경쟁 조건을 방지하기에 충분하지 않을 수 있다.

요약하면, 세마포어를 단독으로 사용하여 공유 리소스에 대한 액세스를 동기화하는 것이 가능하지만, 세마포어 외에 락을 사용하면 상호 배제 및 경합 조건으로부터의 보호와 같은 추가적인 동기화 보장을 제공할 수 있다.