[yummyHitOS] 16 day (2017.07.31)
짜란!! 바로 하루만에 글쓰려니 너무 흥분돼서 잠도 제대로 못잤네여!! 그러므로 첫 짤로 이것을 투척할게여!!
오늘은 스케줄러에 대해서 알아보기로 했었져!! 스케줄러... 이름은 참 이쁘지 않나여? 연예인이나 사업하시는 바쁘신분들 보면 '어 나 오늘 스케줄이 빡빡해서~' 크 뭔가 바빠보이는 멋찜뿜뿜!!
그러면 뭐하나여... 이 스케줄러는 태스크의 실행 순서를 결정하기 위한 녀석인걸요...
Scheduler
스케줄러(Scheduler)란 각 프로세스들이 같은 자원을 공유할 때나 실행된 태스크를 우선순위 및 중요도 등의 기준에 따라 정렬해 순서를 정해주는 녀석이예요. 이를 통해 시스템의 성능 향상을 시키는데, 이 스케줄러는 아직 완벽하게 끝이 나지 않았어요! 왜냐하면! 알고리즘이 계속해서 나오고 있기 때문이져!
바로 이 알고리즘때문에 스케줄러에 거부감이 확확 와닿는거예여 T^T 이런 거부감과 스트레쓰엔 역씨 이번 제주도 다녀온 맛집들과 풍경으로 풀어야져!! 가랏 아름다운 제주아일랜드!!
ㅜㅠㅜ갈치회를 못먹었어여.. 고등어회, 광어회, 우럭회, 도미회, 황돔회를 먹었는데 개인적으로 고등어회가 제일 맛있더라구여!! 그리고 옥돔구이정식!! 흑돼지 제육볶음과 간장게장 등의 밑반찬에 1인 1옥돔구이 ㅜㅠㅜ정녕 이것이 혜자식당입니까.. 힘들기도했지만 넘나 즐거운 제주도여행이어써여!! 맨아래 풍경 이쁘지않나여!? 야미는 풍경찍는걸 넘나 좋아하거든여!!
자! 그럼! 책을 살펴보기 전에 먼저 스케줄링 알고리즘 종류부터 볼까여?
items
<< 비선점 프로세스 스케줄링 >>
FCFS(First Come First Served) Scheduling
SJF(Shortest Job First) Scheduling
HRRN(Highest Response Ratio Next) Scheduling
<< 선점 프로세스 스케줄링 >>
RR(Round Robin) Scheduling
SRTF(Shortest Remaining-Time First) Scheduling
Multi-Level Queue Scheduling
Multi-Level Feedback Queue Scheduling
RM(Rate Monotonic) Scheduling
EDF(Earliest Deadline First) Scheduling
사실 이게 전부는 아니지만, 위키백갓에 나와있는 것이므로 대표적인 것들이겠죠!? 이 중에서 몇 개는 들어보셨을거예요! 왜냐하면 FCFS 스케줄링 같은 경우, 먼저 도착한 것이 먼저 처리되는 스케줄링 기법으로 자료구조에서 FIFO와 일맥상통하기 때문이죠!
우리가 알아볼 스케줄링은 무엇일까요 두구두구두구두~
바로 비선점 프로세스 스케줄링의 2가지와, 선점 프로세스 스케줄링의 4가지를 알아볼까해요! (제가 생각하기에)기본적인 스케줄링이라고 생각하거든여!! 사실 저두 RM 스케줄링과 EDF 스케줄링은 첨드러바써영...헿헤헤
스케줄링 알고리즘이 아직도 끝이 없이 계속 나오는 이유는, 평가 기준을 살펴보면 이해가 되실거예요.
criteria
<< 스케줄링 알고리즘의 평가 기준 >>
CPU 사용률(CPU Utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율
처리량(Throughput) : CPU가 단위 시간당 처리하는 프로세스의 개수
응답 시간(Response Time) : 대화식 시스템에서 요청 후 응답이 오기 시작할 때까지의 시간
대기 시간(Waiting Time) : 프로세스가 준비 큐 내에서 대기하는 시간의 총합
반환 시간(Turnaround Time) : 프로세스가 시작해서 끝날 때까지 걸리는 시간
즉, 소프트웨어적으로 구상하고 구현해둔 알고리즘이 하드웨어가 변경되면 어떻게 될지 모르는 상황이라는 것이예요!! 언젠가는 현재 알고리즘이 다 구식이 되거나 정 반대의 알고리즘이 필요해지는 상황이 생길 쑤도 있겠죠?! 크~ 역시 인생이란 살아봐야 안다더니..
먼저 첫 번째로 가볍게 설명드렸던 FCFS 스케줄링을 알아보아여!!
FCFS
FCFS(First Come First Served) Scheduling은 가장 단순한 스케줄링으로, 먼저 자원 사용을 요청한 프로세스에게 자원을 할당해 주는 방식의 스케줄링 알고리즘이예요. 위 그림을 보면, P0 프로세스가 가장 먼저 도착했기 때문에, P0 프로세스가 끝날 때까지 나머지 프로세스는 대기하고, P0 프로세스가 수행이 끝나는 5초 후에 P0 프로세스 다음으로 도착한 P1 프로세스를 실행하게 되지요! 그렇게 P1 프로세스가 3초 실행되어 수행이 끝나면 그 다음으로 도착한 P2 프로세스를 실행하게되고, 이런 식으로 수행하는 알고리즘이 FCFS 스케줄링이예요.
아까 말했던 것처럼 Queue처럼 들어온 순서대로 처리하니 넘나 비슷하지 않나여!! 아닌가여!? 넵... 쭈굴...
그럼 다음으로는 SJF 스케줄링을 살펴볼게여 ㅎㅎㅎ
이거 그림이 이상해서 제가 그림판으로 수정 좀 했어요! 전 그림판쟁이거든여 ㅎㅎㅎ(프로그램 다운받기 싫어하는 1ㅅ)
SJF
SJF(Shortest Job First) Scheduling은 평균 대기 시간을 최소화하기 위해 CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식의 CPU 스케줄링 알고리즘으로 평균 대기시간을 최소로 만드는 걸 최적으로 두고 있는 알고리즘이예요. 위 그림을 보시면 먼저 도착한 P0 프로세스를 실행하지만, 1초가 경과했을 때 P1 프로세스가 도착해 가장 짧은 실행시간을 갖고 있기 때문에 P0 프로세스는 수행을 멈추고 P1 프로세스를 실행해요. 그 후 P2 프로세스나 P3 프로세스가 도착해도 P1 프로세스가 가장 실행시간이 짧기 때문에 P1 프로세스가 수행이 끝난 후 실행시간이 짧은 P0 프로세스를 수행하게 되고, 그런 식으로 수행을 끝까지 하게 되는 알고리즘이예요.
비선점 프로세스 스케줄링은 생각보다 간단하지 않나여?! 바로 다음으로 첫 번째 선점 프로세스 스케줄링인 Round Robin 스케줄링을 알아보아여!!
RR
RR(Round Robin) Scheduling은 시분할 시스템을 위해 설계되었으며 프로세스들 사이에 우선순위 없이 Quantum이라는 시간단위를 통해 CPU를 할당하는 알고리즘이예요! 먼저 도착한 프로세스에 대해 퀀텀 단위만큼 실행 시킨 후, 그 다음으로 도착한 프로세스를 퀀텀 단위만큼 실행시켜요. 만약 퀀텀 단위보다 실행시간이 적다면 실행시간만큼만 수행한 후 다음 프로세스를 실행시키구요. 순차적으로 퀀텀 단위만큼 수행하게 CPU를 할당한 후 모든 프로세스가 끝날 때까지 빙글빙글 돌리는 방식이라 라운드라는 단어가 붙지 않았을까여!? 아닌가... 헿 그래서 위 그림처럼 가장 먼저 도착한 P0 프로세스를 3초 수행하고 그 다음 프로세스인 P1 프로세스를 수행하는데, P1 프로세스는 실행시간이 3초이기 때문에 순서가 되면 수행이 종료되어 이 후에 P1 프로세스를 수행할 필요가 없지요! 그리고 P2 프로세스를 실행하며 이렇게 모든 프로세스가 끝날 때까지 반복하는 알고리즘이랍니다!
우리가 알아보려는 스케줄링 알고리즘 중 3가지가 끝났어여! 그런데 벌써 스크롤이 작아지네여... 오늘도 스압주의가 필요할 것 같아요!! 더 깊게 공부해야하는 스케줄링에 대해 단기집중식으로 알아보고 있는데, 머리가 넘나 깨질 것만 같네영 ㅠㅜ 여러분은 어떠신가여?
공부는 미X놈처럼 해야 흥미가 생기는 것 같아여! 개미를 저렇게 통통통~ 치시면.. 넵 얼른 다음 스케줄링인 SRTF 스케줄링을 봅씨다!!
SRTF
SRTF(Shortest Remaining Time First) Scheduling은 SJF 스케줄링을 비선점에서 선점 형태로 수정한 스케줄링 알고리즘이예요. 위 SJF 스케줄링과 비교하면 거~의 비슷하지 않나여!? 실행시간을 비교하여 현재 수행 중인 프로세스보다 실행시간이 짧으면 수행 중인 프로세스를 중단시키고 새로 들어온 프로세스를 먼저 실행해버려요. SRT(Shortest Remaining Time) 스케줄링이라고도 부른다고 해요! 위 그림을 설명하자면 가장 먼저 들어온 P0 프로세스를 수행하다가 실행시간이 더 짧은 P1 프로세스가 들어오면서 P0 프로세스를 잠시 중단하고 P1 프로세스를 실행해요. 다른 프로세스가 들어와도 실행시간이 더 길어 P1 프로세스를 끝까지 수행하고, 다시 실행시간을 비교하는데 잠시 중단중이던 P0 프로세스가 실행시간이 가장 짧기 때문에 P0 프로세스를 전부 수행하고 그 다음으로 실행시간이 짧은 P3 프로세스를 실행하는 방식의 알고리즘이지요.
자! 이제 우리에게 남은 스케줄링은 멀티레벨 큐 스케줄링과 멀티레벨 피드백 큐 스케줄링이 남았어요! 위키백갓에 찾아보면 멀티레벨을 다단계라고.. 넹?! 다단계여!? 우리가아는 그 네트워크 마케팅이라는 다른 이름의 다단계여!? 그래서 저는 그냥 멀티레벨이라구 하려구여.. 여러 단계로 되어있다는 의미로 다단계라는 단어를 쓴 것 같긴 한데... 넘나 낯선것~
Multi-Level Queue
Multi-Level Queue Scheduling은 커널 내의 준비 큐를 여러 개의 큐로 분리하여 큐 사이에도 우선순위를 부여하는 스케줄링 알고리즘이예요. 각 큐마다 다른 스케줄링을 적용시키고, 적용된 스케줄링을 변경할 수 없는 알고리즘이예요!
이에 반해 Multi-Level Feedback Queue Scheduling은 멀티레벨 큐 스케줄링에서 프로세스가 자신에게 적합한 스케줄링이 적용되어 있는 큐로 배치되어 작업을 수행하는 알고리즘이구요!
우와~ 드디어 6가지의 스케줄링 알고리즘을 전부 살펴보았어요!! 박수쨖쨖~~~
드디어 이번 챕터가 끝난 거신가!? 아녀... 제가 저번에 LIFO(FILO), FIFO(LILO) 자료구조를 설명할 때 스택과 큐만 설명하구 리스트를 설명 안했더라구여... 이 멍청한 야미...ㅜㅠ 그래서 스케줄링과 함께 리스트를 구현할 이번 챕터이기에 리스트와 링크드 리스트를 설명드리려고 해요! 넘나 빡센 이론을 공부하니 머리가 아프시져?! 아주 씬나는 비트의 노래를 들으며 곰과 함께 쿵짝쿵짞~
흥많은 곰과 둠칫 두둠칫~
리스트에 대해서 간략히 설명드리자면, 일반적으로 리스트는 ArrayList를 의미해요. Python을 사용해 보신 분이라면 일반 변수가 리스트로 생성된다는 것을 아실텐데, 이 리스트는 배열과 비슷해요! 인덱스 값을 가지고 리스트를 구성하여 관리하기 때문이예요. 배열과 배열리스트(ArrayList)의 차이점에 대한 것은 참고자료로 드릴게여!(또다시 시작된 야미의 떠넘기기..가 아니라 저도 읽어보고 괜찮은 문헌을 배포하는거예요!! 의심하지 말아주세여 ㅜㅠㅜ제가 설명하는 것보다 자료를 읽는게 좋은 것 같아서여...쭈굴...)
Arrays and ArrayLists Lecture.pdf
그리고 LinkedList에 대한 자료도 있지만, 우선 제가 쉽게 설명해드리자면 Node 라는 것이 있어요. 바로 전 인덱스의 주소를 가리키는 포인터로 이루어진 것인데, 이 노드가 이 전 인덱스를 가리키기 때문에 포인터만 잘 적용해주면 Null Pointer Exception 예외가 발생할 일은 없어요! ArrayList보다는 구현이 조금 복잡하지만, 구현만 해두면 사용하기 정말 편하다는 강점이있지요! 이렇게 노드를 이용해 리스트를 꾸리는 것이 링크드리스트랍니다! 가랏 참고자료!!
이 두 참고자료를 정리해주신 멋찐분들께 감사의 박수를 쨖쨖~~
이번 챕터 18의 큰 틀은 스케줄링과 링크드리스트를 통한 라운드 로빈 스케줄러를 구현하는 것인데, 이론적인 설명은 다 된 것 같아요!
그 외 이론은 매 포스팅마다 극찬하는 갓승훈 선생님의 책에 상세히 적혀있구요! 천천히 책을 넘겨보다보면... 뭔가 익숙한듯 낯선 용어가 나오네여! 태스크풀..? TCB..? 먹는건강 파오후 쿰척쿰척...
TCB
그림판충 야미가 마쏘오피스의 빠워뽀인트를 이용해서 그려보았어요!! 스택 포인터가 가리키는 위치는 태스크 풀이 있을 0x800000(8MB)에서부터 [TCB크기(sizeof(struct TCB)) * Task 수] 만큼 떨어진 곳에 있는 스택 풀이예요!! 그 위치를 정확히 모르니 그냥 정 중앙에 화살표를...(사실 파워포인트에 나타내지는 선의 중앙에 자동으로 뙇 하고 되길래 그대로 그려써여...) 그렇다면 TCB는 무엇이고 태스크 풀이란 무엇일까여?!
task pool
태스크 풀(Task Pool)이란 용어가 태스크 자료구조인 TCB를 모아둔 공간, 즉 특정 메모리 영역이 등장하고 TCB(Task Control Block)는 태스크를 생성하거나 삭제할 때 사용 할 블록이 나오는데 이 블록은 관리가 필요한 특정 프로세스의 정보를 포함하는 커널영역의 자료구조예요. 어제 Task와 Process는 일맥상통하는 의미로 사용된다고 했었죠!? 그래서 PCB(Process Control Block)라고도 하더라구여!
드디어 이번 챕터의 마지막 포스팅인 시분할 멀티태스킹이라는 용어!! 아까 스케줄링 알고리즘에서 시분할 시스템을 위해 설계된 것이 있지 않았나여? 바로 라운드 로빈 스케줄링이죠!! 우리는 Interrupt 파트에서 이미 시분할에 대한 인터럽트처리를 공부했어요. Timer Interrupt인 IRQ 0번이요!! 그것을 통해 시분할 멀티태스킹을 처리해 주는 것이 우리의 개성파 OS이예요!!
오늘은 여담이 적고 이론이 많지 않았나여!? 저도 열씸히 포스팅하며 뿌듯뿌듯했는데... 아니었다면 죄송해여ㅜㅠ쭈굴...
갓승훈 선생님의 책에는 기본적인 컴퓨터 지식을 베이스로 깔고 가기 때문에 자료구조, 알고리즘, 운영체제와 같은 컴퓨터공학부가 배우는 이론 지식이 낯설 쑤가 이써여! 보통 OS 개발을 한다고 하면 컴퓨터 지식이 있는 사람이라고 생각하기 때문인지.. 저두 암것도 모르는뎅 ㅜㅠㅜ 우리 같이 공부 열씸히하면서 컴퓨터와 친해져보아여!!!
이번 구현의 마지막에는 바람개비인지 풍차인지 귀염귀염한 명령어를 구현하게 되는데, 멍청한 야미는 여기서도 이틀이 걸려써여... 그 이유는 바로!! 오타 아닌 오타 때문이예여!! 컴파일 에러도 없이 잘 돌아가는데, 이상하게 자꾸 createTask 명령만 하면 벡터 13번의 General Protection Fault가 뜨더라구여...
준비리스트를 추가하는 한 줄이 빠져서 그랬던것이었어여... 그 한 줄 찾는게 그렇게나 어려웠는지 ㅜㅠ 개발하다보면 이런 찾기 힘든 실쑤가... 자칫하면 디버깅 삽질을 할 뻔 했네여 T^T
이번 챕터까지는 무난히 구현하실 쑤 있으리라고 믿어여! 혹씨라도 문제가 발생하신다면 댓글로 남겨주세여!! 깃헙에 소스도 첨부해주시면 더더욱 감사하구영!! 그럼 우린 다음 챕터에서 라운드 로빈 스케줄러를 멀티레벨 큐 스케줄러로 업그레이드해보아여!! 이번 포스팅에서도 고생 많으셨씁니다~_~
Check out the yummyhit’s website for more info on who am i. If you have questions, you can ask them on E-mail.
댓글남기기