자신에 대한 고찰

지금까지 계속 다룬 걸 보면 계속 Scheduling에 대한 내용에는 항상 Timing Value에 관한 것이 포함되어 있다. 우리가 이 값들을 미리 알고 해당 Task에 대한 Scheduling을 할 수 있다면 그보다 더 나은 System은 없을 것이다. 그런데 이걸 매 Timing 때마다 고려를 하자니 여기에 소모되는 Resource가 낭비된다고 생각할 수 있다. 그래서 해 볼 수 있는 생각이 한계를 정해두고 한계를 넘지 않는 한은 계속 용인하고 한계를 넘는 것에 대해서만 다른 처리를 할 수 있는 구조를 택하자는 것이고, 그 한계를 Worst Case일 때의 한계로 정해보자는 것이다. 이번 포스트에서 소개하는 Worst Case Execution Time은 말 그대로 Execution Time 중에서..

지금까지 계속 EDF와 RM의 Optimality 혹은 Schedulability를 확인하는 내용을 다뤘었다. 그런데 사실 이렇게 구한 값들이 실제 케이스상에서도 적용할 수 있는 값일까 하는 의문을 가질 수 있다. 만약 그게 가능하다면 앞으로 Task Scheduler를 설계할 때는 이미 구해놓은 utilization이나 Release Time만을 활용하면 쉽게 설계할 수 있다. 하지만 공학을 설계한 사람이라면 누구나 알다시피 이론과 실제 케이스는 너무나 큰 차이를 나타낸다. 이론에 나온 것은 단순히 실제 케이스들 중에서 제한 사항을 엄격히 설정한, 아주 특이한 케이스 인 것이다. 실제로 이전의 EDF나 RM의 Optimality를 측정할 때도 언급하지는 않았지만 우리는 무언의 제한을 두고 있던 것과 같..

지난 포스트에서 이야기 했던 것처럼 N개의 Task에 대해서 Utilization를 측정하는 것이 어렵기 때문에 이에 대안적인 방안으로 Time Demand Analysis를 쓸 수 있다고 했다. 간단히 요약하자면 각 Task의 Response Time을 측정해서 그때의 Time Supply보다 큰가 작은가를 비교하면 Schedulability 를 얻을 수 있다는 것이다. 그런데 아마 Time Demand Analysis에 대해서 기억하는 사람이 있다면 이 접근 방식의 문제를 알고 있을 것이다. 바로 모든 Case에 대해서 다 구해야 한다는 것, 매 period마다 Schedulability를 측정하기 위해서는 response time을 재야 하고 이를 위해서는 무한적으로 측정해야 한다는 답이 나온다. ..

지난 포스트를 통해서 Rate Monotonic Algorithm을 사용한 Schedule의 Minimum Utilization이 0.69 이고 이걸 LL Bound라고 했다. 이번 포스트에서는 Earliest Deadline First의 Schedulability를 보고자 한다. 아무튼 우리가 알고 있는 것은 해당 Task 들의 Schedulability를 측정하기 위해서는 각각의 Task에 대한 Utilization을 구해야 되고 그 중에서 가장 작은 Utilization Bound를 찾아야 한다. 이게 결국은 Utilization Bound Check의 간략한 진행 방법이다.그러면 Utilization 자체는 Execution Time / Period 의 합이므로 EDF의 Utilization은 다..

대학원이 참 빡세긴 하네요. 학교 과제하랴. 복습하랴.. 또 프로젝트 하랴.. 앞으로도 어떻게 될지는 모르겠지만 그래도 조금씩 마음으로나마 여유를 가져보려고 합니다. 이번 기회에 읽어본 책은 "OpenCL 프로그래밍"이라는 책입니다. 사실 OpenCL이 뭔지 그냥 감만 잡힌 상태였고, 병렬처리를 어떤식으로 프로그래밍하는지 궁금해서 이 책을 선택하게 되었습니다. 그런데 사전에 전제를 해야 될 부분이 꼭 병렬 처리를 써야 한다. 코드를 통해서 프로그래밍 예제가 어떤식으로 구성되어 있는지를 확인하시려는 분한테는 큰 도움이 될만한 책입니다. 하지만 단순히 흥미 거리로 OpenCL이 뭔지 알고 싶다. 병렬처리 프로그램이 어떤식으로 동작하고 그림과 쉬운 설명이 들어간 걸 원하시는 분은 이 책을 피하시는 게 좋을 것..

ubuntu를 처음 접하는 사람은 터미널을 열어보면 윈도우의 GUI와는 다르게 이쁜 색과 깔끔한 인터페이스 때문에 터미널이 이뻐 보인다.그런데 막상 ls 명령어를 통해서 파일을 쭉 나열해보면 각각의 파일 색상이 뭘 나타내는지 의문이 들때가 발생할 것이다. 사실 이부분은 dir_colors 라는 file format에 정의되어 있다. 자세한 내용을 확인하려면 terminal에서 man dir_colors 라고 치면 된다.그러면 dir_color로 정의할 수 있는 색상과 default 시 나타내는 색상에 대한 정보를 얻을 수 있다. r그런데 위의 경우는 default의 경우일 뿐 실제 터미널에서 확인해보면 결과가 약간 다르게 나온다. 이때는 직접 setting을 확인해보면 된다. chans@chans: ~$..

과제로 Compiler의 Lexcial Analysis를 담당하는 Scanner와 Parser를 만드는 것이 목적이다. 원래는 전반적인 부분을 모두 코딩하는 게 맞지만 교수님이 Grammar Specification을 미리 지정해줘서 그 것에 맞춰서 작성하면 된다.우선은 Scanner를 만들었는데 Scanner의 역할은 코드 내의 Token이 어디에 속하는지를 분류해주는 역할을 한다. 보통 test code로 다음과 같이 제공된다. 그러면 Scanner는 한 character씩 읽어나가면서 해당 구문이 어디에 속하는지를 화면상으로 보여줘야 한다. 유의할 점이 있다면 간혹 예외적인 구문이 있다는 것이다.그냥 character 별로 구분하는 거면 switch 구문을 사용해서 해당 character를 분별해내..

계속해서 shift reduce Parsing에 대해 다뤄보고 있다. 지난 포스트에서 소개한 건 현재 주어진 Production을 통해서 DFA를 구하는 LR(0) Parsing이었다. 잠시만 Rewind해보자 사실 이 건 정확한 답이라고 할 수 없다. 그때도 언급했었지만 효율적인 algorithm이라는 건 없고, heuristic을 활용해서 전개하는 방식이 위와 같은 건데 갑자기 왠 헛소리냐라고 생각할 수 있다. 그런데 우리가 간과한게 있으니 바로 conflict라는 것이다. Shift Reduce Parsing에서는 두가지 conflict가 있는데 하나는 Reduce-Reduce conflict 이고 다른 하나는 Shift-Reduce Conflict이다. 가령 다음과 같은 item이 있다고 가정해보..

드디어 500번째 글입니다. 사실 블로그를 통해서 많은 글들을 남겼습니다. 그게 누구한테는 그저 하찮은 자료일 수도 있었고, 혹은 틀린 사실을 담고 있었을지도 모릅니다. 하지만 아무것도 없는 허허벌판에서 무언가를 찾는 사람들에게 같은 주제와 관심사를 가진 글이 있다면 도움이 안될지는 몰라도 힘이라도 될거 같아서 글을 쭉 올리고 있습니다. 뭐 500번째 글이 넘었다고 해서 특별한 이벤트도 없고, 기념거리도 없습니다만. 저한테는 그래도 나름의 뿌듯함이 듭니다. 이 블로그를 본격적으로 시작한 게 11년 10월 경에 Windows phone 연재를 하면서였는데 그동안 500개의 글을 썼다는 건 그래도 거의 하루에 하나의 글을 썼다는 의미일 겁니다. 그래서 누구한테 보이지는 않더라도 저자신한테는 꾸준했다는 것 자..

지난 포스트에 이어서 Shift Reduce Parsing에 대해서 조금더 이야기 해보도록 하겠다. 어차피 Shift Reduce 방식도 전형적인 Bottom Up Parsing 중 하나이므로 substring에 대한 handle이 존재할 것이고, 그 handle로부터 pruning을 해나가면서 최종적으로 root node를 찾아나가는 것이 목적이다. 그런데 문제는 input string 중에서 어떤 걸 handle이라고 정의할 것이냐는 것이다. 지금 우리가 다루고 있는 내용은 지난 포스트 중에서 나왔지만 Context Free Grammar(CFG)를 바탕으로 설명되고 있다. 사실 가장 이상적인 Parsing이라면 한번에 handle을 인식하고 그에 따른 terminal string으로 바꿔주는 건데 ..

이번 포스트에서는 Bottom Up Parsing으로 해결하는 방법 중 하나인 Shift Reduce Parsing에 대해서 정리해보겠다. 일단 지난 포스트에서 잠깐 다룬 것처럼 Bottom Up Parsing을 하기 위해서는 일종의 Handle, 즉 Production의 반대 개념인 Reduction을 적용할 substring을 찾는 과정이 필요했고, 이걸 마지막에 Handle Pruning이라고 했다. 그런데 한번 생각을 해보자. 어차피 substring으로 나누는 건데 reduction을 한 나머지도 일종의 substring이 아닐까? 물론 그게 정확한 terminal이다 라고는 말 못하지만 아무튼 진짜 terminal일 수도 있고, 혹은 Nonterminal과 Terminal로 결합으로 구성되어 ..

이번에 다룰 내용은 Bottom up Approach를 통해서 Parsing하는 Bottom up Parsing이다. 말 그대로 아래에서 위로, leaves에서 root를 찾아가는 방식이다. 그런데 사실 다른 compiler의 내부 구조는 거진 Top Down이 아닌 Bottom up 방식으로 구현되어 있다. 사실 Top Down 방식에서 직관적으로 봤을 때 가장 풀기 어려웠던 점이 무엇인지를 생각해보자. 개인적으로 생각했을 때는 absolute한 path를 찾는데 시간이 많이 걸린다는 것이다. grammar라는게 가지치기를 통해서 여러 방향으로 뻗어나갈 수 있는 건데 Top Down 방식에서는 선택이 맞는지 틀린지를 직접 해보고 path를 결정할 수 있는 것이다. 또한 중간 결과가 맞았다고 해서 최종 ..

이번 포스트에서 다뤄볼 내용은 지난 포스트에서 언급했던 backtracking을 완전히 배제한 Predictive Parsing이다. 말 그대로 한단계 이후의 결과를 미리 예상하고 parsing path를 정하기 때문에 틀린 결과로 인한 backtracking을 할 필요가 없어진다. 보통 이런 개념을 lookahead라고 하고 몇단계를 미리 예상할 것이냐에 따라서 정도가 달라진다. 물론 그 depth가 커지면 그만큼 컴파일러의 성능도 나빠질 것이다. 그래서 일반적으로는 이 lookahead의 정도를 1로 둔다. 참고로 이런 Top Down parsing방식은 지난 포스트에서도 언급했었지만 왼쪽에서 오른쪽으로 가면서 분석하고(left-to-right) 왼쪽부터 derivation을 수행하기 때문에(left..

지난 포스트에서 Abstract Syntax Tree 즉, derivation을 생략한 필수적인 정보만 남긴 Tree를 정리했었고, 이걸 지금까지 하고 있는 Top Down Parsing에 적용해보는 것을 이번 포스트에서 정리해보려고 한다. Top Down Parsing이라는 것은 말 그대로 Tree의 맨 위에서부터 차례대로 Parsing한다는 의미를 가지고 있다. 그런데 우리가 보기 쉽게 Tree 형식으로 만들어놓는 것이지, 실제로 compiler가 볼때는 왼쪽에서 오른쪽으로 차례대로 string을 검색하는 형식을 취한다. 그 때 이걸 left Recursive라고 언급했었고, 바로 이런 방식때문에 Top Down Parsing을 Recursive Descent Parsing이라고 하기도 한다. 보통 ..

계속 이어서 Utilization Bound Check을 다뤄보려고 한다. 일단 간단히 요약하자면 우리는 task들을 보면서 해당 task의 execution time과 period를 구할 수 있다. 이를 바탕으로 Utilization이라는 것을 구할 수 있었는데 System내에서도 task가 여러 개이기 때문에 Utilization들을 모두 합친 Total Utilization을 얻을 수 있을 것이다. 이 값과 Scheduling algorithm을 적용한 후의 Utilization의 최소값, 즉 Utilization Bound와 비교를 통해서 Schedulability를 측정하는 방식이 지난 포스트에 언급한 Utilization Bound Check의 내용이었다. 그래서 이번에는 실례를 통해서 다시 ..