Algorithm

재귀 사용하는 패턴

단순 반복문

• 반복문으로 구현했을 때보다 이점이 되는 부분이 없음

• Call Stack에 공간을 많이 차지해 성능이 반복문보다 좋지 않다.

하향식 계산

• 하향식 계산 : 하위문제의 결과를 기반으로 현재 문제를 계산하는 방식

  • 재귀가 반복문보다 성능이 좋은 경우

  • 큰 문제를 해결하기 위해 작은 재귀 함수를 호출한다.

  • 재귀를 사용해서만 구현이 가능하다.

• 상향식 계산 : 하위 문제를 모아서 현재 문제를 계산하는 방식

  • 반복문으로 구현한 것보다 성능이 좋지 않음

  • 반복문이나 재귀를 사용해서 구현할 수 있다.

OS

Process간 통신

• 하나의 컴퓨터 내에서 프로세스간 통신하는 방법

Pipe

• 운영체제가 생성한 파이프를 이용해 데이터를 읽고 쓰는 방법

File

• 통신을 하려는 프로세스들이 하나의 파일을 이용해 읽고 쓰는 방법

Thread를 이용한 통신

• 하나의 프로세스 내에서 쓰레드간 통신하는 방법

• 쓰레드는 코드, 데이터, 힙 영역을 공유한다.
  (스택 영역만 별도로 갖는다.)

• 데이터 영역의 전역 변수나 힙 영역을 이용하여 통신할 수 있다.

Network

• OS가 제공하는 Socket 통신

• RPC(Remote Procedure Call)

  • 다른 컴퓨터의 함수를 호출하는 방법

공유자원과 임계구역

• 공유자원 : 프로세스간 통신을 할 때 공용으로 이용하는 변수나 파일

  • 여러 프로세스가 공유하기 때문에 각 프로세스의 접근 순서에 따라서 결과가 달라질 수 있다.

  • 컨텍스트 스위칭으로 시분할 처리를 하기 때문에 프로세스간의 실행 순서를 예측하기 어렵다.
    ⇒ 동기화 문제가 발생할 수 있다.

• 임계규역 : 여러 프로세스가 동시에 사용하면 안되는 영역

  • 상호배제 메커니즘을 통해 해결할 수 있다.

• 경쟁조건 : 공유자원을 사용하기 위해 서로 경쟁하는 것

상호배제 요구사항

1. 임계영역엔 동시에 하나의 프로세스만 접근한다.

2. 여러 요청에도 하나의 프로세스의 접근만 허용한다.

3. 임계구역에 들어간 프로세스는 빠르게 나와야한다.

Semaphore

• 상호배제 메커니즘의 한 종류

• Semaphore :  정수 값을 가지는 변수로, 공유 자원에 접근할 수 있는 프로세스/스레드의 수를 나타낸다.

• 세마포어를 갖고 있는 프로세스가 실행되고 세마포어를 반납한다.

기본 연산

• wait(S): 세마포어 값을 감소시킨다.

  • 값이 0이면 프로세스/스레드를 대기 상태로 만든다.

• signal(S): 세마포어 값을 증가시킵니다.

  • 대기 중인 프로세스/스레드가 있다면 깨운다.

종류

• 이진 세마포어: 0과 1 두 가지 값만 갖는다.
  (뮤텍스와 유사하게 사용한다.)

• 카운팅 세마포어: 0 이상의 정수 값을 갖는다.
  (여러 자원을 관리할 때 사용된다.)

장단점

• 장점: 여러 프로세스/스레드 간의 복잡한 동기화 문제를 해결할 수 있다.

• 단점

  • 잘못 사용하면 교착 상태나 기아 상태를 유발할 수 있다.
    ex) 세마포어를 획득하는 함수와 세마포어를 반납하는 함수의 위치 잘못 사용

Mutex(MUTual EXclusion)

• 뮤텍스는 이진 세마포어의 특수한 경우

• 여러 스레드가 공유 자원에 동시에 접근하는 것을 방지하는 기술

기본 연산

• Lock: 스레드가 임계 영역에 진입할 권한을 획득

• Unlock: 임계 영역 사용을 마치고 다른 스레드가 진입할 수 있게 한다.

뮤텍스와의 차이

• 세마포어는 여러 프로세스/스레드의 접근을 허용할 수 있지만, 뮤텍스는 하나의 프로세스/스레드만 접근을 허용한다.

Monitor

• 세마포어의 단점을 보완한 상호배제 메커니즘

• OS가 처리하는 것이 아니라 프로그래밍 언어단에서 지원하는 기능
  ex) Java : synchronized 키워드

• 한 번에 하나의 프로세스/스레드만 실행할 수 있다.