WEEK08 - PintOS Project1 - WIL

Pintos Project_1에 해당하는 부분

1. Alarm clock
2-1. Priority Scheduling

  -2. synchronization

  -3. Donation

--- 1,2는 기본적으로 구현해야 하는 부분 ---
3. Advanced Scheduler

--- 3은 옵션 ---

---

 

1. 이번 프로젝트를 하면서 알아야했던 것들 (CS적으로)

 

1. Alarm Clock

= 프로세스와 스레드 process & thread + life cycle

= 흐름 전환 (문맥 전환) context switching

= 인터럽트 interrupt

#참고한 강의(반효경) / #강의2 (김덕수)

2-1. Priority Scheduling

= 라운드 로빈 round robin

= 스케줄링 scheduling

  -2. Synchronization

  -3. Donation

= 세마포어 semaphore

= 뮤텍스 mutex (=lock)

= 모니터 monitor (=condition variable)

#전반적인 project2의 내용에 참고했던 사이트 정리

 

 

 

 

아래는 해당 주차 팀끼리 같이 작성한 WIL 및 발표 스크립트

팀원: ㅎㄷㅇ, ㅈㅇㅅ, me

발표자: me😏!

---

첫 번째 과제인 Alarm Clock

프로젝트를 들어가기 전에 공부한 내용으로는

• 프로세스와 스레드의 생명주기
• 인터럽트
• Context Switching
  • context switching이란? 현재 핀토스의 스레드 기준으로, 인터럽트가 발생했을 때, 현재 스레드의 진행 상태를 TCB에 저장하고 다음 진행할 스레드의 상태 값을 읽어서 실행하는 과정을 말합니다.
• CPU 스케줄링
  • 스케줄링의 정책은 크게 선점형과 비선점형으로 나뉩니다. 선점형은 하나의 스레드가 다른 스레드 대신에 CPU를 차지할 수 있는 것을 말하고, 비선점형은 하나의 스레드가 끝나지 않으면 다른 스레드가 CPU를 점유할 수 없는 것을 말합니다. 핀토스에서는 선점형 방식인 라운드 로빈과 우선순위 스케줄링을 사용합니다.

기존 핀토스의 Alarm Clock 문제점을 분석해보자면,

• 실행되어야 할 tick이 아닌 스레드가 계속해서 ready_list에 들어와 CPU를 점유하곤 합니다. 이런 상황을 busy waiting 이라고 하는데 이렇게 되면, 아무것도 하지않는 스레드의 반복적인 CPU 점유로 인해 자원이 낭비됩니다.

이러한 문제를 해결하기 위해…

• 스레드 구조체 안에 깨어나야 할 tick을 저장하는 변수wakeup_tick 을 생성하고,
• sleep_list를 만들어 현재 실행될 수 없는 스레드들을 넣어 관리합니다.
• 매 tick마다 timer_interrupt() 함수가 호출되면서 현재 tick과 sleep_list안에 있는 가장 작은 wakeup_tick 을 비교하여, 깨워야 할 스레드가 있는 경우, 깨워서 ready_list에 넣습니다.
• 이와 같이, 스레드가 CPU나 ready_list 또는 sleep_list 로 이동하는 과정 중에는 인터럽트의 방해를 무시하고, 온전히 함수 내부를 실행하기 위해서 인터럽트를 disable시키고, 이동이 완료 되면 interrupt level을 다시 원상태로 돌려 놓습니다.

결과적으로

• 따로 sleep_list를 만들어 잠들어야 할 스레드에게 일어나야하는 시간을 기록하여 넣게 되면, CPU가 불필요하게 실행되어 스레드를 점유하는 시간을 줄일 수 있습니다.

 

두 번째 과제인 Priority Scheduling

프로젝트를 들어가기 전에 공부한 내용으로는

• 공유자원의 동기화
• 상호배제 기법 : 공유 자원을 동기화시키기 위한 방법을 말합니다. 상호 배제 기법은 하드웨어, 소프트웨어, OS 차원으로 나누어지는데 핀토스에서는 OS차원에서 Lock, 세마포어, condition variable을 이용해 해결합니다.

기존 핀토스의 Priority Scheduling 문제점을 분석해 보면

• 기존 CPU 스케쥴링은 모든 스레드를 ready_list 의 뒤에 넣고, 꺼낼때는 앞에서 꺼내기 때문에 스레드의 우선순위에 상관없이 먼저 들어간 스레드가 CPU를 점유하게 됩니다.
• 여러 스레드가 공유자원에 접근하기 위해 Lock, 세마포어, Condition Variable을 얻기까지 waiters 리스트 안에서 기다립니다. 이때, ready_list 와 마찬가지로 선입선출의 방식으로 구현되어 있습니다.
• 우선순위가 높은 스레드가 우선순위가 낮은 스레드가 가지고 있는 lock을 얻기 위해 대기열에 있을 때, 중간 우선순위를 가진 스레드가 우선순위가 높은 스레드보다 먼저 CPU 점유권을 가져가버리는 현상이 발생합니다.

이러한 문제를 해결하기 위해…

• 여러 개의 스레드가 독립적으로 실행되면서 공유자원에 접근하고 사용할 때, 공유 자원을 동기화 시켜야 원하는 결과를 얻을 수 있습니다.
• 공유자원을 사용하기 위해 기다리고 있는 세마포어의 waiters 리스트에서도 여러 스레드가 sema_down() 함수를 호출하여 대기하고 있다고 할 때, 이 공유자원 사용이 가능해지면 기다리고 있는 스레드들 중 우선순위가 가장 높은 스레드를 선택했습니다.
• Lock을 갖고있는 스레드가 현재 CPU를 점유한 스레드보다 낮은 우선순위를 가진 경우, 현재 스레드의 우선순위를 donate하여 Lock을 갖고 있는 스레드를 우선적으로 완료 시킨 후, Lock을 받는것으로 priority inversion 문제를 해결하였습니다.

이 과정에서 어려웠던 부분을 말씀드리자면,

• 세마포어 구조체 안에도 리스트가 존재하며 이 세마포어 리스트와 기존의 ready_list와의 관계를 이해하는 게 어려웠습니다.
• 핀토스에서 모니터 역할을 하는 condition 과 그 안의 semaphore 가 어떤 상관관계를 이루는지 파악하기가 힘들었습니다.

---

 

 

실제 발표 자료

pintos8주차 발표_최종.pptx

0.68MB

 

+

이때 지적사항이 있었는데, ppt에 내용을 채워두지 않고 스크립트만 읽는 바람에, 그냥 깃북을 읽는 것 같다는 이야기를 들었다. 그래서 이후의 팀 방향은 노션이나 블로그에 글을 정리하고 해당 페이지를 스크린에 띄워 발표를 하기로 이야기를 나누었다.