[PintOS] Project 1: Threads (Alarm clock, Priority Scheduling) & 회고

WEEK08 TEAM08 IDENTITY

SW Jungle WEEK08 (2022.11.10 ~ 11.16)

PROJECT 1: THREADS

 

WIL (Weekly I Learned)

11.10 목

• 작업환경 세팅 (EC2, Ubuntu18.04) + repo 생성
• PintOS project Git Book 읽기

11.11 금

• KAIST 권영진 교수님 OS 강의
• 공부로 도망치지 마세요. from 코치님

11.12 토

PintOS 전반적인 코드 파악

• /threads/init.c
• /threads/thread.c
• /lib/kernel/list.c & /include/lib/kernel/list.h
• /tests/threads/tests.c
• /threads/synch.c

11.13 일

Alarm clock 구현

• Alarm Clock이란?
  • 호출한 프로세스를 정해진 시간 후에 다시 시작하는 커널 내부 함수
  • PintOS에서는 thread가 CPU를 사용할 시간(할당시간)은 4 tick(40ms)으로 한정되어 있음
  • 4 tick이 지나면 thread는 ready_list의 맨 뒤에 추가됨
• 문제점: Pintos의 Alarm clock은 loop 기반의 Busy waiting 방식
  • Busy waiting 방식: time_interrupt가 일어날 때마다 ready_list를 순회하며 thread들이 사용해야할 타이밍인지를 체크함
  • 즉, 자고 있는 thread들 중에 아직 일어날 시간이 아닌 thread들도 running에 상태에 넣어 CPU를 쓰면서 대기하고 있는 상태
• 목표: 프로세스를 재울 때 시스템 자원 낭비를 최소화하는 것
• 문제 해결: sleep/wake up으로 문제점 개선
  • sleep_list를 하나 만들어서 thread들을 blocked된 상태(잠자는 상태)로 넣어줌
  • time_interrupt가 일어날 때마다 sleep_list에 존재하는 thread들 중 깨워야할 tick이 된 thread를 ready_list에 넣고 상태를 ready로 바꿔줌
  • 아직 깨어날 시간(tick)이 되지 않은 thread들은 CPU를 사용하지 않고 대기할 수 있기에 문제 해결

11.14 월

Priority Scheduling (1) Priority Scheduling 구현

• Scheduling란?
  • 여러 프로세스가 번갈아가며 사용하는 자원을 어떤 시점에 어떤 프로세스에게 자원을 할당할 지 결정하는 것
• 문제점: thread들 간의 우선순위 없이 ready_list에 들어온 순서대로 실행됨(Round-Robin 방식)
  • Pintos는 Round-Robin 방식 채택, 할당된 시간 4 tick이 지나면 running thread는 다른 thread에게 선점당함
  • Pintos는 새로운 thread를 ready_list에 넣을 때 항상 맨 뒤에 넣고, ready_list에서 다음 CPU에 할당할 thread를 찾을 때는 앞에서 꺼냄
• 목표: thread의 우선순위대로 scheduling 하는 것
• 문제 해결: 우선순위를 비교하여 우선순위가 가장 높은 thread를 ready_list의 맨 앞에 위치시킴
  • thread를 ready_list에 우선순위대로 정렬되도록 삽입
  • ready_list에서 thread를 뺄 때 앞에서부터 빼기 때문
  • 문제 해결에서의 문제: running thread가 가장 높은 priority를 가지는 것을 보장하지 못 함
    1. 새로운 thread의 priority가 현재 running하고 있는 thread보다 우선순위가 높아질 때
    2. thread의 priority가 변경될 때 => ready_list에서 우선순위가 가장 높은 thread와 running thread를 비교하여 우선순위가 더 높은 thread가 선점할 수 있게 해줌

11.15 화

Priority Scheduling (2) Semaphore, Lock, Condition Variable 구현

• Semaphore, Lock, Condition Variable을 사용하여 Priority Scheduling 개선
  • PintOS는 여러 thread들이 Semaphore, Lock, Condition Variable를 얻기 위해 기다릴 경우 먼저 온 thread가 먼저 사용하는 FIFO 방식을 사용
  • Sychronization 도구들을 기다릴 때, 우선순위가 가장 높은 thread가 CPU를 점유하도록 구현

11.16 수

Priority Scheduling (3) Priority donation(Prority inversion problem) 구현

• 문제점: 여러 thread가 lock을 요청하고 점유하는 과정에서 Priority Inversion 발생
  • priority가 높은 thread가 priority가 낮은 thread를 기다리는 현상
• 문제 해결: Priority donation
  • Multiple donation
    • thread가 두 개 이상의 lock 보유 시 각 lock을 획득하고자 하는 thread들에게 donation 발생가능
    • 예시) thread L이 lock A와 lock B를 점유하고 있을 때 thread M이 lock A를 요청, thread H가 lock B를 요청하는 상황
  • Nested donation
    • 여러 번의 단계적 donation이 일어나는 상황

11.17 목

Project 1 결과

• 10:00 ~ 11:00 발표 진행

 

https://github.com/choidabom/KAIST-PintOS

GitHub - choidabom/KAIST-PintOS: WEEK08: THREADS, WEEK09: USER PROGRAMS

 

Pintos 회고)

Pintos Project 1이 끝났다. 정말 책에서만 보던 커널을 내가 짜게 될 줄 몰랐다. 공부로 도망치지 말라는 코치님의 말씀은 어느정도 이해는 갔지만 정말 일요일부터 몸소 느꼈다. 시간이 없다는 것을. 블로그에 정답이 나와있는 코드를 보지 않고 짜고자 했고 우리조는 최소한의 레퍼런스를 봤었다. 사실 처음 3일 정도는 감이 안 잡혔기 때문에 정말 극도의 스트레스를 받았다.. 일단 첫번째로 함수를 타고 타고 타고 타고 타고가야하는 과정 자체가 처음에는 "정말" 쉽지 않았었다. 또한, 큰 그림을 보고 싶었는데 큰 그림이 안 보였다. 사실 이렇게 방대한 양의 코드를 보고 구조를 파악하는게 핀토스의 핵심 포인트라고도 생각한다. 이론만 봐서는 절대 모를 핀토스 과제를 수행하기 위해 우리조는 머리는 3개, 코드는 1개인 트리플 코딩을 진행했고, 결론적으로는 나쁘지 않았다. 코드를 계속 보면서 어느 정도 그림이 그려졌긴했다. 과정 속에서 디버깅의 어려움을 정말 정말 정말 느꼈고, list_remove의 반환값을 받지 않아 힘든 고생을 했음에도 같은 실수를 반복했다거나, 함수 하나의 오류로 모든 test case가 FAIL이 뜨는 경험도 했다. 정확히 발표날인 목요일 새벽 4시 반에 ALL PASS가 뜬 후, 발표를 하고자 정리했던 부분에서 우리는 코드의 구조를 이해하기 위해 "추상화"의 과정을 통해 이해했음을 깨달았다. 모르면 DL 오빠의 주도하에 그림을 그려가면서 이해하고 넘어갔다.(짱) 운영체제는 추상화의 꽃이니라 ... 끝으로 내용이 방대한 만큼 순간 순간에 정리해야하는 습관을 들여야할 것 같다. 잘 풀리면 재밌고, 안 풀리면 정말 말도 안 되게.....  힘든 핀토스 녀석 ... Project 2도 화이팅이다.