나한나한나한나

Main goal

• FIFO scheduling을 priority scheduling으로 수정할 것
  • ready list를 thread priority로 정렬
  • wait list 정렬 - synchronization primitives로
  • 선점 구현
    • 선점은 운영 체제가 현재 실행 중인 태스크(프로세스 또는 스레드)를 일시 중단하고, 더 높은 우선순위의 태스크에 CPU 사용권을 넘겨주는 과정입니다. 이는 시스템이 더 긴급하거나 중요한 작업을 빠르게 처리할 수 있도록 해줍니다.
    • 선점 구현 방법
      1. 타이머 인터럽트 사용: 대부분의 현대 운영 체제는 타이머 인터럽트를 사용하여 정기적으로 현재 실행 중인 태스크의 상태를 확인합니다. 타이머 인터럽트가 발생하면, 운영 체제는 CPU를 점유하고 있는 태스크를 중단시킬 수 있는지 결정합니다.
      2. 우선순위 체크: 운영 체제는 실행 대기 중인 태스크들의 우선순위를 검토합니다. 현재 실행 중인 태스크보다 높은 우선순위를 가진 태스크가 있으면, 운영 체제는 현재 태스크를 중단하고 더 높은 우선순위의 태스크에 CPU를 할당합니다.
      3. 컨텍스트 스위치: 선점이 결정되면, 운영 체제는 컨텍스트 스위치를 수행합니다. 이는 현재 태스크의 상태(컨텍스트)를 저장하고, 새로 실행할 태스크의 컨텍스트를 복원하는 과정을 포함합니다.
      4. 자원 관리: 선점이 일어나면, 운영 체제는 필요한 자원(메모리, 입출력 장치 등)을 새로운 태스크에 재할당해야 할 수도 있습니다. 이는 자원의 효율적 관리와 빠른 접근을 보장하기 위해 필요합니다.
  • 선점 지점preemption point : 쓰레드가 ready list에 포함될 때(타이머 인터럽트가 호출될 때마다가 아님)
• Files to modify
  • threads/thread.*
  • threads/synch.*

 

고려해야 할 세 가지

• ready list에서 run할 쓰레드를 고를 때, 가장 우선순위가 높은 것을 골라야 함
• 선점preemption
  • 뉴 쓰레드를 ready list에 삽입할 때, running 쓰레드와 우선순위를 비교해야 함
  • 새로 삽입된 쓰레드가 currently running 쓰레드보다 우선순위가 높다면 스케줄링 수행
• 락: 세마포어, 조건변수
  • 락(또는 조건 변수)을 기다리는 쓰레드 집합에서 쓰레드를 선택할 때, 가장 높은 우선순위를 가진 스레드를 선택하라

 

우선순위 in pintos

• Priority ranges from PRI_MIN (=0) to PRI_MAX (=63).
  • 숫자가 높을 수록 우선순위가 높음
  • Default is PRI_DEFAULT (=31)
• 핀토스는 thread_create()에 의해 생성될 때 초기 우선순위를 설정한다
• Existing functions
  • void thread_set_priority (int new_priority)
    • 현재 쓰레드의 우선순위를 new_priority로 변경하라
  • int thread_get_priority (void)
    • 현재 쓰레드의 우선순위를 리턴하라

 

Implementation of Priority Scheduling

tie_t thread_create(const char *name, int priority, thread_func *function, void *aux)

• 업데이트 포인트
  • 우선순위 순서대로 준비 목록에 쓰레드를 삽입하라. (확장성이 없다는 점을 유의하라)
  • 스레드가 준비 목록에 추가될 때, 새 스레드의 우선순위와 현재 스레드의 우선순위를 비교하라.
  • 새 스레드의 우선순위가 더 높다면 schedule()을 호출하라(현재 스레드가 CPU를 양보함)
• pintos/threads/thread.c

tid_t thread_create (const char *name, int priority, thread_func *function, void *aux)
{
	...
    thread_unblock (t);
    
    /* 
    compare the priorities of the currently running thread and the newly inserted one.
    Yield the CPU if the newly arriving thread has higher priority    
    */
    
    return tid;
}

 

 

Others to modify

void thread_unblock(struct thread *t)
	// when the thread is unblocked, it is inserted to ready_list in the priority order
void thread_yield(void)
	// The current thread yields CPU and it is inserted to ready_list in priority order
void thread_set_priority(int new_priority)
	// set priority of the current thread
	// reorder the ready_list

 

Hint: thread_unblock

• When unblocking a thread, use list_insert_ordered instead of list_push_back
• pintos/threads/thread.c

void thread_unblock (struct thread *t)
{
	...
    // list_push_back (&ready_list, &t->elem); --> delete
    
    list_insert_ordered(&ready_list, &t->elem, cmp_priority, NULL); // --> add
    
    t->status = THREAD_READY;
    intr_set_level (old_level);
}

 

 

우선순위는 무시하고 FIFO mechanism으로 작동하는 pintos

B D C 순으로 lock을 얻음 (request 먼저 한 순서대로)

 

우선순위 기반 락/언락 매커니즘

D C B 순으로 lock을 얻음 (priority 순서대로)

 

Semahpore in pintos

• sema_init()
  • 세마포어 초기화
• sema_down()
  • 세마포어 요청
  • If it acquired the semaphore, value를 1만큼 감소
• sema_up()
  • semaphore를 release하고 value를 1만큼 증가
  • semahpore를 release한다는 게 뭔 말?
    • "세마포어를 release(릴리스)한다"는 말은 멀티스레드 프로그래밍에서 세마포어의 값(리소스의 수를 나타냄)을 증가시켜서, 다른 스레드들이 해당 리소스를 사용할 수 있도록 만드는 작업을 의미합니다. 세마포어는 주로 리소스 접근을 제한하는 데 사용되며, 리소스를 안전하게 공유할 수 있도록 돕습니다.
      
      스레드가 리소스 작업을 마치고 나서 세마포어를 릴리스하면, 세마포어의 카운트가 증가합니다. 이렇게 카운트가 증가함으로써, 대기 중인 다른 스레드들 중 하나가 리소스를 얻을 수 있는 기회를 가지게 되고, 그 스레드는 세마포어를 'acquire(획득)'하여 리소스에 접근하게 됩니다.

 

조건변수 in pintos

• cond_init()
  • CV data structure 초기화
• cond_wait()
  • CV에 의한 시그널을 기다림
• cond_signal()
  • 우선순위가 가장 높은 쓰레드에게 시그널을 보냄, CV에서 기다리는 쓰레드 중에 
• cond_broadcast()
  • 모든 쓰레드에게 시그널을 보냄, CV에서 기다리는 쓰레드 중에 

 

Priority Inversion

생략!

 

Priority Donation

 

Nested Donation

 

Multiple Donation

 

Data Structure for Multiple Donation

 

Data Structure for Nested Donation

 

Implementation of Priority Donation

• init_thread(*쓰레드, *쓰레드 이름, 우선순위)
  • priority donation을 위한 data structure 초기화
• lock_acquire(*락)
  • 락이 불가능하면, 락의 주소를 저장(사용가능할 때까지 대기하기 위해)
  • 현재 우선순위를 저장하고 이 스레드에게 우선순위를 기부 받은 스레드들을 리스트에서 관리(?)
  • 우선순위 기부
• lock_release(*락)
  • 락이 릴리즈될때, donation list에서 락을 hold한 스레드를 제거하고 우선순위를 다시 set
• thread_set_priority(new 우선순위)
  • donation을 고려한 우선순위 set

 

결과

 

 

backtrace 하는법

https://web.stanford.edu/class/cs140/projects/pintos/pintos_10.html

Pintos Projects: Debugging Tools

스탠포드 대학교에서 알려주는 디버깅 도구들..중에 backtrace항목을 보았는데, 봐도 뭔 소린지 잘 모르겠다.

 

커널이 패닉 상태가 되면, "백트레이스"를 출력합니다. 즉, 패닉 시점에 실행 중이었던 함수 내의 주소 목록을 요약하여 프로그램이 어떻게 현재 상태에 이르렀는지 보여줍니다. 코드 내의 어떤 지점에서든 debug_backtrace() 함수를 호출하여 백트레이스를 출력할 수 있으며, 이 함수는 <debug.h>에 프로토타입으로 선언되어 있습니다. 또한 <debug.h>에 선언된 debug_backtrace_all() 함수는 모든 스레드의 백트레이스를 출력합니다.

백트레이스의 주소는 원시 16진수 숫자로 나열되며, 이는 해석하기 어렵습니다. 우리는 이러한 주소를 함수 이름과 소스 파일 줄 번호로 변환해주는 backtrace 도구를 제공합니다. 첫 번째 인수로 kernel.o의 이름과 백트레이스를 구성하는 16진수 숫자들(0x 접두사 포함)을 나머지 인수로 입력하면 각 주소에 해당하는 함수 이름과 소스 파일 줄 번호를 출력합니다.

백트레이스의 번역된 형태가 엉망이거나 말이 되지 않는 경우(예를 들어, 함수 A가 함수 B 위에 나열되어 있지만 B가 A를 호출하지 않는 경우), 커널 스레드의 스택이 손상되었다는 좋은 징후입니다. 왜냐하면 백트레이스는 스택에서 추출되기 때문입니다. 또 다른 가능성은 backtrace에 전달한 kernel.o가 백트레이스를 생성한 커널과 동일하지 않을 수 있기 때문입니다.

컴파일러 최적화로 인해 때때로 백트레이스가 혼란스러울 수 있습니다. 함수가 마지막 행동으로 다른 함수를 호출하는 경우(테일 콜), 호출 함수는 백트레이스에 전혀 나타나지 않을 수 있습니다. 마찬가지로 함수 A가 반환하지 않는 함수 B를 호출할 때, 컴파일러는 관련 없는 함수 C가 A 대신 백트레이스에 나타나도록 최적화할 수 있습니다. 함수 C는 단순히 메모리상에서 A 바로 뒤에 있는 함수입니다. 스레드 프로젝트에서 이는 일반적으로 테스트 실패에 대한 백트레이스에서 볼 수 있습니다.