버전 선택

• 우분투 18.04 사용 -> VS코드 1.98으로 다운그레이드해야 함 (25년 2월)
  • 우분투 18.04는 glibc 2.28 이하 미만 버전을 사용하는데, v1.99부터 지원하지 않음
• 우분투 22.04 사용 -> 아무 문제 없지만 호환성문제 발생할 수 있음
• 보다 안정적인 18.04 버전을 사용하려고 했으나, VS코드가 강제로 업데이트되는 문제 때문에 결국 22.04를 사용하게 됨.

Project1: Threads

• 이미 구현된 부분
  • 쓰레드 생성 및 종료하기
  • 쓰레드 간 전환을 위한 간단한 스케줄러
  • 세마포어, 락, 모니터, optimization barrier 등 동기화 기법
• 쓰레드 생성 시 thread_create()에 인자로 전달된 함수는, 쓰레드가 처음 실행된 지점부터 실행됨
  • 해당 함수가 반횐되면 쓰레드가 종료됨
  • 즉 각 쓰레드는 독립적인 프로그램으로, 쓰레드 함수는 main()으로 생각하면 편함
• 매번 한 개의 쓰레드만 실행됨
  • 스케줄러는 다음에 어떤 쓰레드를 실행할지 결정
  • Ready 상태의 쓰레드가 없는 경우, idle이 실행됨
• 동기화 함수 내 한 쓰레드가 다른 쓰레드를 기다리는 경우, 쓰레드 간 context switching 발생
  • 현재 쓰레드의 state를 저장
  • 전환이 이루어지는 쓰레드의 state를 복원

동기화 문제?

• (1) 인터럽트를 종료한다
  • 동시성이 존재할 수 없음. race condition도 없음
  • 하지만 커널 쓰레드와 인터럽트 핸들러가 공유하는 데이터를 동기화할 때만, 이 방법으로 해결하자.
    • 인터럽트 핸들러는 sleep하지 못함 -> lock을 얻지 못함
    • cf. sleep: 쓰레드의 실행을 임시 중단하고, 대기 큐에 넣는 동작. 하지만 인터럽트 핸들러는 쓰레드가 아님.
    • 세마포어, 락은 다른 쓰레드가 점유 시 현재 쓰레드를 block(=sleep)시켜 대기하게 만듦. 하지만 여기선 sleep할 수 없음.
• (2) 세마포어, 락, 조건변수를 사용한다
  • 일반적으론 이게 맞지. threads/synch.c 참고하기.

Alarm Clock

• devices/timer.c의 timer_sleep() 함수를 개선하라.

  • void timer_sleep (int64_t ticks);
  • ticks번 timer tick이 발생할 때까지 현재 쓰레드의 실행을 중단한다.
  • 무조건 ticks번 timer tick이 발생한 직후에 깨울 필요는 없다.

• 현재의 함수는 busy wait

  • 지난 시간 확인하고, 충분히 지나기 전까지 thread_yield() 실행.
  • (void) thread_yield (void): 스케줄러가 새롭게 실행할 쓰레드를 선택. 단, 현재 쓰레드일 수도 있음. 즉 특정 쓰레드 실행을 일정시간 막는 용도로 사용 불가
  • 1초엔 TIMER_FREQ = 100(devices/timer.h)번 틱이 발생함.

• 인터럽트를 종료해야 할 수도 있음.

  • 타이머 인터럽트가 sleep 중인 쓰레드를 깨워야 함
  • 이때 인터럽트 핸들러는, sleep queue 같은 공유 데이터를 건드릴 수 있음
  • sleep queue에 접근하는 커널 쓰레드 코드에선, 인터럽트를 꺼야 함.

• timer interrupt는 1초에 100번 발생.

• time slice에선 4번의 tick(timer interrupt가 1번 발생한 순간) 발생.

  • time slice는 하나의 프로세스가 CPU를 사용할 수 있는 시간.
  • 100Hz 시스템인 경우, 40ms (1000ms가 1초) 동안 한 쓰레드가 사용된다는 점...

타이머, 타이머 인터럽트

• 프로세스가 시스템 콜을 호출하지 않아도, 하드웨어의 도움으로 제어권을 운영체제로 넘길 수 있음
• 타이머 인터럽트
  • 타이머: 정해진 시간간격(약 10ms)마다 인터럽트(전기적 신호)를 발생시키는 하드웨어 장치
  • 인터럽트 1회 = 1틱 이라고 함.
  • 인터럽트 발생 시, CPU는 수행 중인 프로세스를 잠시 멈추고, CPU 제어권이 운영체제로 넘어감
  • 이후 타이머 인터럽트 핸들러가 실행됨
    • 시간할당이 끝난 프로세스 중단, 스케줄러 호출을 통핸 문맥 전환 등 담당

질문

• busy waiting을 어떻게 해결해야 해??
  • semaphore 같은걸로? mutex?
• sleep queue는 직접 만들어야 하나??
  • Linked List 있음
• 시그널 함수 같은 거 써야 하나??

Priority Scheduling

• 176줄 주목! The code provided sets the new thread's `priority' member to
  PRIORITY, but no actual priority scheduling is implemented.
• 현재 thread보다 더 priority가 높은 thread가 ready list에 들어온 경우
  • 새 쓰레드에게 바로 CPU를 넘김
• 현재 thread가 lock, semaphore, condition variable을 기다리고 있는 경우
  • priority가 가장 높은 waiting thread를 제일 먼저 깨워야 함
• thread 조정은 가능하지만...
  • 조정 후 더 이상 제일 높은 priority가 아닌 경우, 바로 yield해야 함
• QNA: 제일 높은 우선순위인 thread가 thread_yield하는 경우? -> block / finish 전까진 계속 실행. 여러 쓰레드의 priority가 동일하면 round robin order로 바꾸기.

thread priorities

• PRI_MIN(0) 부터 PRI_MAX(63)
  • default는 PRI_DEFAULT(31)
  • threads/threads.h 확인!

priority donation

• Priority Inversion
  • H, M, L 순으로 쓰레드 우선순위가 높음
  • H가 L을 기다리고 있고 (e.g., L이 잠금한 락) M이 ready list에 있을 때
  • H는 절대로 실행되지 않을걸? L이 CPU타임을 갖지 않음
  • (M이 CPU를 오래 쓰는 작업일 수도 있으니까?)
• Priority Donation
  • H -> L에게 priority를 donate하기
  • L이 lock을 release하고 H가 lock을 acquire했을 때 회수
  • LOCK 에만 Priority Donation 구현하면 됨
  • QNA 3: 블로킹된 쓰레드의 priority도 증가할 수 있음.
  • 기부받은 쓰레드의 priority가, 기부한 쓰레드의 priority로 바뀌는 식!!
  • priority 5를 가진 A가 priority 3를 가진 B에 기부하면, B의 새 priority는 5. 8이 아님.
  • ready queue / block된 thread의 priority도 바꿀 수 있음.

함수들

• void thread_set_priority (int new_priority)
  • 현재 쓰레드의 priority를 new_priority로 수정
  • 단, 현재 쓰레드가 더 이상 제일 높은 priority를 갖지 않은 경우, 제일 높은 애한테 양보해야 함
• int thread_get_priority(void)
  • 현재 쓰레드의 priority를 반환.
  • priority donation 이루어진 경우, 높은 priority를 반환해야 함

질문들

• ready list가 뭐임? run queue는 또 뭐임? -> 코드를 분석해야 한다
  • 놀랍게도 둘이 똑같은 뜻. THREAD_READY state에 있는 애들이 담긴 연결리스트임. 우리 코드에선 ready_list 변수에 있네.
• priority scheduling 하려면 뭘 수정해야 하는 건데?
• 그래서 priority donation 어떻게 해야 하는 건데?
• 두 함수 말고 또 뭘 수정해야 하는 건데?

Q&A

• 모범답안에서 수정한 코드들?

devices/timer.c               |  29 +++++++++++++++++++++++++++++
include/threads/fixed-point.h |  10 ++++++++++
include/threads/synch.h       |   4 ++++
include/threads/thread.h      |  21 +++++++++++++++++++++
threads/synch.c               | 143 +++++++++++++++++++++++++++++++++++++++++++-
threads/thread.c              | 135 ++++++++++++++++++++++++++++++++++++++++----

• lock이 해제된 후에 어떤 쓰레드가 실행되어야 하지?
  • 해당 lock을 기다리는 highest priority thread를, list of ready threads에 넣기
  • 그 다음에 제일 높은 thread 시동 걸기

통과해야 하는 테스트들?

• alarm-priority: timer_sleep한 쓰레드을 alarm clock으로 깨울 때, 높은 priority의 쓰레드를 먼저 깨워라!-
• priority-fifo: 동일 priority의 여러 thread를 만들면, round-robin order로 실행되게끔 해라!
• priority-preempt: 더 높은 priority의 thread가 만들어지면 선점하게 하라!
• priority-sema: 세마포어에서 blocking된 thread 중에선 highest priority가 먼저 깨게 하라!
• priority-condvar: 조건 변수로 blocking된 thread 중에선 highest priority가 먼저 깨게 하라!
• donate류, mlfqs류는 나중에 해보자...