08:24 입실
Donation 개념 정리 및 코드 이해
MLFQ 구현 시도!
PintOS
Donation
Nested Donation
A가 B에서 우선 기부하고, B가 C에게 기부하는 경우
You
중첩 기부는 우선순위가 전파된다고 표현해도 돼?
ChatGPT
네, "중첩 기부"를 우선순위가 전파된다고 표현하는 것은 적절합니다. 이 개념은 우선순위 스케줄링 시스템에서 고우선순위 스레드의 우선순위가 다른 스레드에게 전파되는 메커니즘을 설명합니다. 이러한 우선순위의 전파는 다음과 같은 상황에서 발생합니다:
우선순위 전파: 고우선순위 스레드가 저우선순위 스레드가 점유하고 있는 자원을 기다릴 때, 이 저우선순위 스레드는 고우선순위 스레드로부터 우선순위를 '기부' 받게 됩니다. 이 과정에서 우선순위는 고우선순위 스레드로부터 저우선순위 스레드로 전파됩니다.
중첩 상황: 이 전파는 스레드 간의 의존성이 복잡하게 얽혀 있는 경우 여러 단계에 걸쳐 이루어질 수 있습니다. 즉, 하나의 스레드가 다른 스레드에게 우선순위를 기부하고, 그 스레드가 또 다른 스레드에게 우선순위를 전파하는 것입니다.
자원 점유 해제 후 우선순위 복원: 자원을 점유하고 있던 스레드가 그 자원을 해제하면, 그 스레드의 우선순위는 원래대로 복원됩니다. 이는 전파된 우선순위가 일시적인 것임을 의미합니다.
중첩 기부는 우선순위 역전 문제를 방지하고, 운영 체제에서 자원을 보다 공정하고 효율적으로 관리하는 데 도움을 주는 중요한 기법입니다.
Multiple Donation
한 스레드가 여러 스레드로부터 우선순위를 기부 받는 상황
이때 기부 받은 우선순위 중 가장 높은 우선순위를 반영하여 상승
이것도 멀티플?
구조체 관계가 잘 그려진 그림!
이 그림에서 조금 헷갈렸던 점이 세마포어 안의 waiters는 사실상 1개의 스레드만 들어갈 수 있는 상황이다. 스레드가 리스트 형태로 들어갈 수 있다고 착각해서 고민했음! 그래서 아래처럼 바꿔 봄!
모니터 + 구조체 관계도
어제 엉망으로 그린 거 수정함!
세마포어의 웨이터스에 하나의 스레드만 들어갈 수 있는지는 검증 필요!
테스트 코드 살펴보기
msg()는 삭제
우선순위 기본값 31 가정
priority-donate-one
우선순위 도네이션
void
test_priority_donate_one (void)
{
struct lock lock;
ASSERT (!thread_mlfqs);
ASSERT (thread_get_priority () == PRI_DEFAULT);
lock_init (&lock);
lock_acquire (&lock);
thread_create ("acquire1", PRI_DEFAULT + 1, acquire1_thread_func, &lock);
thread_create ("acquire2", PRI_DEFAULT + 2, acquire2_thread_func, &lock);
lock_release (&lock);
}- 락을 초기화한다.
- 메인 스레드가 락을 취득한다.
- 우선순위를 31+1로 스레드1을 생성한다.
락을 취득하려고 하지만 불가능하다. - 우선순위를 31+2로 스레드2를 생성한다.
락을 취득하려고 하지만 불가능하다. - 메인 스레드의 우선 순위를 스레드2의 31+2로 끌어 올린다. 메인 스레드가 락이 필요할 동안 처리 후 락을 해제하고 우선순위가 원래 낮은 상태로 돌아간다.
- 스레드2가 락을 취득 후 실행 완료 후 락을 해제한다.
- 스레드1이 락을 취득 후 실행 완료 후 락을 해제한다.
- 메인 스레드는 나머지를 실행 완료한다.
- 현재 락을 보유한 스레드가 락을 해제한다.
priority-donate-multiple
멀티플 도네이션
priority-donate-multiple2
멀티플 도네이션2
priority-donate-nest
중첩 도네이션
priority-donate-sema
세마포어로 도네이션
priority-donate-lower
priority-fifo
선입선출 우선순위
priority-preempt
priority-sema
세마포어 우선순위
priority-condvar
priority-donate-chain
교착상태
자원 할당 그래프
이런 개념이 있었다!
노드: 활성 프로세스, 락(자원)
간선: 요청 간선(p->r), 할당 간선(r->p)
비슷하게 대기 그래프도 있음!
자원이란?
자원이랑 프로세서나 메모리만 의미하는 게 아니다.
프린터와 같은 하드웨어, 파일 등도 모두 자원이라고 할 수 있다.
은행원 알고리즘
한정된 돈을 모든 고객이 만족하게 나누어 주는 것
만약 돈이 부족하면, 먼저 돈을 모두 줄 수 있는 고객에게 돈을 주고, 그 다음에 회수가 되면 다른 고객에게 요청한 전체 돈을 빌려주는 것
여기서 돈을 자원이라고 생각하면 됨.
탐지 알고리즘
교착 상태 방지 목적이 아니다.
교착 상태를 그냥 허용한다.
대신 교착 상태인지를 탐지할 수는 있어야 함.
얼마나 할당해야 하는지 체크 안 함.
어떤 프로세스가 어떤 자원을 점유하고 있는지, 또 다른 어떤 자원을 기다리고 있는지를 파악하여 교착 상태의 존재 여부를 확인
은행원, 탐지 알고리즘은 개념만 대충 알고 자세한 구현 방법은 모르겠음. 이건 추후 다시 공부하기!
타조 알고리즘
그냥 교착 상태 아예 처리 안 함.
교착이 발생하면 시스템 재부팅 등으로 처리
