핀토스는 FIFO scheduling 사용

목표

핀토스 스케줄링을 우선순위 스케줄링으로 바꾸자

• ready list를 스레드 우선 순위에 따라 정렬
• wait list를 정렬
  사용하는 동기화 기법들(락, 세마포어, 조건 변수)을 우선순위 기반으로 동작하도록 -> 우선순위가 높은 스래드를 먼저 깨우자
• Implement preemption (CPU를 스레드가 독점하지 못하도록 중간에 뺏는 기능)
  preemption point: 스레드가 준비 리스트에 들어갈때(타임 인터럽트가 발생할때 마다 안해도된다)

wait list: lock을 요청했지만 아직 획득하지 못한 스레드를 포함

우선순위 가진 스레드 실행

1. 레디리스트에 실행될 스레드를 선택할 때 가장 높은 우선순위를 가진 스레드를 고른다
2. • 새로운 스레드를 준비리스트에 넣을 때 실행중인 스레드와 우선 순위 비교
   • 현재 실행중인 스레드보다 높은 우선순위를 가지고 있다면 새롭게 삽입된 스레드를 스케줄
3. lock: semaphore, condition variable

priority in pintos

• priotity 범위 PriMin(=0) to PreMax(=63)
  (default: Pre_default(=31))
• thread_create() 로 스레드 생성될 때마다 핀토스는 초기 우선순위를 정한다)

함수

void thread_set_priority(int new_priority)
현재 스레드의 우선순위를 새로운 우선순위로 변경한다

int thread_get_priority(void)
현재 스레드 우선순위 반환

뭐 해야함?

• 우선순위대로 레디리스트에 삽입
• 레디리스트에 추가 되었으면 새스래드 우선순위와 현재 스래드 우선 순위 비교
• 새 스래드 우선순위가 높다면, schedule() 호출 (현재 스래드가 cpu를 양보한다)

in thread_create.c

현재 실행중인 스래드 우선순위와 새 스래드 우선순위 비교
들어온 스래드가 더 높은 우선순위를 갖고 있다면 CPU양보

void thread unblock()

• 잠들어있던 스레드를 깨우는 함수
  if thread is unblocked, 우선순위로 ready list 삽입

void thread yield(void)

현재 스래드가 cpu양보하고 우선순위에 따라 ready list 삽입

함수 이름	어떤 스레드를	언제	어디에 삽입?
thread_unblock(t)	잠자고 있던 스레드 t	외부에서 깨어날 때 (예: sema_up)	ready list (우선순위 정렬)
thread_yield()	현재 실행 중인 스레드	스스로 CPU를 양보할 때	ready list (우선순위 정렬

void thread set priority(int new priority)

현재 스래드 우선순위 set, reorder ready list

thread unblock 할때 push back 대신 list_insert_order() 사용

void thread_unblock(struct thread *t){
	...//delete push back code
    list_insert_ordered(&ready list, &t->elem, cmp_priority,NULL)
    t-> status=THREAD_READY;
    intr_set_level(old level)
}

---

# change the synchronization primitives -lock, semaphore, condition variables

기존 방식:
• sema_up() 또는 lock_release()에서 대기 중인 스레드 중 가장 먼저 기다린 애를 깨움

수정해야 할 방식:
• 대기 중인 스레드들 중에서 priority가 가장 높은 애를 깨워야 함

cf) Lock (락)
• “혼자 쓰기”를 보장하는 자물쇠
• 하나의 스레드만 공유 자원(CPU, 변수, 파일 등)을 사용할 수 있게 막아주는 도구

cf) Semaphore (세마포어)

• 카운터가 있는 락
• 동시에 여러 개가 들어갈 수 있는 자원 (ex. 좌석 3개짜리 방)에 대해 몇 개나 남았는지를 추적해줘.

  주차장에 총 3자리가 있어.
  차가 들어올 때마다 세마포어는 1씩 줄어들고, 나가면 다시 1씩 늘어나.
  만약 세마포어 값이 0이면, 기다려야 해(sema_down).
  자리가 생기면 세마포어를 올려주고(sema_up) 기다리는 차를 깨우는 거야.

cf) Condition Variable (조건 변수)
특정 조건이 충족될 때까지 기다리게 해주는 도구
락과 함께 사용
“지금은 자원이 준비 안 됐으니, 다른 누군가가 알려줄 때까지 잠깐 자라”고 할 때 써.
스레드는 조건이 충족될 때까지 조건 변수에 wait() 하고 자.
충족되면 다른 스레드가 signal() 해서 깨움

semaphore

세마포어 값이 0이면 기다림
값이 증가할때 sema_up()이 호출되어 기다리던 스레드 깨움

• modify
  sema_down() : list_insert_ordered
  sema_up() : 우선순위 높은 스레드 깨우고 필요하면 cpu 양보

condition variable

• modify
  cond_wait() : 우선순위대로 삽입
  cond_signal() : 우선순위 가장 높은 스래드 깨움

우선순위가 없을때

D가 우선순위가 가장 높지만 가장 늦게 받는다

우선순위가 존재할 때

modify semadown(), cond wait()

---

pintos/src/threads/synch.h

struct semaphore   {
    unsigned value;             /* Current value. */
    struct list waiters;        /* List of waiting threads. */
};

• void sema_init(struct semaphore *sema, unsigned value)
  Initialize semaphore to the given value
• void sema_down(struct semaphore *sema)
  Request the semaphore. If it acquired the semaphore, decrease the value by 1
• void sema_up(struct semaphore *sema)
  Release the semaphore and increase the value by 1

struct lock 
{
    struct thread *holder;       /* Thread holding lock */
    struct semaphore semaphore;  /* Binary semaphore 
                                    controlling access. */
};

• void lock_init (struct lock *lock)
  Initialize the lock data structure.
• void lock_acquire (struct lock *lock)
  Request the lock.
• void lock_release (struct lock *lock)
  Release the lock.

struct condition {
    struct list waiters;     /* List of waiting threads. */
};

• void cond_init(struct condition *cond)
  Initialize the condition variable data structure.
• void cond_wait(struct condition cond, struct lock lock)
  Wait for signal by the condition variable.
• void cond_signal(struct condition cond, struct lock lock UNUSED)
  Send a signal to thread of the highest priority waiting in the condition variable.
• void cond_broadcast(struct condition cond, struct lock lock)
  Send a signal to all threads waiting in the condition variable.

변경해야하는 함수

Modify to insert thread at waiters list in order of priority

• void sema_down(struct semaphore *sema)
• void cond_wait(struct condition cond, struct lock lock)

Sort the waiters list in order of priority

• It is to consider the case of changing priority of threads in waiters list.
• void sema_up(struct semaphore *sema)
• void cond_signal(struct condition cond,  struct lock lock UNUSED)

Priority Inversion

: 더 높은 우선순위를 가진 스래드가 낮은 우선순위를 가진 스래드를 기다린다

A는 왜 기다리고 있을까?

•	운영체제는 ready 상태에 있는 스레드들 중 우선순위가 가장 높은 스레드에게 CPU를 준다.
•	하지만 A는 현재 blocked 상태다. 왜냐하면:
•	A는 락을 요청했지만
•	그 락은 이미 다른 스레드(C)가 가지고 있기 때문
•	따라서 A는 wait list에 들어가고 실행되지 못한다.

⸻

왜 C가 CPU를 못 받는가?

•	C는 락을 들고 있지만, 우선순위가 낮다.
•	운영체제는 ready 상태의 스레드 중에서 우선순위가 높은 스레드를 선택하기 때문에
•	C보다 우선순위가 높은 다른 스레드가 있다면, C는 CPU를 받지 못한다.
•	결과적으로 C는 락을 계속 가지고 있는 상태가 되고,
•	A는 락을 기다리느라 계속 blocked 상태에 머물게 된다.

⸻

그럼 B는 왜 실행되는가?

•	락을 요청하는 상태와 CPU를 쓰는 상태는 별개다.
•	B는 락을 요청하지 않고, 자신의 일을 하기 위해 ready 상태에 있다.
•	운영체제는 다음과 같은 스레드 상태를 본다:
•	B: ready 상태 (락과 무관)
•	A: blocked 상태 (락을 기다리는 중)
•	C: ready 상태지만 우선순위가 낮음
•	따라서 운영체제는 B에게 CPU를 할당한다.

⸻

우선순위 역전이 발생하는 구조

•	C는 락을 쥐고 있다. → A가 실행되기 위해선 C가 락을 놓아야 한다.
•	A는 락을 기다리고 있다. → blocked 상태
•	B는 락과 상관없는 작업을 하고 있다. → 하지만 우선순위가 C보다 높기 때문에 계속 CPU를 점유한다.

결과적으로:
• C는 실행되지 못해서 락을 놓지 못하고,
• A는 계속 락을 기다리며 blocked 상태에 머무른다.

Priority Donation

우선순위를 상속