Pintos Thread (WIL) 깊게 생각해볼 Keyword

이번주에는 쓰레드 스케줄링 알고리즘을 이해하고 OS 알고리즘을 짜봤는데 깊게 생각해봐야될 키워드 들이 뭐가 있는지 고민해보고 적어보려고한다.

 

1. 쓰레드 상태란

 

운영체제에서 관리하는 쓰레드의 현재 상태를 나타내는 개념이다.

 

5개의 상태가 있고 Create,Ready,Running,Blocked, Terminated

 

생성(Create) : 쓰레드가 생성되었지만 아직 실행되지 않은 초기 상태이다.

 

준비(Ready) : 쓰레드가 실행 가능한 상태이고, 프로세서의 할당 기다리는 상태

 

실행(Running) : 쓰레드가 현재 프로세서에서 실행되고 있는 상태

 

종료(Terminated) : 쓰레드가 실행을 완료하고 종료된 상태

 

위와 같은 상태가 있고 스케줄러에 의해 상태 전환이 관리 된다.

 

 그러면 스케줄링은 무엇인가?

---

2. 스케줄링이 무엇인지?

운영체제에서 프로세스나 쓰레드의 실행순서를 결정하는 방법이다.

 

운영체제에서 스케줄링은 어떠한 방법으로 돌아갈까?

 

스케줄링은 운영체제에서 공정성과 내가 처리해야되는 처리량, 응답 시간, 대기 기산, 처리의 우선순위, 자원 효율 등을 확인하고 알맞는 정책을 사용하여 수행한다.

 

또 의문이 생긴다 어떤 스케줄링이 있을까?

 

---

3. 스케줄링 알고리즘종류

스케줄링 알고리즘은 다양한 알고리즘이 있다.

 

1. Round Robin 방식 라운드 로빈 방식은 일정한 시간 할당하여 순환 방식으로 실행한다. 시간 할당량이 지나면 다른 프로세스나 쓰레드로 전환하는 방식이다. 공정성 유지하면서 시분할 시스템에서 널리사용된다.

 

2. 우선순위 기반 스케줄링은 우리가 이번주에 구현해본 알고리즘이다. 쓰레드나 프로세스에 우선순위를 부여하고, 높은 작업을 우선적으로 실행한다. 정적 우선순위, 동적 우선순위등 여러 방식으로 쓸 수있다. 해당 주 pintos에서는 우선순위를 기부하는 donation으로 우선순위 역전(inversion) 현상을 방지해보고, 다단계 큐방식인 (MLFQ)까지 구현해보았다.

 

3. 최단 작업 우선은(SJF) 실행 시간이 가장 짧은 작업을 우선적으로 실행한다.

 

4.최소 잔여 시간 우선(SRTF)은 현재 실행중인 작업보다 실행 시간이 더 짧은 작업이 도착하면 중단하고 해당 작업을 실행하는것.

 

5. 최소 응답 시간 우선(SRTF) : 현재 실행 중인 작업보다 응답시간이 더 짧은 작업이 도착하면 실행 중인 작업을 중단하고 새로운 작업을 실행하는 알고리즘.

 

---

4. 프로세스와 쓰레드

이 주제는 엄청 중요한 부분이다.

 

프로세스는 하나의 관리의 단위로 생각할 수 있다.

 

관리의 주체는 OS 이고 프로세스는 연산을 한다. 이러한 연산이 연속적으로 모여서 하나의 흐름을 만드는데 이 흐름을 

 

프로세스 수준에서는 최소 1개 이상 있는데 이러한 흐름을 flow나 하거나 context라고 한다. 또 이 흐름이 2개 이상이 될 때가 있는데, 이 흐름들은 동시에 각자 작동한다.

 

한 프로세스에서 개별화된 실행순서의 흐름이 여러개로 나뉠때 이 각 흐름을 쓰레드라고 하는데 프로세스에 무조건 1개 이상 존재한다.

 

이 흐름이 여러개가 되었을때 멀티 쓰레드라고 하고, 프로세스가 여러개면 멀티 태스킹이라고 한다.

 

요즘 CPU 여러개의 코어를 가지는데, 연산할 때는 RAM 하고 직접적으로 붙어서 작동한다.

 

만약 어떤 프로세스가 존재한다면, 이 안에 연산 코드들이 흐름을따라 연산하는데 여기서 가장 필요한 장치는 CPU이다.

 

또 운영체제 입장에서는 이 프로세스를 관리하고 잘작동하도록 지원하는데, 우리의 CPU은 연산을 할 즉 그림으로 따지면 연습장(공간)= RAM이 필요하다. 이 메모리를 일정 단위로 잘라서(paging) 해서 매핑해서 사용하게 해준다.

 

하드웨어 기준에서는 물리 메모리인데 운영체제에서 프로세스를 위해 매핑 해주는 것이  메모리(연습장)는 가상화 메모리 이다.

 

무조건 RAM만 사용하는 것이 아니고 HDD와 같은 2차 메모리도 사용한다. 즉, 크게 보면 RAM 과 HDD를 통해 추가로 만든게 가상 메모리라고 생각하면 된다.

 

운영체제는 만든 가상메모리를 프로세스에게 할당해준다.

 

처음 부터 요약해보자면 우리가 연산한다고 하는것은 쓰레드 단위로 한다.

 

프로세스에 속한 모든 쓰레드는 프로세스의 가상 메모리안으로 공간이 제약된다.

 

쓰레드 라는 것이 실질적으로 연산을 하는 주체이다.

 

쓰레드 마다 각자 stack 메모리와 레지스터를 할당해준다.

 

간단하게 보면 프로세스라고 하는 애를 한 가구라고 생각하고, 프로세스라고 하는 집이라는 공간을 주고 이 한 집에 세대원이 있고, 거기 안에 각자 공간이 있다고 해보자

 

우리는 집이라고 하는 공간이 virtual 메모리이고,세대원들이 Thread라고 생각할 수 있다.

 

각자의 공간은 사생활을 위해 방을 준다. 이 방을 Thread_local_storage라고 하고 거실 같은 공용 공간을 Heap이라고 생각하면 편하다.

 

각자 virtual memory를 주는게 나을까 공용 virtual memory를 쓸 것인지 어떤것이 더 좋다 보다 해야하는 일의 특성에 따라 고르면 된다.

 

쓰레드 관해서는 또 멀티 쓰레딩에 관한 문제인데 우리가 걱정하는 동시성 문제와 동기화 문제가 따라온다.

 

---

5. 동기화 수단

우리조는 이번주 pintos에서 동기화 수단으로 semaphore와 lock방식, condition variable을 사용하였다.

 

semaphore로 waiter_list를 만들어서 block 상태로 만들어 놓고 interrupt가 일어나면 water_list에서 공유자원을 점유하는 방식을 사용하였고, condition variable에서 semaphore내 연산들의 우선순위들을 계속 동적으로 재조정해주면서 처리 해주었다.

 

---

6. 컨텍스트 스위칭 + PCB

CPU는 한 번에 하나의 프로세스만 수행할 수 있지만, 우리는 동시에 여러개의 일을 시키기 때문에, 여러 개의 프로세스를 번갈아 가며 수행한다. 이 번갈아 가면서 수행할 명령어를 바꾸는 과정을 context switching 이라고 한다.

 

우리는 번갈아 하는 와중에 프로세스와 관련된 데이터 구조가 당연히 있어야하고, 이 기본적인 정보들을 어딘가에 저장되어야 한다고 생각 할 수 있다.

 

이 저장하는 곳이 바로 PCB(Process control block)이다.

 

예를 들어서 다른 프로세스로 전환되어서 기존 작업 하던 작업을 임시 저장했다가 다시 실행해야되는데 그 다시 처리할 명령을 저장하는 공간을 의미한다.

 

이 PCB안에는 Process id , Process state, Program Counter, Register, CPU 스케줄링 정보 등 이 들어간다.

 

---

7. atomic

 

원자성은 수행 도중 중단될 수 없는 하나의 동작 단위를 의미하는데,  우리는 개별 프로세서 명령어들은 각각 원자적 행위라 보는게 가능하다.

 

이것은 프로세스 동기화와 상호배제 측면에서 매우 중요한 주제이다.

 

하나의 프로세서 명령어가 수행 중이라면, 어떤 인터럽트가 발생해도 그 명령어 수행은 중단되지 않고, 프로세서는 그 명령어의 수행이 종료된 이후에 인터럽트를 처리하는것을 의미한다.

 

전에 공부했던 동시성 프로그래밍에서 한 공유 변수(전역 변수)에 대해서 count++ 했던 과정에서 나오는 P(s) 을 하는 증가 연산과 V(s)하는 감산 연산이 인터럽트 기준으로 돌아가는 부분을 의미하는것 같다.