환급미션 47일째...
운영체제 - 쓰레드의 이해 - 04. 세마포어
운영체제 - 쓰레드의 이해 - 05. deadlock과 starvation
소프트웨어 베이직 - 자료구조와 알고리즘 - 13. 우선순위 큐
소프트웨어 베이직 - 자료구조와 알고리즘 - 14. 탐색 - 순차 탐색과 이진 탐색
운영체제 - 쓰레드의 이해 - 04. 세마포어
이전 강의에서 다루었던 내용을 살펴보면
동기화 이슈 해결 방안에는 여러 가지가 있었다.
•Mutual exclusion (상호 배제)
•여러 스레드가 변경하는 공유 변수에 대해 Exclusive Access
•특정 스레드가 공유 변수를 갱신하는 동안 다른 스레드가 동시에 접근하지 못하도록 막을 것
* Mutual exclusion (상호 배제)
•임계 자원(critical resource)
•임계 영역(critical section)
-----------python--------------
lock.acquire()
for i in range(1000000):
g_count+=1
lock.release()
--------------------------------
-> mutual exclusion 기법을 사용하는 예시
- Mutex와 세마포어(Semaphore)
Critical Section(임계 구역)에 대한 접근을 막기 위해 locking 메커니즘이 필요하다.
* Mutex (binary semaphore)
임계구역에 1개의 스레드만 들어갈 수 있다
* Semaphore
임계구역에 여러 스레드가 들어갈 수 있다
counter를 둬 동시에 리소스에 접근할 수 있는 스레드 수를 제어
- 세마포어 (Semaphore)
: 리눅스에서 코드로 구현되어있는 하나의 함수
슈도 코드(pseudo code) : 특정 언어에 구애받지 않고 로직 자체를 이해할 수 있도록 만들어진 코드
세마포어는 특별한 로직이 있기 때문에 pseudo code 형식으로 설명되어 있다.
어떤 로직으로 리소스에 접근하는 스레드의 수를 제어할 수 있는지에 대해 다룰 것이다.
P : 검사 (임계영역에 들어갈 때) - ex) lock.acquire()
S값이 1 이상이면, 임계영역 진입 후 S값 -1 & S값=0이면 대기
V : 증가 (임계영역에서 나올 때) - ex) lock.release()
S+=1 & 임계영역을 나옴
S : 세마포어 값 (초기값만큼 여러 프로세스가 동시에 임계영역 접근 가능)
동시에 임계영역에 접근할 수 있는 스레드의 수
--------pseudo code-----
P(S) : wait(S)
{
while S<=0 // 바쁜 대기
;
S--; // 다른 프로세스 접근 제한
}
~~임계영역~~
V(S) : signal(S)
{
S++; //다른 프로세스 접근 허용
}
---------------------------
-> wait()는 S가 0이라면, 임계영역에 들어가기 위해 반복문 수행
: 바쁜 대기, busy waiting
* 프로그래밍은 중단없이 끊임없이 코드를 실행한다.
중단은 대부분 loop로 표현되고, loop으로 인해 cpu에 부하가 걸릴 수 있다.
- 세마포어 - 대기 큐 (운영체제 기술로 보완 : 대기 큐)
S가 음수일 경우,
바쁜 대기 대신, 대기 큐에 넣어두고
대기가 끝나면 대기 큐에 있는 프로세스를 재실행한다.
-------pseudo code---
wait(S)
{
S->count--;
if (S->count <= 0)
{
add this process to S ->queue; //루프에 돌리는 대신 특정 큐에 넣어놓는다.
block() //슬립
}
}
signal(S)
{
S->count++;
if (S->count >=1)
{
remove a process P from S->queue;
wakeup(P) // wait state->running state로 전환, 운영체제(스케쥴러 또는 시스템콜 등)를 이용
}
}
---------------------------
* 참고 : 주요 세마포어 함수 (POSIX 세마포어)
sem_open() : 세마포어 생성
sem_wait() : 임계영역 접근 전 세마포어를 잠그고, 세마포어가 잠겨있다면 풀릴 때까지 대기
sem_post() : 공유자원에 대한 접근이 끝나면 세마포어 잠금 해제
운영체제 - 쓰레드의 이해 - 05. deadlock과 starvation
*** 용어 이해에 중점을 둘 예정이다.
- 교착상태 (dead lock) & 기아상태 (starvation)
* 교착상태 (dead lock)
무한 대기 상태, 즉 2개 이상의 작업이 서로의 작업이 끝나기를 기다리고 있고 아무것도 진행되지 않는 상태
batch system에서는 이러한 문제가 일어나지 않으며
프로세스, 스레드 모두 deadlock이 발생할 수 있다.
** deadlock 발생조건 - 4가지 조건이 모두 성립할 때, 교착상태 발생 가능
•상호배제(Mutual exclusion) : 프로세스들이 필요한 자원에 대해 배타적인 통제권 요구
•점유대기(Hold and wait) : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다림
•비선점(No preemption) : 프로세스가 어떤 자원의 사용을 끝날 때까지 그 자원을 사용할 수 없다.
•순환대기(Circular wait) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가진다.
** 교착상태 예방 (deadlock prevention)
•발생조건 4가지 중 하나를 제거
상호배제 -> 임계 영역 제거
점유대기 -> 한번에 모든 필요자원 점유 및 해제
비선점 -> 선점 가능기법을 구현
순환대기 -> 자원 유형에 따라 순서 부여
** 교착상태 회피 (deadlock avoidance)
교착상태 조건 4번만 제거 (조건 1,2,3 제거시 프로세스 효율성이 줄어듬)
-> 자원 유형에 따라 순서 부여
** 교착상태 발견 (deadlock detection) & 회복(recovery)
deadlock detection : deadlock 발생 체크, 교착상태인 프로세스/자원을 발견
deadlock recovery : deadlock 발생한 프로세스 종료하거나, 할당된 자원을 선점하여 프로세스/자원을 회복
* 기아상태 (starvation)
여러 프로세스가 부족한 자원을 점유하기 위해 경쟁하는 상황에서 주로 발생한다.
특정 프로세스의 우선순위가 낮아서 원하는 자원을 영원히 할당받을 수 없는 상태......
->
50개의 스레드 중 49개의 스레드가 우선순위 1, 1개의 스레드가 우선순위 2라고 가정
프로그램 10번 실행한 뒤에 프로그램 종료하면 절대 우선순위가 2인 스레드가 실행될 수 없다....
** 기아상태 해결 방안
•우선순위 변경
프로세스 우선순위를 수시로 변경
오래 기다린 프로세스의 우선순위 높이기
우선순위 기반이 아닌 FIFO 기반 요청 큐 사용
소프트웨어 베이직 - 자료구조와 알고리즘 - 13. 우선순위 큐
- 우선순위 큐 필요성
우선순위 큐 : '우선순위'를 가진 데이터들을 저장하는 큐를 의미
우선순위가 높은 데이터가 가장 먼저 나온다.
운영체제의 작업 스케쥴링, 정렬, 네트워크 관리 등에 적용됨
- 일반적인 큐 vs 우선순위 큐
일반적인 큐 : 선형적인 형태
우선순위 큐 : 트리(Tree)구조, 최대 힙을 이용해 구현 (완전 이진트리와 흡사)
* 최대 힙 (Max heap)
최대 힙 : 모든 부모 노드가 그의 자식 노드보다 값이 큰 완전 이진트리
root node는 항상 가장 큰 값을 갖는다.
항상 전체 트리가 최대 힙 구조를 유지하도록 자료구조를 만들 수 있다.
큐를 기반으로 동작하기 때문에 PUSH, POP 함수로 구성된다.
3번째 예시는 '완전이진트리'가 아니기 때문에 최대힙 x
4번째 예시는 부모 7이 자식 9보다 값이 작기 때문에 최대힙 x
- 우선순위 큐의 삽입
우선순위 큐의 삽입은 아래 그림의 순서대로 진행된다.
먼저, 완전 이진트리를 유지하는 형태로 순차적으로 삽입된다.
(위에서부터 & 왼쪽부터 채워짐)
삽입된 이후에
root node까지 거슬러 올라가면서 최대 힙을 구성 [상향식]
최종적으로 최대힙이 구성된 결과이다.
logN만큼의 시간이 소요된다.
- 우선순위 큐의 삭제
우선순위 큐의 삭제방법은 아래 순서대로 진행된다.
root node를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 옮겨준다.
삭제 이후에
leaf node까지 내려가면서 최대 힙을 구성한다. [하향식]
왼쪽/오른쪽 자식 우선순위와 관계없이
둘 중 큰 값을 root node에 두면 된다.
최종적으로 우선순위 큐의 삭제 결과를 보여준다.
- 우선순위 큐 구현
* 우선순위 큐의 정의
----------------
#include <stdio.h>
#define MAX_SIZE 10000
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
typedef struct
{
int heap[MAX_SIZE]; //하나의 heap이 배열형태로 만들어짐
int count; //힙의 원소에 갯수가 count가 되도록 구현할 예정
} priorityQueue;
----------------
* 우선순의 큐 삽입
---------------
---------------
* 우선순위 큐의 추출
일반적인 큐와는 약간 다른 동작을 보여준다.
* 우선순위 큐의 사용
츨력은 위와 같다.
5개의 원소
2,8,3,7,9를 순서대로 입력했을 때
우선순위가 높은 순서대로 정렬되어 출력이 된 것을 확인할 수 있었다.
정리
우선순위 큐 : 완전 이진 트리 형태의 힙을 이용해 구현
삽입/삭제는 O(logN)의 시간 복잡도
-> 우선순위 큐를 이용한 정렬은 O(logN)의 시간 복잡도
소프트웨어 베이직 - 자료구조와 알고리즘 - 14. 탐색 - 순차 탐색과 이진 탐색
- 순차 탐색 (Sequential Search)
특정한 원소를 찾기 위해 원소를 순차적으로 하나씩 탐색
시간 복잡도는 O(N)이다.
원하는 값을 찾았을 때 해당 인덱스 값을 반환
* 문자열 순차 탐색 구현
위의 코드를 작성했을 때
결과값이 정상적으로 출력되는 것을 확인할 수 있었다.
- 이진 탐색 (Binary Search)
배열 내부 데이터가 이미 정렬되어있는 상황에서 사용 가능한 알고리즘
탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다. (중간 위치에 있는 원소와 반복적으로 비교)
한 번 탐색시 탐색해야 하는 원소의 갯수가 절반씩 줄어들기 때문에 시간 복잡도는 O(logN)이 된다.
시간적인 부분에서 효율적인 알고리즘이란 것은 부정할 수 없지만
데이터가 이미 정렬되어있는 상황에서만 사용 가능하다는 단점이 있다.
이미 원소들이 순서대로 정렬되어 있는 상황을 가정
찾을 원소 값과 중간값을 비교,
위의 예시에서 찾을 원소보다 중간값이 더 크기 때문에
뒤의 값들은 더이상 볼 필요가 없고 앞의 값들 중에서 찾아보면 된다.
마찬가지로 찾을 원소와 중간값을 비교,
찾을 원소보다 중간값이 더 작기 때문에
뒤의 값들 중에서 찾으면 된다.
위의 예시의 경우는 사실 3번째에 찾는 원소가 있기 때문에
순차 탐색과 탐색하는 속도는 같을 수 있지만
우연히 일치하는 것 뿐이고
실제로는 훨씬 시간이 적게 든다.
* 이진 탐색의 구현
순차 탐색에 비해 코드가 좀 더 길어보이지만 로직은 단순하다.
10개의 원소 중 '33'을 탐색하였고,
원소를 순서대로 입력해넣었는데,
정상적으로 원하던 값이 출력된 것을 확인했다.
올인원 패키지 : 컴퓨터 공학 전공 필수👉https://bit.ly/3i4sCVE
'패스트캠퍼스' 카테고리의 다른 글
| [패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 49회차 미션 (0) | 2020.12.06 |
|---|---|
| [패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 48회차 미션 (0) | 2020.12.05 |
| [패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 46회차 미션 (0) | 2020.12.03 |
| [패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 45회차 미션 (0) | 2020.12.02 |
| [패스트캠퍼스 수강 후기] 올인원 패키지 : 컴퓨터 공학 전공 필수👉C언어인강 100% 환급 챌린지 44회차 미션 (0) | 2020.12.01 |