CS : 스레드 / 멀티 스레딩 / 동시성 / 공유 자원 / race condition / critical section / CPU 스케쥴링 알고리즘

스레드?

프로세스의 실행가능한 가장 작은 단위입니다. 프로세스는 여러 스레드를 가집니다.  코드 데이터 스택 힙을 각각 생성하는 프로세스와는 달리 스레드는 코드, 데이터, 힙은 스레드끼리 서로 공유합니다. 그 외 영역(스택, 스레드 상태)은 각각 생성됩니다

 

동시성?

서로 독립적인 작업들을 작은 단위로 나누고 동시에 실행되는 것처럼 보여주는것

 

멀티 스레딩

프로세스 내 작업을 여러개의 스레드로 처리는 기법이며, 스레드끼리는 서로 자원을 공유하기 때문에 효율성이 높습니다.  예로 웹 요청을 처리할때 새 프로세스를 생성하는 대신 스레드를 사용하는 웹 서버는 훨씬 적은 리소스를 소비하며, 한 스레드가 중단되어도(blocked) 다른 스레드는 실행 상태(running)일 수 있기 때문에 중단되지 않은 빠른 처리가 가능합니다.  또한 동시성에도 큰 장점이 있습니다..  하지만 한 스레드가 문제가 생기면 다른 스레드에도 영향을 끼쳐 스레드로 이루어져 있는 프로세스에 영향을 줄 수 있는 단점이 있습니다

 

멀티스레드의 웹 브라우저의 예는?

렌더러 프로세스를 들 수 있습니다 메인 스레드 워커 스레드 레이어를 합성하는 컴포지터 스레드 화면을 픽셀로 변환하는 레스터 스레드 등이 존재합니다  렌더러 = 메워컴레

공유 자원에 대해 알려줘

공유 자원은 시스템 안에서 각 프로세스, 스레드가 함께 접근할 수 있는 모니터, 프린터, 메모리, 파일, 데이터 등의 자원이나 변수 등을 의미합니다.

race condition?>

공유 자원을 두 개 이상의 프로세스가(스레드 X) 동시에 읽거나 쓰는 상황을 경쟁 상태라고 합니다.  동시에 접근했을때 접근의 타이밍이나 순서 등이 결과값에 영향을 줄 수 있는 상태입니다.

 

임계 영역?

critical section, 임계 영역은 둘 이상의 프로세스나 스레드가 공유 자원에 접근할 때 순서 등의 이유로 결과가 달라지는 코드 영역을 말합니다.

critical section을 해결하기 위한 방법을 3가지 말하라

뮤텍스 세마포어 모니터

각 방법의 조건들은?

lock 메커니즘을 기반합니다.  상호 배제(mutual exclustion) 한정 대기(bounded waiting) 융퉁성(progress) 이 있으며,  한 프로세스가 임계 영역에 들어갔을 때 다른 프로세스는 들어갈 수 없습니다. 특정 프로세스가 영원히 임계 영역에 들어가지 못하면 안됩니다. 만약 어떤 프로세스도 임계 영역을 사용하지 않는다면 임계 영역 외부의 어떠한 프로세스도 들어갈 수 없으며, 이 때 프로세스끼리 서로 방해하지 않습니다.

mutex

프로세스나 스레드가 공유 자원을 lock()을 통해 잠금 설정 사용 후에 unlock()을 통해 잠금 해제하는 객체입니다.  뮤텍스는 잠금 or 잠금 해제라는 상태만을 가집니다.

semaphore

세마포어는 일반화된 뮤텍스입니다.  간단한 정수 값과 두 가지 함수 : wait(P) / signal(V)로 공유 자원에 대한 접근을 처리합니다.  wait()는 자신의 차례가 올 때까지 기다리는 함수이며, signal()은 다음 프로세스로 순서를 넘겨주는 함수입니다.

자원을 공유하는 프로세스들이 세마포어를 가지고 하는 플로우를 설명해주세요

프로세스나 스레드가 공유 자원에 접근하면 세마포어에서 wait() 작업을 수행하고,  프로세스나 스레드가 공유 자원을 해제하면 세마포어에서 signal() 작업을 수행합니다.  세마포어에는 조건 변수가 없고 프로세스나 스레드가 세마포어 값을 수정할 때 다른 프로세스나 스레드는 동시에 세마포어 값을 수정할 수 없습니다.

세마포어 키워드

스레드 -> signal -> 세마포어 값 수정

바이너리 세마포어?>

0과 1 두 가지 값만 가질 수 있는 세마포어입니다.  구현의 유사성으로 인해 뮤텍스는 바이너리 세마포어라고 할 수 있지만 엄밀히 말하면 뮤텍스는 잠금을 기반으로 상호배제가 일어나는 '잠금 메커니즘'이고.  세마포어는 시그널 기반의 '신호 메커니즘' 입니다.  여기서 신호 메커니즘은 휴대폰에서 노래를 듣다가 친구로부터 전화가 오면 노래가 중지되고, 통화 처리 작업에 관한 인터페이스가 등장하는 것을 상상면 됩니다.  :  바이너리 0.,1 세마포어 그대로 읽기

카운팅 세마포어

카운팅 세마포어는 여러 개의 값을 가질 수 있는 세마포어이며, 여러 자원에 대한 접근을 제어하는 데 사용됩니다.  counting = 여러개

 

모니터?

모니터는 둘 이상의 스레드나 프로세스가 공유 자원에 안전하게 접근할 수 있도록 공유 자원을 숨기고 해당 접근에 대해 인터페이스만 제공합니다.  모니터는 모니터QUEUE를 통해 공유 자원에 대한 작업들을 순차적으로 처리합니다.  모니터는 세마포어보다 구현하기 쉬우며 모니터에서 상호 배제는 자동인 반면,  세마포어에서는 상호 배제를 명시적으로 구현해야 하는 차이점이 있습니다.

 

deadlock에 대해 알려주세요

교착 상태는 두 개 이상의 프로세스들이 서로가 가진 자원을 기다리며 중단된 상태를 의미합니다.  예를 들어 프로세스 A가 프로세스B의 어떤 자원을 요청할떄 B도 A가 점유하고 있는 자원을 요청하는 것이죠.

그럼 데드락의 원인에 대해 알려주세요

데드락은 상호 배제, 점유 대기, 비선점. 환형 대기로 유발됩니다.  

 

상호 배제 : 한 프로세스가 자원을 독점하고 있으며 다른  프로세스는 접근이 불가합니다. 

점유 대기 : 특정 프로세스가 점유한 자원을 다른 프로세스가 요청하는 상태입니다. 

비선점 : 다른 프로세스의 자원을 강제적으로 가져올 수 없습니다. 

환형 대기 : 서로의 자원 요구

데드락의 해결 방법?

교착 상태는 매우 드물게 일어나기 때문에 이를 처리하는 비용이 더 커서 상태 발생시 사실 사용자가 작업을 강제 종료하는 편이 낫습니다. 작업 관리자-응답없음  자원을 할당할때 애초에 조건이 성립되지 않도록 설계합니다.  

교착 상태 가능성이 없을때만 자우너 할당하며, 프로세스당 요청할 자원의 최대치를 통해 할당 가능 여부를 파악하는 은행원 알고리즘을 씁니다.  교착 상태가 발생하면 사이클이 있는지 찾아보고 이에 관련된 프로세스를 한 개씩 지웁니다.

 

은행원 알고리즘?

총 자원의 양과 현재 할당한 자원의 양을 기준으로 안정 또는 불안정 상태로 나누고 안정 상태로 가도록 자원을 할당하는 알고리즘  은행원은 보험 : 안정 / 불안정

 

0 : CPU 스케쥴링 알고리즘?

CPU 스케쥴러는 CPU 스케쥴링 알고리즘에 따라 일을 스레드 단위로 CPU에 할당합니다.  프로그램이 실행될 떄는 CPU 스케쥴링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정합니다.

1 : CPU 알고리즘의 방향성?

CPU 이용률은 높게,  주어진 단위시간당 많은 일을 하게, 준비 큐(ready queue) 에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 합니다.

2 : CPU 스케쥴링 알고리즘의 종류를 나눌 수 있나>

비선점형과 선점형이 각각 3개씩 있으며. 

비선점형은 : FCFS / SJF / 우선순위 

선점형은 : 라운드로빈 / SRF / 다단계 QUEUE가 있습니다.

비선점형 방식(non-preemptive)이란?

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않습니다.  따라서 컨텍스트 스위칭으로 인한 부하가 적습니다.

FCFS란?

first come first served는 가장 먼저 온 것을 가장 먼저 처리하는 알고리즘입니다. 길게 수행되는 프로세스 떄문에 준비 큐에서 오래 기다리는 현상(convey effect)가 발생하는 단점이 있습니다.

SJF는?

Shortest Job First는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘입니다.  

긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며, 평균 대기 시간이 가장 짧습니다.  하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용합니다.

우선순위

비선점 스케쥴링 알고리즘 3가지 중 한 방식입니다.  기존 shortest job first는 starvation이 일어나기 때문에 오래된 작업일수록 우선순위를 높이는 방법(aging)을 사용해 보완한 알고리즘입니다.

우선순위는 우선순위 알고리즘만 하나?

우선순위는 SJF와 우선순위를 말하는 것 뿐 아니라 FCFS를 활용하여 만들기도 합니다.  선점형 비선점형적인 우선순위 스케쥴링 알고리즘을 말하기도 합니다.

선점형 방식은 무엇인가요?

preemtive는 현대 운영체제가 쓰이는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고  강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말합니다.  *날카로운 선으로 끊어버린다.

라운드 로빈?

RR은 현대 컴퓨터가 쓰는 선점형 알고리즘 스케쥴링 방법으로,  각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 ready queue(준비 큐)에 뒤에 줄을 서는 알고리즘입니다.  로드밸런서의 트래픽 분산 알고리즘으로도 쓰입니다.  rr 사전 : 토너먼트 / 여러 명이서 돌려쓰는 이야기

할당 시간에 관한 RR에 대한 추가 설명

할당 시간을 잘 짜야 합니다.  q만큼의 할당 시간이 부여되었고, n개의 프로세스가 운영중이라고 하면 (n-1)*q 시간이 지나면 자기 차례가 오게 됩니다.  할당 시간이 너무 크면 사실상 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커집니다.   일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간을 짧아진다는 특성이 있습니다.

SRF?

SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 짧은 작업을 모두 수행하고 그 다음 짧은 작업을 이어나가는 반면,  짧은 남아있는 작업시간(Shortest Remaining Time First)는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘입니다.

다단계 큐?

우선순위에 따른 준비 큐를 여러개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케쥴링 알고리즘을 적용한 것을 말합니다.  큐 간의 프로세스 이동이 안되므로 스케쥴링 부담이 적지만 유연성이 떨어진단느 특징이 있습니다.

오버헤드?

컴퓨터가 유저 프로그램을 실행할 때에 직접 유저 프로그램처리를 하지 않는 부분을 오버헤드라고 한다.   

구체적으로는 OS(오퍼레이팅 시스템)가 시스템을 관리하는데 필요로 하는 CPU 타임이나 메모리용량을 오버헤드라고도 하는데 OS가 처리하는 시스템의 자원을 유효하게 이용하여 스루풋을 향상시키기 위해서는 필요 불가결한 것이기 때문에 OS의 설계에 있어서는 어떻게 하여 오버헤드를 최소한으로 하고 또한 스루풋을 향상시키는가가 중요하게 된다.

오버헤드

특정한 목표를 달성하기 위해 간접적 혹은 추가적으로 요구되는 시간, 메모리, 대역폭 혹은 다른 컴퓨터 자원을 말한다. 프로그래머나 소프트웨어 엔지니어는 알고리즘, 인코딩, 데이터 형, 데이터 구조 등을 선택할 때 각각의 선택으로 인한 오버헤드를 고려하여야 한다. 일반적으로 오버헤드는 시스템이나 기계마다 달라질 수 있기 때문에 알고리즘의 복잡도를 표시하는 빅 오(Big O) 표기는 오버헤드 값을 포함하지 않는다. 소프트웨어 설계자는 설계 시 새로 포함될 특징이 초래하는 오버헤드와 보상에 따라 트레이드 오프(trade-off)를 분석하여 그 특징의 포함 여부를 결정하여야 한다.  오버헤드의 예로는 다음과 같은 것들이 있다.  -컴퓨터 프로그래밍 (실시간, 컴퓨팅 오버헤드) : 함수 호출(invoke) 시 스택 프레임을 설정하고 매개변수들과 반환 주소들을 복사하기 위한 실시간 오버헤드가 발생하며 컴파일러는 이 오버헤드를 최소화하기 위해 함수 호출을 재정렬하기도 한다.  -통신 (데이터 전송 오버헤드) : 통신 네트워크 상에서 전송하고자 하는 페이로드(payload)는 실제 데이터 자체뿐 아니라, 신뢰성 있는 통신을 보장하기 위한 다양한 제어 및 신호 데이터를 포함한다. 이때 이러한 제어 신호들은 모두 오버헤드로 간주된다. [네이버 지식백과] 오버헤드 [overhead] (두산백과 두피디아, 두산백과)

 

-