Pintos project 1 Alarm clock, priority scheduling

project 1 Threads는 크게 2가지를 개선하는 방식으로 진행되는데 우선 alarm clock을 먼저 이야기하겠다

 기존의 Alarm clock(sleep)은 스레드가 일어날 때까지 busy waiting으로 대기하면서 언제 깨울지를 기다린다. 밑의 코드처럼 시간이 될 때까지 계속 깨워서 확인하게 된다. 우리는 이걸 주어진 시간만큼 스레드를 재웠다가 다시 깨울 것이다.

기존의 alarm clock

그러기 위해서는 몇 가지 상태에 대해 알아야 되는데 위에서 말한 것처럼 스레드가 돌고 있는 상태를 running,  우리가 스레드를 잠재우면 blocked 된다고 말한다. 이걸 다시 깨워서 ready 큐에 넣는데 이걸 대기 상태라 볼 수 있다. 따라서 우리는 block 시켜서 잠재울 애들을 따로 관리하는 sleep list를 추가해 줄 것이다. 구체적인 구현은 직접 해보면서 찾고 흐름만 파악해야겠다. 우선 가장 중요한 sleep과 awake를 보자

sleep

awake

그리고 당연히 timer interrupt 하는 부분에서 틱이 바뀔 때마다 awake를 호출해주면 된다. 그래서 sleep 리스트 스레드 중에 조건에 해당하는 스레드를 다시 깨워준다.

여기서 몇 가지 기억해야 되는 건  sleep 하는 부분에서 다른 인터럽트가 생기지 않게 꺼주는 부분이다. 

다음은 바로 priority shedule로 넘어가 보자

우선순위 스케줄은 말 그대로 우선순위를 두어서 ready_list에서 스레드를 꺼내는 방식이다. 그럼 당연히 우선순위를 쓰레드 마다 둬야겠다. 지금은 단순이 FIFO로 작성되어있다. 그러기 위해서 기존에 list.c에 작성되어 있는 list_insert_ordered를 사용할 것이다. 나는 넣을때 마다 순서를 맞춰 넣어주는 방식을 사용 할 것이다. 그렇다면 언제 쓰레드 들을 넣는지 알아야 할것인데 위에서 대략 말한 state들의 변화가 생기는 것을 기억해 보자. 우선 yield라는 부분에서 말 그대로 쓰레드를 양보하는 함수니까 준비 리스트로 넣을테고 unblock할때도 넣을 것이다 따라서 여기에 준비리스트에 들어가는 쓰레드들을 순서대로 넣으면 되겠다. 그리고 마지막으로 추가 할 것은 쓰레드를 만들고 우선순위를 설정하는 부분에서 바뀌는 부분이 있기 때문에 이때 스레드의 우선 순위들을 체크하여 yield를 실행 시켜 주면 되겠다

우선 순위를 확인해 선점하는 코드

자 여기까지 쓰레드 자체의 우선순위가 생길 때 상황들을 설정해 주었다. 그렇다면 스레드는 각각 공유자원을 점유해야 할 일이 생길 텐데 그럼 당연히 그 상황에서 대기하고 다시 점유하는 스레드들이 생길 것이다. 동기화 도구들을 살펴보고 고 우선순위에 맞게 동기화 도구들을 할당하는 것도 스케줄링해야 한다. 먼저 세마포를 보자 기존 코드 역시 FIFO 형태로 되어있다. 이전 준비 리스트 했던 방식으로 우선순위에 맞추면서 넣어주자

다음은 sema_up인데 여기서는 우선순위 변경을 대비해서 정렬을 한번 해준다.

조건 변수들도 세마포랑 똑같이 작성하면 되는데 다른 점은 기존 코드에서 조건 변수는 세마포에서와 다르게 리스트에 세마포가 들어가기 때문에 비교 함수도 다르게 작성해 주어야 한다. 세마포의 가장 앞의 스레드를 비교해 주면 된다.

이러면 일단 동기화 도구에 대한 스케줄까지 끝난다.

다음으로 donation인데 이게 왜 갑자기 튀어나오냐면 여러 스레드들 사이에서 우선순위가 높은 스레드가 락을 얻고 싶은데 그 lock을 대기중인 낮은 쓰레드가 가지고 있기 때문이다 따라서 높은 우선순위를 가진 친구가 낮은 친구에게 잠시 우선순위를 빌려줘 그 스레드의 실행이 끝나게 해 준 뒤 자기가 받아 온다. 구체적인 구현은 코드로 설명하고 싶으나 생략하고. 필요한 사항들을 체크해 보자 여기서는 당연히 lock부분을 수정해 줘야 하는데 lock holder와 donate 부분을 추가해주면 된다. 또한 donate 부분은 chain처럼 연결된 상황도 생각해서 구현해 주어야 한다. donation은 여러 개를 받아야 하니 list로 만들어 관리해 준다.

우선순위 donate

우선순위를 업데이트 하는 부분은 priority가 새로 갱신 될때 해줘야 한다