Time-sharing system
- Context Switching
- Scheduler
- Round Robin (RR)
- Priority
- Priority donation
- Multi-Level Feedback Queue Scheduler (MLFQS)
- 4BSD
- nice
- Thread
- Thread control block (TCB)
Timer Interrupt
Timer sleep
Synchronization
- Semaphore
- lock
- condvar
이 키워드들은 노션에서 참고할 것 - 다른 기수분 정리 노션
project 1 흐름
Alarm Clock
기존에 사용하던 방식인 busy-waiting은 효율성이 현저히 떨어져서 sleep-wakeup 방식으로 교체 해준다.
busy-waiting과 sleep-wakeup 관련 이론 보러가기
- sleep-wakeup 방식
timer_sleep() -> thread_sleep() -> timer_interrupt() -> thread_wakeup()
Priority Scheduling
현재 실행되고 있는 스레드는 우선순위가 높은 스레드가 ready_list에 추가 되면 즉시 멈추고 프로세서를 새로운 스레드에 양보해야 한다. 이 때 기다리고 있는 스레드가 무한 대기 상태가 될 수 있으므로 이는
priority donation을 통해 문제를 해결한다.
이 프로젝트에서 적용되는 개념이 lock과 semaphore이다.
자세한 개념을 알고 싶다면 lock과 semaphore 개념 정리 보러가기로 이동하자
priority 관련 변수 추가 및 함수 구현
synch.c에 구현된 lock 등에서 priority 반영
priority donation 관련 함수 구현
1. 쓰레드 생성 후 ready_list에서 우선순위 정렬
thread_create()->thread_set_priority()->refresh_priority()->test_max_priority()->cmp_priority()->thread_yield()
-
thread_create()
스레드가 실행 되면 "kernel_thread" 함수에서 실행되며, 필요한 인자들은 레지스터에 rdi,rsi에 저장되고 세그먼트 선택지를 설정하여 스레드의 코드, 데이터, 스택 영역을 지정한다. 특히 eflag에는 인터럽트 플래그를 받을 수 있게 함 -
thread_set_priority()
thread의 우선순위를 설정하는 함수로 테스트 코드에서 new_priority를 주면 현재 스레드 priority를 변경한다.
2-1.refresh_priority()
빈 donation_list가 아니면 우선순위를 정렬
2-2.test_max_priority()
인터럽트가 실행중이지 않고cmp_priority()의 값이 1일때thread_yield()실행
2-2-1.cmp_priority()
현재 수행중인 스레드와 ready_list에서 가장 높은 우선순위의 스레드 비교, 이때 bool타입으로 1 또는 0 값으로 return 해줌 -
thread_yield()
현재 실행시킬 스레드가 외부 인터럽트가 수행이지 않을 때 실행
만약 현재 스레드가 처음 스레드가 아닐 경우 ready_list와 현재 실행시킬 스레드의 우선순위를 비교해서 list에 정렬한다.
그 후 인터럽트 level을 인터럽트 disable로 설정한다.
2. lock 적용(lock_acquire)
lock_acquire->donate_priority()->sema_down()->cmp_priority()
lock_acquire
lock_acquire이 실행되었다는 것은 이미 lock을 가지고 있는 thread의 우선순위보다 높다는 의미
이때 priority donation이 실행되는데 만약 lock을 다른 스레드가 사용하고 있을 때 현재 스레드의 wait_on_lock에 lock을 저장하고 donations_list에 현재 스레드를 저장하고 우선순위 기부 함수를 실행(donate_priority())
이때 donations_list는 현재 스레드의 기부를 기록하는 리스트
2.donate_priority()
현재 스레드가 기다리는 동안 잠근 lock의 홀더 스레드에게 우선순위를 기부하여 우선순위 기부 체인을 형성하는 역할
cur->wait_on_lock->holder를 사용하여 현재 스레드가 기다리는 lock의 홀더 스레드를 가져옵니다. 그리고 holder의 우선순위를 현재 스레드의 우선순위로 설정하여 기부
sema_down()
세마포어(semaphore)의 값을 양수가 될 때까지 기다린 후 원자적으로 값을 감소시킴
여기서 리스트 정렬을 함
3-1.cmp_priority()
현재 수행중인 스레드와 ready_list에서 가장 높은 우선순위의 스레드 비교, 이때 bool타입으로 1 또는 0 값으로 return 해줌
3. lock 해제 (lock_release)
remove_with_lock()->refresh_priority()->sema_up()->
1.remove_with_lock()
donation_list에서 현재 priority를 가진 thread를 제거
2.refresh_priority()
빈 donation_list가 아니면 우선순위를 정렬
3.sema_up()
세마포어의 v연산, semaphore를 반환한뒤 value 값을 1 올림
4.test_max_priority()
인터럽트가 실행중이지 않고 cmp_priority()의 값이 1일때 thread_yield() 실행
