CS

알고리즘 - 프림 알고리즘(Prim Algorithm)

최소 비용 신장 트리를 구하는 알고리즘이다. 크루스칼 알고리즘은 간선을 기준으로 그래프를 생성하여 최소 비용 신장 트리를 구한다. 프림 알고리즘은 임의의 정점을 선택하며 가중치가 적은 노드를 선택해서 연결해주고 가중치를 업데이트 하는 과정을 반복해준다. 크루스칼 알고리즘은 간선을 기준으로 그래프를 구하는 반면 프림 알고리즘은 정점을 기준으로 최소 비용 신장 트리를 구한다. 노드 0을 선택한다. 노드 0을 선택하고 연결된 모든 노드의 거리를 살펴본다. 직접 이어지지 않은 노드의 거리는 inf(무한대)가 된다. 따라서 0과 연결된 1, 2, 3에 각각 4, 6, 5가 할당된다. 그 후 거리가 가장 짧은 노드를 선택한다. 1번 노드의 거리가 4므로 거리가 가장 짧으니 1번 노드가 선택된다. 그 후 1번 노드와..

알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용되는 알고리즘이다. 최소 신장 트리를 만들기 위한 알고리즘이다. 1. 모든 간선들을 오름차순으로 정렬한다. 2. 가중치가 가장 적은 간선을 추가한다. 3. 추가된 간선이 사이클을 만들면 삭제한다. 2~3번의 동작을 반복한다. 시간복잡도: O(m log m)

운영체제(OS) - 페이지 교체(Page Replacement)

프로세스를 사용하기 위해선 메모리에 올려야 한다. 그럼 언제 메모리에 가져다 놓는가? - Demand fetch(필요로 할 때 가져온다) - Anticipatory fetch(예상해서 가져온다) 메모리 빈 공간중 어디에 가져다 놓는가? - First-fit(첫 번째로 빈공간), Best-fit(필요한 공간과 크기가 비슷한 공간), Worst-fit(best의 반대, 가변 파티션이 가능한 조건에서) 교체가 발생할 때 무엇을 교체할 것인가? - 교체전략을 말한다. 디스크에서 데이터를 갖고 왔는데 메모리에 빈자리가 없을 경우 메모리를 점유하고 있는 것 중에서 누군가를 교체시켜야 한다. 이게 바로 replacement 문제이다. 메모리에서 쫓겨날것은 앞으로 잘 사용되지 않을 프로그램이 쫓겨나야 한다. 페이지 교..

운영체제(OS) - 가상메모리(Virtual Memory)

Overlay vs Virtual Memory Overlay 프로그램의 실행간에 메모리 관리를 프로그램이 직접한다. 어떤 데이터는 필요 없으니까 메모리에서 지우고, 필요한 데이터는 메모리로 가져오면서 필요한 부분씩 쪼개서 실행하는것. 게임이라면 게임이 메모리 관리를 직접하는데, 직접하게 만들기 위해선 프로그래머가 직접 개발 당시에 코딩한다. 게임을 만들 때 프로그래머가 직접 설계한다. 운영체제가 메모리 관리를 하지 않는다 Virtual Memory 프로그래머가 메모리 관리를 하지 않고 운영체제가 한다. 운영체제가 알아서 어떤 부분을 가져오고, 지운다. 하지만 한계점이 존재한다. 성능상의 최적화가 안될 수 있고 제대로 동작하지 않으면 성능이 안좋을 수 있다. MMU(Memory Management Unit..

운영체제(OS) - 메모리 관리(Basic Memory Management)

Real Memory(Real Storage) 실제 메모리(주 기억장치)라고도 한다. 메모리는 CPU와 상호작용을 통해 CPU는 메인메모리에 주소로 접근하면 CPU는 메모리에서 해당 주소에 위치한데이터를 가져온다. 주소의 개수 128M의 Ram이 있을 경우 M(메가바이트) = 2의 20승 128 = 2의 7승 2^20 * 2^7 = 2^27만큼의 주소 개수가 사용된다. 재배치 문제 a와 b는 개별 프로그램의 메모리구조이며 각 메모리마다 0~16380의 메모리 영역을 차지한다.. a를 실행하면 0번이 실행되고 24번으로 점프한 후 나머지가 실행되고 끝난다. b는 28번으로 점프해서CMP(비교)를 실행하고 프로그램이 끝난다. 이렇게 작성된 프로그램을 한개의 메모리에 적재를 시킨다. a가 낮은 주소 영역(흑색..

운영체제(OS) - 세마포어(Semaphore)와 뮤텍스(Mutex)

프로세스간 메시지를 전송하거나, 공유메모리를 통해 특정 데이터를 공유하게 되는 경우 문제가 발생한다. 즉, 공유된 자원에 여러 개의 프로세스가 동시에 접근 하면서 문제가 발생하는 것으로써 공유된 자원 속 하나의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한해 두어야 하는데, 이를 위하여 고안된 것이 바로 세마포어(Semaphore)다. 세마포어와 뮤텍스의 차이 - 세마포어(Semaphore): 공유 자원의 데이터 혹은 임계영역(Critical region)등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌.(동기화 대상이 하나 이상) - 뮤텍스(Mutex): 공유 자원의 데이터 혹은 임계영역(Critical region)등에 하나의 Process 혹은 Thread가 접근하는 것..

운영체제(OS) - 식사하는 철학자 문제(Dining Philosophers Problem)

식사하는 철학자 문제 철학자 다섯이서 원형 식탁에 둘러앉아 생각에 빠지다가, 배고플 땐 밥을 먹는다. 그들의 양쪽엔 각각 젓가락 한 짝씩 놓여있고, 밥을 먹으려 할 땐 다음의 과정을 따른다. 1. 왼쪽 젓가락부터 집어든다. 다른 철학자가 이미 왼쪽 젓가락을 쓰고 있다면 그가 내려놓을 때 까지 생각하며 대기한다. 2. 왼쪽을 들었으면 오른쪽 젓가락을 든다. 들 수 없다면 1번과 마찬가지로 들 수 있을 때까지 생각하며 대기한다. 3. 두 젓가락을 모두 들었다면 일정 시간동안 식사를 한다. 4. 식사를 마쳤으면 오른쪽 젓가락을 내려놓고, 그 다음 왼쪽 젓가락을 내려놓는다. 5. 다시 생각하다가 배고프면 1번으로 돌아간다. 발생할 수 있는 문제 식사하는 철학자 문제는 교착상태(Deadlock)의 대표적인 예제이..

운영체제(OS) - 스케줄링(Scheduling)

스케줄링은 프로세스가 생성되어 실행될 때 필요한 시스템의 여러 자원을 해당 프로세스에게 할당하는 작업이다. CPU는 한 번의 하나의 작업만 처리 가능한데, 여러개의 작업이 존재할 경우 해당 작업들이 번갈아 가면서 수행되도록 만드는 것을 스케쥴링이라고 한다. 프로세스가 실행되는 순서를 정해주는 작업이라고도 한다. 스케줄링 과정 1. 문맥교환(Context Switching) 문맥교환 "Context Switching에서 Context는 현재 프로세스에 사용되는 자원 혹은 개체들의 상태를 의미한다. Switching은 교환을 의미한다. CPU가 스케줄링에 따라서 프로세스들에게 CPU를 할당해 줄 때 1) 현재 CPU가 할당된 프로세스의 정보를 저장.(프로세스 테이블에 레지스터값과 메모리맵(참조비트)) 2) ..

운영체제(OS) - IPC(2)(Inter-Process Communication), ITC(Inter-Thread Communication)

race cindition을 피하기 위해 하드웨어 지원을 통한 Busy Waiting TSL(Test and Set Lock) TSL R, A 명령어를 사용한다. 메모리 A에서 레지스터 R로 값을 읽고 동시에 A에 0이 아닌 값을 저장한다. 프로그램 코드상 동시에 일어나기 때문에 스케쥴러에 의해 코드가 실행되다 cpu사용권을 넘겨주는 일은 발생하지 않는다. 실행 횟수 cpu memory 초기 0 0 실행 1 0 1 실행 2 1 1 0번 프로세스와 1번 프로세스가 있다고 가정한다면 0번 프로세스가 메모리의 0을 읽는다. 그럼 cpu의 레지스터엔 0이 읽히고 메모리는 1이된다. 그리고 1번 프로세스로 넘어가서 다시 메모리를 읽으려한다면 메모리엔 실제 값인 0이 아닌 1의 값을 읽게된다. 메모리의 값이 0이면..

알고리즘 - 퀵 정렬(Quick Sort)

퀵 정렬은 대표적인 분할 정복 알고리즘이다, 하지만 알고리즘이 수행되는 과정을 살펴보면 정복 후 분할하는 알고리즘이다. 피봇은 항상 요소의 가장 오른쪽 멤버가 되는 퀵정렬 1. 퀵 정렬의 아이디어는 피봇이라는 원소(숫자)를 정하고, 피봇보다 작은 숫자는 왼편으로, 피봇보다 큰 숫자는 오른편에 위치하도록하고, 피봇을 그 사이에 놓는다. 2. 피봇을 기준으로 작은쪽(왼쪽)과, 큰쪽(오른쪽)의 순서는 상관하지 않는다. 3. 피봇의 왼쪽엔 피봇으로 정한 수보다 작은수들만 모여있다. 순서X 4. 피봇 이전의 수를 기준으로 다시 수들을 정렬하고, 5. 피봇의 위치를 그 수들의 사이에 놓는다. 6. 1 ~ 5를 반복한다. 예) 7 2 5 1 3 4 피봇은 4가된다. 4보다 작은 애들을 왼쪽으로 몰아둔다. j가 4보다..