만족

리눅스 커널에서는 자체적으로 LinkedList를 제공한다. 여기에서 제공되는 LinkedList는 "원형 더블 링크드 리스트이다" 이...이게뭐노..? 이미지에서 볼 수 있듯이 각 노드는 head와 prev 포인터를 갖는다. //#include struct list_head{ struct list_head *prev, *next; } 엥? 각 노드에 데이터는 어디있나? 특이하게도 prev, next, data가 평면적으로 존재하는것이 아니라, data안에 prev,next 정보를 가진 구조체 변수가 존재한다. struct your_data{ struct list_head list; int data; } 그러니까 위의 Circular Doubly Linked List에서 각 노드마다 data가 같이 존재..

O 표기법 Big O 표기법이라고 읽는다. 알고리즘의 Time Complexity를 분석하는 데 가장 많이 쓰이는 표기법이다. O(g(n)) = { f(n) | 충분히 큰 n에 관해서 f(n)

Early Systems 메모리의 관점에서, 과거의 machine들은 사용자에게 abstraction을 제공하지 못했다. OS는 단순히 메모리의 0번지에 위치하는 library와 같은 routine의 집합체일 뿐이었다. 하나의 machine에서 하나의 program만이 실행가능했으며, 그 당시의 OS는 해야 할 일이 별로 없으니 당연스럽게도 매우 단순했었다. Multiprocessing and Time Sharing 당연히 사용자들은 한개의 machine에서도 한개만이 아닌 여러 가지 작업들을 동시에 처리하길 원했다. 그래서 Time Sharing이라는 개념이 이 때 생겨나게 되었다.(Time Sharing= 어떤 Computer Resource들을 여러 사용자들이나 프로세스들 간에 공유하는 것) 이 T..

우리 주변의 컴퓨터들을 보더라도, 대부분의 컴퓨터들은 듀얼코어 이상의 CPU를 사용하고 있다. 게다가, 요즘에는 일반 데스크탑 용도의 컴퓨터에도 6코어, 8코어 CPU를 사용하고 있으니,단순히 Single core에 대한 scheduling 뿐만 아니라 Multi core에 대한 Scheduling도 교려해야 한다. 먼저 Single Core 환경에 대해 간단히 살펴보면 (CPU - Cache) ------Memory 형태로 되어 있다 Cache는 Main Memory보다 용량은 작지만, 주요 data들을 모아 둔 작고 빠른 임시저장장치이다. 이 Cache를 이용함으로써 CPU와 Memory간의 다소 느린 속도를 보완해줄 수 있다. Cache는 다음과 같은 Idea에서 탄생하였다. 1. temporal ..

Overview 각각의 Level을 갖는 여러 개의 Queue가 존재하며, 새로운 Job이 도착하면 이 Queue 안에서 특정 규칙에 따라 우선순위가 변하면서 여러 가지 Job들 중에 하나를 선정해 실행하는 Scheduling 방법론이다. 아래는 기본적 특징이다. 여러 개의 Queue를 가지며, 각각의 Queue는 Priority를 가진다. 여러 개의 작업들 중, 어떤 작업을 선정하여 실행할 것인지를 결정하기 위해 Priority를 기준으로 사용한다. Job의 Priority는 계속해서 변하며, 그 작업이 CPU를 얼마나 점유하는지를 기반으로 결정된다.(오래 점유할수록 Priority는 밀려난다) Basic Rule 위와 같은 특성으로 보았을 때 우리는 기본적 규칙 몇 가지를 발견할 수 있다. 1. A의..

Modern Scheduling에 대해 알아보기 위해 몇 가지 사전 가정을 해보자. (실제로 그렇지 않다 하더라도) 1. 각각의 Job들은 모두 같은 시간동안 동작한다. 2. 모든 Job들은 같은 시간에 도착한다 3. 모든 Job들은 작업 시간동안 전부 CPU를 사용한다 4. 모든 Job들의 Running-Time은 알려져 있다. Scheduling Metrics 어떤 Scheduling 방법의 효율성을 측정하기 위한 몇 가지 지표가 있는데, 자주 사용되는 두 가지의 지표를 소개하겠다. 1. Turnaround Time Job Complete Time- arrived time in system으로 정의된다. Job이 System에 도착하고 나서 끝날 때 까지 얼마만큼의 시간이 지났는지를 나타내는 지표이다..

왜 Limited 되어야 하는가? Limited되지 않는다면, OS와 Program은 동등한 계층(hierarchy)를 갖는다. 따라서 OS는 Program을 감시하거나 동작을 제어할 수 없다. 만약 Program이 무한히 돌고 있다면(intended하든, unintended하든지간에), OS는 주도권을 갖을 수 없으며 멈추는 방법은 오로지 restart하나 뿐일 것이다. 또한 접근하지 않아야 할 영역에도 무차별적으로 접근하여 Process간 Protection이 전혀 존재하지 않는다. 따라서 OS가 다른 모든 process보다 높은 곳에서 process들을 관리하는 최상위 계층에 존재해서 이들을 제어할 수 있어야 한다. Limited Direct Execution Hardware는 OS에게 두 가지 e..

Process란 무엇인가? 간단히 말해, 실행중인 프로그램(running process)를 말한다. 잠깐 혼동할 수 있는 개념을 정리하자면 Program: Storage에 저장된 instruction들의 집합Process: Memory에 code, register, data등이 load되어 실행중인 ProgramProcessor: Process를 실행시키는 Hardware Overview: Multi-Process 여러 개의 작업을 실행시켰을 때, 마치 여러 개의 작업이 동시에 실행되는 것 처럼 보인다. 그러나 실제로는 한 번에 하나의 작업(one task at once time)을 실행시킨다. Time Sharing이라는 기법을 이용하여, 아주 짧은 시간마다 작업을 번갈아가면서 실행하기 때문에 마치 동..