Blog For Me

그래프 (Graph) 선형 자료구조나 트리 자료구조로 표현하기 어려운 多:多 의 관계를 지니는 원소들을 표현하기 위한 자료구조 그래프 G 객체를 나타내는 정점 Vertex와 객체를 연결하는 간선 edge의 집합 G = (V, E) V : 그래프에 있는 정점들의 집합 E : 정점을 연결하는 간선들의 집합 그래프의 예 : 버스나 지하철 노선도, 인스타그램의 following/follower 관계 지도 그래프의 종류 1. 무방향 그래프 (undirected graph) 두 정점을 연결하는 간선의 방향이 없는 그래프 정점 Vi와 정점 Vj를 연결하는 간선을 (Vi, Vj)로 표현 (Vi, Vj)와 (Vj, Vi)는 같은 간선을 의미 간선을 나타내는 정점의 쌍에는 순서가 존재하지 않는다. V(G) = {A, B,..

Deadlock Avoidance(교착상태 회피) 교착상태 회피는 교착상태에 빠질 가능성이 있는지 없는지를 운영체제가 검사하고 빠질 가능성이 없을 경우에만 자원을 할당하여 문제 발생을 피하는 방법이다. 우선 이를 판단하기 위해 상태를 안전 상태와 불안전 상태로 나누고, 운영체제는 안정상태를 유지할 수 있는 요구만 수락하고, 나머지 요구들은 안전상태를 만족할 때까지 계속 거절한다. 여기서 은행을 예로 들어보겠다. 100원을 가지고 있는 은행이 있고, 그 은행으로부터 돈을 빌리려는 3명의 고객이 있다. 고객은 필요한 돈이 있어야만 일을 해결할 수 있고, 빌린 돈을 상환할 수 있다. 이를 테면, 30원이 필요한 상황인데 수중에 20원만 있으면 일을 해결하지 못하고 돈을 다시 갚지도 못한다. 고객 1은 60원,..

1. 교착 상태(Dead lock) 한정된 자원을 여러 곳에서 사용하려고 할 때 발생하는 문제 프로세스가 공유 자원을 얻지 못하여 다음 작업을 처리하지 못하는 상황 프로세스 1과 프로세스 2가 모두 자원 A, 자원 B를 얻어야 한다고 할 때, 우선 프로세스 1은 자원 A를 얻었고 프로세스 2는 자원 B를 얻은 상태이다. 그리고 그 상황에서 프로세스 1은 자원 B를 기다리고, 프로세스 2는 자원 A를 기다리고 있다. 여기서 현재 서로 원하는 자원이 상대방에게 할당되어 있어 두 프로세스는 무한정 wait 상태에 빠지게 되고 이러한 상황을 deadlock(교착 상태)라 한다. 2. 교착 상태 발생 조건 교착 상태는 4가지 조건이 동시에 성립할 때 발생한다. 4가지 조건 중 하나라도 성립하지 않으면 교착 상태 ..

The Dining Philisophers Problem(식사하는 철학자 문제) 출처: Operating System Concepts tenth Edition, Abraham Silberschatz, Peter Baer Galvin, Greg Gagne 철학자 다섯 명이 원형 테이블에서 식사를 하려고 한다. 테이블 중앙에 음식이 있고, 다섯 개의 젓가락이 철학자 사이에 놓여 있다. 철학자가 배고파서 음식을 먹으려 할때 자신의 왼쪽과 오른쪽 젓가락을 잡으려고 하고, 두 젓가락을 잡아야 식사가 가능하다. 이후 식사가 끝나면 젓가락 두 개를 테이블에 놓고 다시 생각에 빠지는 상황이다. 철학자 문제 알고리즘은 다음과 같다. while(true) { wait(chopstick[i]); // 왼쪽 젓가락 집기 wa..

1. The Bounded-Buffer Problem 여기에서는 두 종류의 프로세스가 있는데, 하나는 Producer 프로세스, 또 다른 하나는 Consumer 프로세스이다. 즉, 이는 생산자-소비자 문제(Producer-Consumer Problem)이라고도 불린다. Producer 프로세스는 데이터를 만들어 버퍼에 삽입하고, Consumer 프로세스는 버퍼에서 데이터를 꺼내는 역할을 수행한다. 여기서 발생할 수 있는 문제점은 어느 생산자 프로세스가 버퍼 중 빈 곳에 데이터를 쓰려고 할때, Interrupt가 발생하여 다른 프로세스한테 공유자원이 넘어가서 다른 프로세스가 해당하는 빈 곳에 데이터를 쓸 때 나타날 수 있다. 그렇게 되면 둘 중에 한 프로세스의 데이터가 유실될 수 있을 가능성이 농후하기 때..

최근에 lock 방법이 지닌 문제점을 해결하기 위하여 소프트웨어적 방법을 이용하기보다는 더 이상 쪼개지지 않는 원자적 명령어로 구현하거나 Interrupt 제어로 해결한다. 하드웨어 명령어 lock 함수 코드부분 void lock(struct lock *i) { while(i->held); i->held=1; } 이 lock 함수의 문제점은 A 프로세스가 2번 라인의 코드를 실행하고 다음에 3번 라인의 코드를 실행하기 직전에 Interrupt 걸렸을 상황에서 두드러진다. 즉, A 프로세스가 3번 코드인 'i->held=1'을 실행하기 직전에 Interrupt 걸려서 B 프로세스로 전환된 것이다. 그럼 B 프로세스는 아직 held 값이 0인 걸 보고 바로 임계영역에 진입해버리므로 Race Condition..