[pintOS] 1주차 WIL

Johnny·2021년 10월 3일
0

개발일지 (정글)

목록 보기
3/7

목표

결과

  • Alarm Clock: 해결
  • Priority Scheduling: 해결
    • Priority Scheduling
    • Synchronization
    • Priority Inverse Problem
  • Advanced Scheduling: 미완

학습 포인트

Alarm Clock

개요

  • 기존 상황 및 문제점
    • 알람 기능이 busy-wait 방식으로 구현되어 있음
    • thread가 CPU를 점유한 상태로 대기함에 따라 불필요한 자원 낭비가 발생함
  • 개선 사항
    • 다음 실행을 기다리는 thread들의 대기열(ready_list) 외에 알람을 기다리는 thread들의 대기열(sleep_list)를 생성해 별도 관리
    • thread를 sleep_list에 추가하고 필요한 시점에 다시 깨우는, 즉 ready_list에 복귀 시키는 로직 추가

살펴보기: busy wait 방식에는 어떤 문제가 있을까? 꼭 나쁜 걸까?

  • busy wait
    • busy wait은 실행중인 thread가 다른 thread에게 선점(preempt)되었을 때, BLOCKED 상태가 아닌 READY 상태로 대기함을 의미
    • that is, it spins in a loop checking the current time and calling thread_yield() until enough time has gone by.
  • 문제 상황
    • busy wait 방식으로 thread를 기존의 time_sleep()은 thread가 다시 시작되는 조건을 충족할 때까지 계속 실행되어 조건이 충족되었는지 확인하게 됨
    • RUNNING > READY > RUNNING > READY > ... 상태 변경이 반복됨
    • 결과적으로 CPU를 낭비하는 상황 발생
  • 문제 해결
    • 이를 개선하기 위해 event에 대한 조건을 충족할 때까지 해당 thread를 BLOCK 상태로 변경하고 조건이 충족된 시점에 다시 READY 상태로 변경하도록 수정
  • busy wait이 활용되는 상황
    • busy wait이 언제나 비효율적인 것은 아님
    • 마우스 움직임(Input)을 기다리는 것처럼 주기가 상당히 짧은 작업의 경우, busy wait으로 구현되어 있음

Priority Scheduling

개요

  • 기존 상황 및 문제점
    • 스케줄러가 round-robin으로 구현되어 있으며 우선순위를 고려하지 않음
    • 더 높은 우선순위의 thread가 생성되어도 ready_list의 맨 뒤로 들어가며, 다음에 실행될 thread를 찾을 때도 우선순위에 상관 없이 리스트의 맨 앞에서 꺼냄
  • 개선 사항
    • ready_list가 우선순위 순으로 관리됨
    • 더 높은 우선순위의 thread가 생성되면 기존 thread를 밀어내고 실행됨

살펴보기: 개선 후 thread의 실행 순서

  • 어떤 일이 벌어질까?
    • 우선순위가 가장 높은 thread가 1개일 경우, 혼자 계속 실행됨
    • 우선순위가 가장 높은 thread가 2개 이상일 경우, 동일한 우선순위 내에서 round robin

      pintOS GitBook 1주차 FAQ
      If the highest-priority thread yields, does it continue running?
      Yes. If there is a single highest-priority thread, it continues running until it blocks or finishes, even if it calls thread_yield(). If multiple threads have the same highest priority, thread_yield() should switch among them in "round robin" order.

  • 왜 그럴까?
    • 전제 1. 실행중인 thread가 변경되는 상황
      • 정기적인 변경
        • 내장된 타이머(PIT)가 주기적으로 보내는 thread 변경 신호가 발생한 경우
      • 비정기적인 변경
        • 현재 thread가 특정 조건이 충족되기까지 기다려야 하는 경우
        • 더 높은 우선순위의 thread가 생성된 경우
        • 기타 특정한 이벤트가 발생한 경우
    • 전제 2. 우선순위가 반영된 ready_list (현재 문제의 개선 사항)
      • ready_list가 우선순위 순으로 관리됨
      • 더 높은 우선순위의 thread가 생성되면 기존 thread를 밀어내고 실행됨
  • 결과적으로
    • 우선순위가 가장 높은 thread가 1개일 경우
      • CPU를 점유하는 중에도 정기적인 변경 요청에 의해 ready_list에 일단 추가됨 (thread_yield() 참고)
      • 이 때 현재 thread는 우선순위가 가장 높으므로 ready_list의 가장 앞에 배치됨 (list_insert_ordered() 참고)
      • scheduler가 ready_list에서 가장 앞에 놓인 thread를 다음 thread로 변경하려 하지만, 현재 thread와 다음 thread가 동일하기 때문에, 변경되지 않고 그대로 유지됨 (schedule() 참고)
    • 우선순위가 가장 높은 thread가 2개일 경우
      • 정기적 변경 요청에 의해 ready_list에 추가됨
      • 이 때 현재 thread와 우선순위가 동일한 thread가 ready_list에 대기중이었으므로, 현재 thread와 우선순위가 동일한 thread들 중 가장 뒤에 배치됨 (thread_compare_priority() 참고)
      • scheduler가 ready_list에서 가장 앞에 놓인 thread를 다음 thread로 변경하며 이에 따라 동일한 우선순위의 thread들 간에 round robin이 발생함

Synchronization

개요

  • 기존 상황 및 문제점
    • 공유 자원에 대한 접근 권한을 통제하는 semaphore, lock, condition 등의 로직이 FIFO 방식으로 구현되어 있음
  • 개선 사항
    • synchronization 로직 또한 우선순위에 따라 관리되도록 수정

살펴보기: monitors

  • https://casys-kaist.github.io/pintos-kaist/appendix/synchronization.html
  • monitor의 3가지 구성요소
    • data being synchronized: 공유 자원
    • monitor lock: 공유 자원에 대한 접근 권한
    • condition variables: 공유 자원의 상태 정보
  • 대표 예시: Producer Consumer Problem
    • data: 4칸의 책장
    • monitor lock: 책장 접근 권한
      • PUTTER: 책 1권 추가하기 (Put or Produce)
      • GETTER: 책 1권 가져가기 (Get or Consume)
    • condition variables: 책장의 상태
      • not_empty: 책장에 책이 1권 이상 있는지 여부
        • waiters: 책장에 책이 없다면 책이 추가되기를 기다리는 대기열
      • not_full: 책장에 책이 4권으로 가득 찼는지 여부
        • waiters: 책장이 가득 찼다면 빈 공간이 생기기를 기다리는 대기열
    • 발생 가능 시나리오
      • 책장은 비어 있는 상태임
      • 우선 책장에 GETTER 접근
        • 책장에 GETTER가 접근 권한을 가지고 접근해 1권 가져가려 하며, 책장의 상태가 non_empty인지 확인
        • non_empty가 false이기 때문에 책이 추가되기를 기다려야 하고, 이를 위해 접근 권한을 일단 반납한 뒤 본인은 not_empty waiters에 들어감
      • 그 다음 책장에 PUTTER 접근
        • 책장에 PUTTER가 접근 권한을 가지고 접근해 1권을 추가하려 하며, 책장의 상태가 non_full인지 확인 (이 때 접근 권한은 앞서 GETTER가 반납한 것)
        • non_full이 true이기 때문에 책을 바로 추가
        • 책을 추가한 뒤 책이 추가되기를 기다리는 thread가 있을 수 있기 때문에 non_empty가 해결되었다는 Signal을 보냄
        • 접근 권한이 waiters에 있는 GETTER에게 다시 넘어감
      • 다시 GETTER 차례
        • 책장이 책이 1권이 있기 때문에 이번에는 non_empty 통과
        • 책을 1권 가져간 뒤 책장이 비기를 기다리는 thread가 있을 수 있기 때문에 non_full이 해결되었다는 signal을 보냄
        • 접근 권한을 반납한 뒤 종료

Priority Inversion Problem

개요

  • 기존 상황 및 문제점
    • 공유자원에 대한 접근 권한으로 인해 실행 우선순위가 역전되는 현상 발생
      • 특정 공유자원에 대하여 낮은 우선순위(L)의 쓰레드가 lock을 점유하고 lock 반납 이전에 context switching 발생
      • 높은 우선순위(H)의 쓰레드의 lock aquire 요청
      • 이러한 상황에서 H와 L 사이의 우선순위를 가지는 다른 thread가 없다면, H는 접근 권한을 양도한 뒤 다시 L이 실행되어 lock 반납이 이루어짐
      • 하지만 만약 H와 L 사이의 우선순위를 가지는 다른 thread M이 존재한다면, M이 먼저 실행되어 H와 M 간에 우선순위가 역전되는 현상이 발생하게 됨
      • M 수준의 thread가 많을수록 H가 대기하는 시간은 훨씬 더 길어질 것
  • 발생 가능한 문제 유형
    • Single Donation
    • Multiple Donation
    • Nested Donation
  • 사고 과정
    • 문제 해결을 위해, lock holder의 우선순위가 lock waiter의 우선순위 보다 낮은 경우, lock holder에게 lock waiter 중 가장 높은 우선순위를 갖는 thread의 priority를 부여
    • Single Donation
    • Multiple Donation
    • Nested Donation

회고

잘한 점

  • 구현한 범위까지는 잘 이해했음
    • 초반에는 거의 대부분의 코드를 웹 상에 나온 solution들에 의존했지만, 점차 로직을 직접 고민해보는 시간을 늘려감
    • 해결한 문제들에 대해서는 충분히 이해하며 다음 단계로 넘어갔음
  • 팀원들과 적극적으로 소통하며 프로젝트를 진행했음
    • 문제를 이해하고 해결 방안을 고민하는 과정을 모두 함께 진행함
  • Github을 활용해 프로젝트 레포를 관리했음
    • 하위 문제 단위로 프로젝트를 나누어 진행
    • 자체적인 repository 관리 정책을 정해 진행
    • 팀원들 모두 1회 이상 Pull Request를 올려 master에 merge하는 경험

아쉬운 점

  • solution 없이 구현하려는 시도가 부족했음
    • 다른 사람의 풀이를 너무 빨리 본다 생각이 들었음
    • testcase를 중심으로 문제를 파악하고 해결 방법을 고민해보는 시간을 조금더 빨리 그리고 길게 가져가면 좋겠음!
  • 상대적으로 혼자 고민하며 정리할 수 있는 시간이 부족했음
    • 다음 주차에는 조금 더 균형을 맞춰보자!
  • 다른 팀과의 교류가 부족했음
    • 테스트를 더 쉽게 할 수 있는 팁이나 좋은 자료들을 뒤늦게 알게 됨
    • 다음 주차에는 강의실에 놀러도 가고 다른 팀을 초대도 하자!
profile
Johnny
개발자 서자헌
다음 포스트

[pintOS] github으로 팀프로젝트 관리하기 (pintOS 팀플 맞춤)

0개의 댓글