[SW정글] Week 08 개발일지

 

Week 08 PintOS Threads

1. Alarm Clock

현재 thread를 정해진 시간 후에 다시 시작하는 system call

 

기존에는 Busy waiting 방식

정해진 시간 동안 계속 바쁜 일을 시켜서 기다리게 하는 방식

pintos에서는 정해진 시간이 지나기 전까지 해당 thread가 cpu를 점유할 때마다 yield시켜버리는 방식

→ 다시 ready list로 돌아감

→ 다시 cpu 점유하러 올 수 있음

 

바로 yield되지만 context switching은 계속 일어나기 때문에 자원 낭비

Sleep-Wakeup 방식으로 변경

정해진 시간 동안 해당 thread를 block시켜서(sleep) ready list에 못오게 하는 방식

sleep thread는 sleep list로 관리

timer interrupt할 때 sleep list를 순회해서 정해진 시간이 지난 thread가 있는지 확인한 후에 있으면 unblock하는(wake up) 방식

 

Thread 4가지 상태

ready

• double linked list로 관리ready list의 가장 앞의 thread가 다음 cpu를 점유하게 된다
• thread의 priority에 의해 정렬될 수도 있다
• CPU만 점유한다면 일할 준비가 된 threads

running

• 싱글 코어 CPU라고 할 때 running thread는 1개만 있다
• 현재 CPU를 점유하고 일하고 있는 thread

blocked

• read list에 없다특정 event에 의해 unblock될 수 있다
• lock, semaphore, condition variable 등으로 인해 다른 thread가 선점한 resource를 필요로 하는 경우나 thread가 cpu 점유하는 것을 막기 위해 의도적으로 block한 경우 등의 이유
• CPU 점유와는 다른 이유로 일을 할 수 없는 threads

dying

• 없앨 thread를 일단 list로 관리한다
• scheduling을 할 때마다 dying list 안의 thread를 삭제한다
• 없어질 thread

 

2. Priority Scheduling

2.1 Priority Scheduling

ready list를 thread의 priority 값으로 정렬해서 관리

 

기존에는 Round Robin 방식

모든 thread는 공평하게 정해진 시간(4ticks)동안만 cpu를 점유한다

yield된 thread는 read list 마지막으로 간다

priority scheduling으로 변경

ready list에 추가된 thread의 priority가 running thread의 priority보다 높을 경우 cpu를 선점한다

→ ready thread와 running thread 중에서 priority가 가장 높은 thread가 cpu를 점유한다

2.2 Synchronization

semaphore 등을 활용한 resource waiter list를 priority 값으로 정렬해서 관리

 

기존에는 resource를 요청한 순서대로 resource를 할당한다

priority가 높은 thread가 priority가 낮은 thread를 계속 기다리는 상황이 생긴다

resource waiter list를 priority로 정렬하도록 변경

기다리는 thread 중에서 priority가 가장 높은 thread가 다음으로 resource를 할당 받는다

2.3 Priority Inversion Problem

priority donation 방식으로 priority inversion 문제를 해결

• priority inversion
• resource wait 때문에 priority가 높은 thread가 priority가 낮은 thread를 기다리는 문제
• priority donation
  • multiple donationthread는 자신이 가진 lock들을 기다리는 thread들을 donations list로 관리한다
  • lock을 가진 thread는 자신의 donations list 안의 thread 중 가장 높은 priority를 donation 받는다
  • 한 thread가 여러 lock을 가지고 있는 경우 각각의 lock을 원하는 thread들에 의해 donation을 여러 번 받는 경우
  • nested donationlock 안에 현재 lock을 가진 holder를 따로 저장하고 thread는 자신이 lock을 기다리면 기다리는 lock을 내부에 저장한다(wait_on_lock) → wait_on_lock과 holder를 따라 올라가면서 lock을 기다리는 모든 thread에 자신의 priority를 donation한다
  • lock A을 가진 thread가 lock B을 기다리고 있을 때 높은 priority를 가진 thread가 lock A를 요청할 때 lock A를 가진 thread 뿐만 아니라 그 thread가 기다리는 lock B를 가진 thread에게도 priority를 donation 해주는 경우
• resource wait를 하는 thread A가 resource를 가지고 있는 thread B보다 priority가 높으면 resource를 반납하기 전까지 B가 A의 priority를 받는 방식

3. Multi-Level Feedback Queue Scheduler