[pintOS] Project 1 : Threads

What is pintOS ?

Welcome to Pintos. Pintos is a simple operating system framework for the 80x86 architecture. It supports kernel threads, loading and running user programs, and a file system, but it implements all of these in a very simple way. In the Pintos projects, you and your project team will strengthen its support in all three of these areas. You will also add a virtual memory implementation.

스탠포드 CS140 강의의 프로젝트 홈페이지 introduction 첫 문단이다. 핀토스는 OS 프레임 워크이다. 이 친구는 kernel threads, user programs, file system을 아주 simple한 방법으로 구현시켜놨으며 우리는 이 친구를 6주에 걸쳐서 강하게 만들 것이다!

Why I do this ?

운영체제에 대해서 깊은 이해를 하기 위해서 OS를 구축하는 경험을 할 것 이다. 이 과정에서 앞서 언급한 threads, user programs, file system 뿐만 아니라 process, virtual memory 등 운영체제에서 중요한 내용들을 다룰 것이다.

What I did ?

아래 명시된 기능들을 구현했고, 해당 구현은 나의 깃헙에 있다. 무엇을 고려하여 구현했는지 작성해보겠다.

1. Alarm Clock

• 기존의 핀토스에서는 sleep list가 존재하지 않았고, ready list만 존재했다. 결국 현재 thread를 특정 ticks동안 sleep을 시키게 되는데, ready list에 있다가 호출된 해당(자라고 명령했던) 스레드는 시간을 체크하고 다시 스레드를 양보하는 과정을 CPU를 선점하고 계속해서 반복문을 돌면서 진행하게 된다. 이를 busy waits 현상이라고 하며 CPU 자원을 쓸데없이 낭비하게 된다.

• 우리는 이 현상을 막기 위해서 ready list가 아닌 sleep list에 넣어서 재울 것이다. 이를 다른 말로 block 시킨다고 한다.
  

2. Priority Scheduling

• 자원을 할당하기 위한 스레드를 선택하는 scheduling 방법 중 priority scehduling을 구현할 것이다.
  

• [ 우선순위 구현 ]

• thread가 생성되면 바로 ready list에 투입된다. 이 때, 방금 만들어진 thread가 현재 프로세서를 점유하고 있는 thread보다 높은 priority를 가졌다면 CPU를 선점해가는 preemption이 발생해야한다.
  

• 우리는 ready list의 가장 앞에 있는 녀석과 현재 CPU점유 중인 스레드의 우선순위를 비교할 것이다. 따라서 ready list를 정렬해야하고, ready list에 들어가는 순간은 다음과 같다.

  • 1. block된 상태의 thread를 unblock 시키는 순간
  • 2. 현재 thread를 yield 시키는 순간

• [Synchronization 구현]

• lock, semaphore, condition variable 얻기 위해서 대기하는 waiters 리스트에 삽입될 때와 이 리스트에서 thread를 깨울 때도 우선순위를 고려하여 삽입/정렬 시킨다.

• [Priority Inheritance(donation) 구현]

• 우선순위가 높은 H 쓰레드가 자원을 요구하기 위해 lock을 acquire하려는 상황에서 이 자원이 나보다 낮은 L 쓰레드의 소유였다면, H 쓰레드는 L 쓰레드가 끝날 때까지 대기해야한다.

• 이 순간에 자원을 필요로 하지 않는 중간순위의 M쓰레드가 등장한다면?!
  Priority Inversion 현상이 발생한다.

• 우리는 이를 방지하기 위해서 Priority Inheritance(Donation)을 구현할 것이다.

What I feel ?

• 간단하게 이러면 좋지 않아? 라는 식의 간단한 scheduling은 존재하지 않는다. 이점을 살리기 위해 구현하면 그 상황에서 발생할 수 있는 문제점들이 발생한다. priority를 살리다보니, priority inversion이 발생하는 것처럼 말이다.

• scheduling 에 대해서 정말 무지했다. 어떤 방법의 scheduling들이 존재하며 이들의 장단점을 조금 더 디테일하게 공부해야겠다.

• starvation, busy waiting, interrupt handle, mutual exclusion, progresss, bounded waiting 을 고려한 알고리즘을 생각해야한다. Test를 진행하면서 해당 schedule을 느껴봐야 한다.

마지막으로 나에게만 할 말을 적겠다.

1. horse는 달리게 해라!!
   
   
2. thread의 elem 은 wait list, ready list, semaphore waiters 등 Thread의 Status에 영향을 주는 list에만 들어간다.
   
   
3. thread의 donation_elem은 기부 명단 donations list에 들어간다.
   
   
4. list_entry에서 elem으로 들어갈 인자들을 맞춰줘야 찾을 수 있다. elem과 donation elem을 맞추면 간격이 맞지 않아 찾을 수 없다.