가전제품 이것저것 이야기

1. 상호배제를 위한 세마포 원리 및 코드

상호 배제의 기능을 수행한다.

< 원리 >

< 함수 내부 >

mutex가 양수이면 들어갈 수 있다.

S.value = mutex 이다.

0 또는 음수이면 사용중이라는 의미이다. (ex) -1이면 대기자가 1명이라는 뜻

wait(S)

S.value = -1이면

if문에 들어가서 add this process to S.L

즉, 진동벨을 나누어주고 다른 일을 수행할 수 있도록 한다.

signal(S)

수행이 끝나면 S.value 값을 1 올려준다.

그럼에도 아직 대기자가 남아있다면(즉, S.value가 0보다 작거나 같다면)

remove a process P from S.L;

wakeup(P);

즉, 아까 나눠줬던 진동벨을 울려 대기자들을 다시 불러온다.

2. 세마포의 장점

: 간단하게 구현된다.

3. 동기화 도구로써의 세마포

: 프로세들간에 실행 순서가 정해져 있을 때 사용한다.

: 세마포는 바쁜 대기를 유발하지 않는 동기화 도구이다. 

* 중요 *

0으로 초기화된 flag를 사용한다. 즉 mutex = 0; 으로 초기화

ex) A -> B 의 실행 순서가 지켜져야 할 때

flag = 0 이므로 Pj가 먼저 실행된다고 하더라도 wait 상태에 들어갈 것이다.

Pi에서 A가 실행되고 signal(flag);를 해서 flag를 1로 만들 때까지 절대 B를 실행할 수 없는 것이다.

4. 세마포의 문제점

: 세모포 변수를 여러 개 두고 실행할 경우 교착 상태와 기아 상태를 유발할 수 있다.

1) 교착 상태

: 둘 이상의 프로세스들이 대기중인 프로세스들 중 단지 하나에 의해서만 야기될 수 있는 사건을 무한정 기다리는 상황

2) 기아 상태

무한 정지, 프로세스들이 세마포 큐에서 제거되지 않고 무한정 대기하는 것

ex) flag가 1로 초기화된 경우

P0

wait(S)에서 flag가 0이 되고

wait(Q)에서도 flag가 0이 되어

기다리는 중

P1

wait(Q)에서 flag가 하나 더 감소하여 -1이 되고

wait(S)에서도  flag가 하나 더 감소하여 -1이 되어

기다리는 중....

-> 서로가 서로를 기다리느라 무한정 기다리는 상황에 빠지게 된다.

5. 고전적 동기화 문제 : 세마포로 해결해보기

* 초기화 : full = 0, empty = n, mutex = 1

-> full은 생산된 데이터의 개수, empty는 남은 버퍼의 개수

가운데에

wait(mutex);        wait(mutex);

...                          ...

signal(mutex);      signal(mutex);

는 상호배제를 위한 세마포를 구현한 것

생산자 위쪽 wait(empty);

소비자 아래쪽 signal(empty); 

는 생산자 동기화를 위한 세마포

생산자 아래쪽 signal(full);

소비자 위쪽 wait(full); 

는 소비자 동기화를 위한 세마포

6. Readers - Writers 문제

: 리더랑 라이터가 여러 명일 때

-> 라이터가 없을 때에는 리더가 여러 명이 들어갈 수 있다.

7. 모니터(Moniters)

: 세마포 연산자들을 한 데에 모아놓은 객체이다.

: 공통된 객체 내에서 활동하도록 보장한다.

: 오류 디버깅을 쉽게 할 수 있게 한다.

-> 많은 세마포 사용시, 잘못된 사용으로 오류가 발생하기 쉽기 때문에 사용한다.

* 정보처리기사 문제 *  

1. 프로세스들 간에 상호배제해야한다.
2. 임계 구역은 여러 사용자가 동시에 사용하지 않도록 하는것
3. 임계 영역 안에서의 작업은 신속히 이루어져야 함
4. 어떤 프로세스가 임계영역 내에서 실행중일때 인터럽트가 발생한다고

하더라도 이 프로세스는 실행을 멈추지 않는다.

    5. 임계영역에서 무결성을 보장한다.(값이 꼬이지 않음)

    6. 하드웨어 자원이 필요한 것 : Test&Set 명령어

1. 임계구역 또는 임계영역

: 한 순간에 한 프로세스만 사용할 수 있는 영역이다.

2. 진입 상호 배제 및 출구 상호 배제

: 프로세스 하나가 임계 영역에 있으면 다른 모든 프로세스는 임계영역으로의 진입을 금지한다.

3. 임계영역을 해결하기 위한 세 가지 만족 요건

1) 상호 배제

2) 진행 : 임계영역에 프로세스가 없을 때, 다음에 임계구역으로 진입하려는 프로세스의 진입을 미루면 안된다.

3) 한계 대기 : 한 프로세스가 임계영역 진입 요청을 한 후 수락되기까지 다른 프로세스가 임계영역에 진입할 수 있는 횟수를 제한해야 한다.

( 새치기 금지 )

4. 임계구역 SW 해결법 : 2개의 프로세스를 위한 임계구역 SW해결법

1) 알고리즘 1

critical section = counter ++ 하는 부분

-> 상호 배제는 충족하나, 진행을 만족하지 못해 실패한 알고리즘이다.

2) 알고리즘 2

-> 이 알고리즘 또한 상호 배제는 충족하나, 진행을 만족하지 못해 실패한 알고리즘이다.

3) 알고리즘 3 (피터슨의 해결안)

: 알고리즘 1, 2의 변수들을 결합한 아이디어

-> 모든 세 요건들을 충족한다.

-> 다만, 2개의 프로세스가 있을 경우만 해결할 수 있다.

5. 임계구역 SW 해결법 : N개의 프로세스를 위한 임계구역 SW해결법

- 램포트(Lamport)가 제안한 베이커리 알고리즘

-> 너무 복잡하여 배보다 배꼽이 큰 상황이 되었다.

결론) HW해결법은 실제로는 거의 사용되고 있지 않다.

6. 임계구역 HW 해결법

: 하드웨어 명령어를 이용한 임계영역 문제 해결

- TestAndSet() : 원소적으로 단어의 내용을 테스트하고 수정하는 명령

- Swap() : 원소적으로 두 변수를 바꾸는 명령

-> 한 원소가 다 끝날 때까지는 변경하지 않도록 한다.

-> 이 명령어에 대해서는 하드웨어가 다르게 작동하도록 한다.

알고리즘 해석 )

문이 잠겨있을 때, (lock = true)

lock이 true이면 반환값도 true이므로 

lock이 false가 될 때까지 while문을 반복한다.

문이 잠겨있지 않을 때, (lock = false)

lock이 false이면 while문을 돌지하지않고

빠져나간다. 이 때, lock은 false -> true가 된다.

그 후에 critical section을 실행하고 

false로 다시 변환된다.

-> 위의 TestAndSet 알고리즘과 동일한 원리이다.

차이점은 lock과 key를 바꾸는 것인데

문이 잠겨있지 않을 때 (lock = false)

lock이 false이면,

lock과 key가 바뀌면서

lock은 true, key는 false가 

되어 while문을 빠져나간다. -> critical section 실행하고(하는 동안은 lock이 true이므로 다른 프로세스가 진입하지 못한다)

끝난 뒤에 lock = false로 바꿔주어 다른 프로세스가 진입할 수 있도록 해준다.

- 임계구역에서는 인터럽트는 금지하여야 한다.

: 임계구역 내에서는 다른 일을 최소화하고 빠르게 출구 코드로 복귀해야 한다.

-임계구역으로 들어갈 때 바쁜 대기(Busy waiting)를 유발한다.

: 프로세스를 블록시키고 CPU를 다른 프로세스에 배정한다.

-> SW, HW 해결법은 바쁜 대기 문제를 해결하지 못했다.

1. 배경 : 병행 프로세스의 문제

1) 결정성 : 상대적인 실행 속도와 관계없이 항상 같은 결과를 도출하는지

-> 입력이 같으면 같은 결과가 나와야 한다. 병행 프로세스에서 순서가 꼬이면 다른 결과를 도출할 수도 있다.

2) 상호 배제와 동기화 

- 상호 배제 : 어떤 자원에 대해 한 번에 한 프로세스만이 접근가능

- 동기화 : 프로세스의 진행이 다른 프로세스에 의존

3) 교착 : 프로세스들이 서로 다른 프로세스가 점유한 자원을 요구하며, 아무도 진행되지 못하는 상태

2. 결정성

: 프로세스들 간의 실행 순서는 독립적 또는 선행 관계이다.

: 선행 관계의 경우, 선행 그래프로 표현 가능하다.

-> 프로세스별로 순서가 있으므로 그에 따라 진행하여야 한다.

3. 상호배제

: 특정 공유 자원을 한 순간에 한 개의 프로세스만이 사용할 수 있는 경우에

: 프로세스 하나가 공유 데이터에 접근해 있는 동안, 다른 프로세스가 접근할 수 없도록 하는 것

-> 교착 상태와 기아 상태가 발생하게하는 원인이다.

4. 동기화

: 빨리 끝나는 프로세스가 늦게 끝나는 프로세스를 어떻게 기다려줄지가 문제이다.

: 비동기 프로세스의 대기 시점을 결정한다.

5. 상호배제 및 동기화의 예시

- 제한 버퍼의 생산자/소비자 문제

6. 경쟁 상태 : 여러 프로세스가 공유 데이터에 동시에 접근할 때, 접근 순서에 따라 결과가 달라지는 상황

< 경쟁 상태를 위한 병행 프로세스들의 동기화 방법 >

1) 임계 영역 : 공유 변수를 어느 한 순간에 한 프로세스만 조작할 수 있도록 한다.

2) 상호 배제 : counter를 조작하는 부분을 임계영역으로 설정하여 상호 배제한다.

1. 기본 개념

: SQL문 안에 SQL문을 중첩하여 사용하는 질의이다.

: 다음과 같은 연산자와 함께 사용한다.

- in, not in

- =some, <some, >some, <=some, >=some, <>some

- =all, <all, <=all, >all, >=all, <>all

- exists, not exists

-> From , where 절에 위치할 수 있다.

2. IN / NOT IN

select title

from course

where course_id not in ('C301', 'C302', 'C401');

라고도 쓸 수 있다.

3. SOME / ALL

= SOME : 지정된 필드의 값이 부-질의 검색 결과에 존재하는 임의의 값과 같은지를 나타낸다. (IN과 같은 의미)

<= SOME : 지정된 필드의 값이 부-질의 검색 결과에 존재하는 임의의 값보다 작거나 같은지를 나타낸다.

= ALL : 지정된 필드의 값이 부-질의 검색 결과에 존재하는 모든 값과 같은지를 나타낸다. 

<= ALL : 지정된 필드의 값이 부-질의 검색 결과에 존재하는 모든 값보다 작거나 같은지를 나타낸다.

4. EXISTS / NOT EXISTS

exists : 최소한 한 개의 레코드가 존재하면 참이 되고 그렇지 않으면 거짓이 된다.

not exists : 부-질의의 결과에 레코드가 하나도 없으면 참이 되고, 하나라도 있으면 거짓이 된다.

[ 집합 연산 ]

1. UNION : 두 연산의 결과를 모두 출력한다.

-> 중복을 제거하고 출력한다.

만약) 중복을 제거하지 않고 출력하고 싶다면,

UNION ALL 연산자를 사용하면 된다.

2. INTERSECT : 두 연산결과의 교집합을 구한다.

3. MINUS : 앞의 연산결과에서 뒤의 연산결과를 제외하고 연산한다.

* 주의 *

select 하는 필드는 동일해야 한다.

[ 외부 조인 ]

두 테이블의 레코드에서 모두 존재하지 않더라도, 가져오고 싶을 때 사용한다.

1) 왼쪽 외부 조인 : 왼쪽에 있는 모든 레코드를 가져온다.

2) 오른쪽 외부 조인 : 오른쪽에 있는 모든 레코드를 가져온다.

3) 완전 외부 조인

[ 집계 함수 ]

- SELECT와 HAVING 절에서만 사용 가능하다.

- sum, avg는 숫자형 데이터 타입일 때만 사용 가능하다.

- NULL은 계산에서 제외된다.

1) COUNT

: 해당 필드에 값이 몇 개 있는지 출력한다.

2) SUM

3) AVG

4) MIN, MAX

1. GROUP BY

* 주의 *

group by절에 포함되지 않은 필드는 select 절에도 포함될 수 없다.

2. HAVING

: 그룹에 대한 조건을 명시할 때 사용한다.

1. 기본 구조

- From 절에서 department 테이블과 Student 테이블을 카티션 프로덕트한다.

- 밑의 관계대수와 같은 의미이다.

* 일반적으로 카티션 프로덕트 보다는 조인이나 자연 조인을 사용한다.

< 오라클에서 조인 사용법 >

1) SELECT s.name, d.dept_name

    FROM Student s, Department d

    WHERE s.dept_id = d.dept_id

         AND d.dept_name = '컴퓨터공학과';

2) SELECT s.name, d.dept_name 

    FROM Student s INNER JOIN Department d          <-- INNER 생략 가능

        ON (s.dept_id = d.dept_id)                            <-- () 생략 가능

    WHERE d.dept_name = '컴퓨터공학과';

3) SELECT s.name, d.dept_name

    FROM Student s INNER JOIN Department d          <-- INNER 생략 가능

        USING (dept_id)                                          <-- () 필요. 컬럼 앞에 alias 접두사 사용 불가 (s.dept_id X)

   WHERE d.dept_name = '컴퓨터공학과';

4) SELECT s.name, d.dept_name

    FROM Student s NATURAL JOIN Department d      <--  join 조건 생략

    WHERE d.dept_name = '컴퓨터공학과';

< 여러 개의 조건을 하고 싶을 때 >

1) SELECT s.name, d.dept_name, c.col_name 

    FROM (Student s JOIN Department d ON s.dept_id = d.dept_id)      <-- () 생략 가능                

                           JOIN Collage c  ON d.col_id = c.col_id           

    WHERE c.col_name = '정보과학대학';

2) SELECT s.name, d.dept_name, c.col_name 

    FROM Student s JOIN Department d  USING (dept_id)                       

                          JOIN Collage c  USING (col_id)           

    WHERE c.col_name = '정보과학대학';

2. 두 개 이상의 테이블이 포함된 질의

3. 레코드 정렬 : ORDER BY

-> 기본적으로 오름차순 정렬이다.

* 내림차순 정렬하려면 해당 필드명 뒤에 'desc'를 붙여주면 된다.

4. 재명명 연산

* 주의 *

특정 테이블에만 존재하는 변수의 테이블명은 생략 가능하다.

- 셀프 조인

- 필드의 재명명

5. LIKE 연산자

: 일부분만 일치하는 경우를 찾아야 할 때

< 문자열 패턴 >

_ : 임의의 한 개 문자에 대응

% : 임의의 여러 개 문자들에 대응