수직적 마이크로 프로그래밍

상점에서 쇼핑을 한다고 생각해보자, 상점의 한코너에서 다른코너로 이동하면서 물건을 하나씩 카트에 담는다.

각 물건을 찾는 지시는  '명령어'에 해당하고, 상점을 돌아다니는 행위를 '마이크로프로그래밍'에 비유 할 수 있다.

이경우, 각단계가 순차적으로 이루어지고, 한번에 하나의 작업만 수행한다. 이런 방식은 구현이 간단하고 이해하기 쉽지만, 전체적인 쇼핑시간이 길어질 수 있다.


수평적 마이크로 프로그래밍

- 동일하게 상점에서 쇼핑을 하는 상황이나, 이번에는 친구를 여러명 대동해서 쇼핑을 진행한다.

친구들에게 쇼핑리스트를 미리 정한뒤에 각 물건을 할당해서 상점에서 물건을 찾게한다. 이렇게 되면 동시에 작업을 할 수 있어 훨씬 빠르게 쇼핑을 마칠수 있다.

하지만 친구들을 관리해야하고, 조금더 복잡하게 처리가 필요하다는걸 알수 있다.

결국 수직적 프로그래밍은 단순화를 통해서 명령어들을 추가할때 더 쉽지만, 느리다는 특성이 있고,

수평적 프로그래밍은 동시성을 증대시키지만, 명령어를 추가(친구들에게 지시할때 복합적인추가)가 필요하고 친구들이 상점을 찾는동안의 메커니즘을 보면 빠르지만 뭔가 추가시에 불리한 점을 확인 할  수있다.

반응형

'정보관리기술사 > CA_OS' 카테고리의 다른 글

운영체제특권레벨  (0) 2023.11.28
Banker's Algorithm(은행가알고리즘)  (1) 2023.11.27
모니터/Monitor 동기화  (1) 2023.11.26
교착상태(Deadlock)  (0) 2023.11.25
우선순위 역전  (0) 2023.11.24
중 운영체제특권레벨 [정의] 운영체제 특권레벨(Privilege Levels) 정의
- CPU에 의해 제공되는 레벨로 어떤 시점에서의 CPU 상태를 나타내며 구체적으로는 CPU가 어떠한 명령을 실행할 수 있는가, 메모리의 어떤 범위에 접근할 수 있는가와 같은 권한의 정도를 의미
CPU에 의해 제공되는 레벨, Ring 0, 1, 2, 3
Ring 0(kernel), 1, 2(드라이버), 3(사용자모드)		  
토픽 이름(상) 운영체제 특권레벨
분류 OS > 운영체제 특권레벨
키워드(암기) Ring 0(kernel), 1, 2(드라이버), 3(사용자모드), 권한, 접근
암기법(해당경우)  

 

기출문제

번호 문제 회차
1 운영체제의 특권레벨과 시스템콜에 대해서 설명하시오. 합숙16.01응용Day-3

 

I. Protection Ring, 운영체제 특권레벨 개요

가. 운영체제 특권레벨(Privilege Levels) 정의

- CPU에 의해 제공되는 레벨로 어떤 시점에서의 CPU 상태를 나타내며 구체적으로는 CPU가 어떠한 명령을 실행할 수 있는가, 메모리의 어떤 범위에 접근할 수 있는가와 같은 권한의 정도를 의미

나. 운영체제 특권레벨의 분류

커널 모드 운영체제 코드가 실행되는 특권레벨 Ring 0
사용자 모드 사용자 코드가 실행되는 특권레벨 Ring 3

- Ring 숫자가 작을수록 더 많은 자원에 접근 가능함

 

II.  운영체제 특권레벨 및 시스템콜

가. 운영체제 특권레벨 개념도

- 응용프로그램의 요청에 의해서 사용자모드에서 커널모드로 전환 호출.

나. 운영체제 특권레벨과 시스템콜의 관계 개념도

- 운영체제의 커널이 제공하는 서비스에 대해, 응용프로그램의 요청에 따라 커널에 접근하기 위한 인터페이스로 사용자모드에서 커널모드로 전환을 위한 호출

- 소프트웨어 인터럽트 또는 Trap(이런 류의 인터럽트)을 발생하여 사용자모드에서 커널모드로 전환

- 시스템콜의 동작 목적이 사용자모드에서 커널모드로 전환하여 사용자모드에서 사용할 수 없는 낮은 수준의 하드웨어 접근이나, 운영체제의 특정 기능을 사용하기 위한 목적

 

III. 특권레벨과 시스템콜을 이용한 모드의 구분 이유

- 운영체제와 사용자 응용프로그램이 수행되는 가상메모리 공간의 분리가 가장 큰 이유

- 가상메모리 공간의 분리로, 사용자응용프로그램은 다른 주소영역을 침범할 수 없어 전체적인 시스템의 안정성 향상

 

 

“끝”

 

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

수직적 프로그래밍 vs 수평적 프로그래밍  (0) 2024.02.18
Banker's Algorithm(은행가알고리즘)  (1) 2023.11.27
모니터/Monitor 동기화  (1) 2023.11.26
교착상태(Deadlock)  (0) 2023.11.25
우선순위 역전  (0) 2023.11.24
중 Banker's Algorithm(은행가알고리즘) [정의]Banker 알고리즘의 정의
- 운영체제는 자원의 상태를 감시하고 사용자 프로세스는 사전에 자기작업에서 필요한 자원의 수를 제시하는 교착상태 회피 알고리즘
프로세스, 자원요청
AMAN(AVAILABLE MAX ALLOCATE NEED)
AMAN+R(Available, Max, Allocation, Need, Request)
토픽 이름 (상) Banker's Algorithm
분류 OS > 병행제어 > Banker's Algorithm
키워드(암기) AMAN+R(Available, Max, Allocation, Need, Request)
암기법(해당경우)  

 

기출문제

번호 문제 회차
1 다중 프로그래밍 운영체제 하에서 발생하는 교착상태(Dead Lock)를 회피(Avoidance)하기 위한 Banker's Algorithm을 설명하시오. 기_86.관.4.2
2 교착상태(Deadlock)의 필요조건과 교착상태 회피 방법으로 많이 사용되고 있는 Banker 알고리즘을 설명하시오. 기_101.관.3.3
3 교착상태 회피를 위한 Banker's Algorithm을 설명하시오. 모1405-관-2-5
4 은행가 알고리즘(Banker's Algorithm)을 이용하여 프로세스 수행 순서에 대해 설명하시오. (단, 프로세스 자원 요청은 P1, P2, P3, P4로 진행) 모1505-관-1-13
5 교착상태(Deadlock)가 발생하는 필수조건과 해결방안을 설명하고, 회피방법인 Banker's Algorithm을 설명하시오. 모1711-응-2-4
6 교착상태를 회피하기 위한 은행가 알고리즘을 설명하고, 시스템의 구성이 다음과 같을 때 은행가 알고리즘을 사용하여 안전한 상태로 수행할 수 있도록 프로세스 수행 순서를 제시하시오
- 프로세스 - P0 , P1 , P2 , P3 , P4 (프로세스 자원 요청은 P0, P1, P2, P3, P4 순으로 진행)
- 자원 - A : 10 B : 5 , C : 7 (세가지 유형과 각 유형의 인스턴스 수)
- 시간 T0 일 때 시스템의 상태는 다음과 같음.		 모1711-관-3-3

 

I. 교착상태 회피 Banker 알고리즘의 개요

가. Banker 알고리즘의 정의

- 운영체제는 자원의 상태를 감시하고 사용자 프로세스는 사전에 자기작업에서 필요한 자원의 수를 제시하는 교착상태 회피 알고리즘

- 운영체제는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정 기간 내에 성공적으로 끝날 수 있는 안전 상태인지를 면밀하게 분석하는 교착상태 회피 알고리즘

- 운영체제는 안전상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 교착상태 회피 알고리즘

 

나. Banker 알고리즘의 동작 개념도

 

II. Banker 알고리즘의 자료구조 및 처리 프로세스

가. Banker 알고리즘의 자료구조(n:프로세서 수, m:자원의 종류 수)

자료명 자료형태 설명 수식
Available m의 vector 사용 가능한 자원의 수 Available[j] = K
자원종류 Rｊ중 K개 사용가능
Max n x m 행렬 프로세스 별 최대 자원의 요구 Max[i, j] = K
Pｉ는 자원종류 Rｊ중 최대 K개요청
Allocation n x m 행렬 현재 프로세스 별 할당되어 있는 자원 수 Allocation[i, j] = K
Pｉ는 현재 자원종류 Rｊ를 K개 할당 받고 있음
Need n x m 행렬 프로세스 별 남아 있는 자원의 수 Need[i, j]=(Max – Allocation)
Pｉ가 작업 완료를 위해 필요한 자원유형 Rｊ의 수
Request n x m 행렬 프로세스가 요청한 자원의 수 Request[i, j] = K
Pｉ는 자원종류 Rｊ를 K개 더 요구함

 

나. Banker 알고리즘 처리 프로세스

 

III. Banker 알고리즘의 구조(사례)

-풀이 2), 3) P2 – R2 – 4를 2로 확인 필요

- 최대 요구 자원 수 (Maximum Claim)에 대한 정보가 있을 경우를 가정

1) 현재 사용 가능한 리소스의 양을 구한다 (Available)
2) 추가 요구량을 구한다 (Request = Max – Allocation)
3) 추가 요구 자원이 현재 여유자원보다 적은 프로세스(i)를 찾는다
(수행을 끝내기 위한 충분한 자원을 확보한 프로세스 검사)
[ (Request (i) ç Available(i) )
4) 수행 가능한 프로세스가 점유한 자원을 여유 자원으로 바꿈
(끝내고 반환한 경우로 가정)한 후에 3번부터 반복
(Available = Available + Allocation)

 

IV. 은행가 알고리즘(Banker’s Algorithm)의 한계 및 교착상태 방지 대응전략

- 일정한 수의 자원과 사용자에서만 가능하며 최대 자원 필요량을 사전에 등록해야 함

- 모든 요구를 유한 시간 내에서 수행해야 하며 프로세스들은 할당 받은 자원을 유한 시간 내 반환해야 함

- 따라서 교착상태 발생을 억제하기 위해서는 예방, 회피, 탐지, 복구 방법을 병행하여 사용하고 각 자원 유형별 특성을 파악하여 대응전략을 구분운영하는 것이 필요

 

 

 

 

 

“끝”

 

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

수직적 프로그래밍 vs 수평적 프로그래밍  (0) 2024.02.18
운영체제특권레벨  (0) 2023.11.28
모니터/Monitor 동기화  (1) 2023.11.26
교착상태(Deadlock)  (0) 2023.11.25
우선순위 역전  (0) 2023.11.24
출제예상 모니터/Monitor 동기화 - 세마포어와 관계 설명 가능
- 프로세스 동기화 수행시 세마포어의 단점인 타이밍 문제를 해결하기 위하여 프로그래밍 언어 수준에서 상호배제를 구현하여 동기화를 제공하는 기법.
(중요) 프로그램 언어로, 제어한다는 것. 이로인해, 변수로 제어 하겠다는 개념		 세마포어의 P 연산과 V 연산
122회 기출
토픽 이름 (중) 모니터(Monitor) 동기화
분류 OS > 병행제어 > 모니터(Monitor) 동기화
키워드(암기) 타이밍 문제, 언어수준의 상호배제, 배타동기, 조건동기, synchronized,wait,notify
암기법(해당경우)  

 

기출문제

번호 문제 회차
1 6. 모니터(Monitor) 프로세스 동기화 기법 기_119.응.1.6
2 세마포어(Semaphore)와 모니터(Monitor)의 상호관계를 설명하시오. 기_98.응.1.11
3 세마포어(Semaphore)와 모니터(Monitor)의 상호관계를 설명하시오. 모1501-응-1-8

 

 

I. 상호배제의 SW적인 해결책 모니터의 개요

가. 모니터의 정의

- 세마포어의 이론을 기반으로 프로그래밍언어 수준에서 상호배제 기능을 제공하는 소프트웨어 모듈

나. 모니터의 특징

- 지역 변수는 모니터 내부에서만 접근 가능

- 프로세스는 모니터 프로시저 중 하나를 호출함으로써 모니터 내부로 진입

- 한 시점에 단 하나의 프로세스만 모니터 내부에서 수행 가능

- 세마포어보다 High Level의 동기화 메소드로 사용하기 용이함

 

II. 모니터의 개념도 및 유형

가. 모니터의 개념도

 <동기화 방법>
- cwait(c) : 호출한 프로세스를 조건 c에서 일시중지


- csignal(c) : cwait에 의해 중지된 프로세스를 재개시킴

나. 모니터의 유형

유형 프리미티브 구현 핵심 구현방법
시그널 기반
유한 버퍼 모니터		 if문 사용 If (count == N) cwait(notfull); /*버퍼에 문자가 가득 찬 경우. 오버플로 방지*/

csignal 문 사용 csignal(notempty); /*not empty조건 변수에서대기하고 있는 프로세스를 깨움*/
MESA 기반
유한 버퍼 모니터		 while문 사용 while (count == N) cwait(notfull); /*버퍼에 문자가 가득 찬 경우. 오버플로 방지*/

cnotify 문 사용 cnotify(notfull); /*대기하는 생산자가 있으면 조건 발생을 통보*/

 

III. 세마포어와 모니터의 상호관계

 

“끝”

 

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

운영체제특권레벨  (0) 2023.11.28
Banker's Algorithm(은행가알고리즘)  (1) 2023.11.27
교착상태(Deadlock)  (0) 2023.11.25
우선순위 역전  (0) 2023.11.24
Semaphore  (1) 2023.11.23
상 교착상태(Deadlock) [정의]다중프로그램환경에서두개이상의프로세스가아무리기다려도자원을사용할수없는무한대기상태
[특징]상호배제, 점유와대기, 비선점, 환형대기, 예방, 회피, 발견, 회복
Wait-die와 Wound-wait
교착상태 4가지발생조건(상점비환) 및
은행가 알고리즘 등 4가지 예방, 회피, 발견, 회복 기법을 기억하세요

 

 

 

 

 

 

토픽 이름 교착상태
분류 OS > 병행 제어 > 교착상태
키워드(암기) 상호배제, 점유와 대기, 비선점, 환형대기, 예방, 회피, 발견, 회복
암기법(해당경우) 상점비환, 예피발복

 

기출문제

번호 문제 회차
1 4. 교착상태 기_116-관-1-4
2 Deadlock 발생원인과 해결방안 기_71-응-1-9
3 다중 프로그래밍 운영체제 하에서 발생하는 교착상태(Dead Lock)를 회피(Avoidance)하기 위한 Banker's Algorithm을 설명하시오. 기_86-관-4-2
4 교착상태(Deadlock)의 필요조건과 교착상태 회피 방법으로 많이 사용되고 있는 Banker 알고리즘을 설명하시오. 기_101-관-3-3

 

I. 다중 프로세싱 환경에서 무한 자원대기, 교착상태의 개요

 - 다중 프로그램 환경에서 두 개 이상의 프로세스가 아무리 기다려도 자원을 사용할 수 없는 무한 대기 상태

 

II. 교착상태 개념도 및 발생원인

가. 교착상태 개념도

 

나. 교착상태 발생 원인

원인 설명
상호배제 (Mutual Exclusion) - 프로세스들이 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용하지 못함
점유와 대기 (Block & wait) - 프로세스가 어떤 자원을 할당 받아 점유하고 있으면서 다른 자원을 요구
비선점 (Non preemption) - 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없으며, 점유하고 있는 프로세스 자신만이 해제 가능
환형대기 (Circular wait) - 프로세스간 자원요구가 하나의 원형을 구성

- 교착상태는 한 시스템에서 다음 4가지 조건이 동시에 성립될 때 발생

III. 교착상태 해결방안 및 상세설명

가. 교착상태 해결방법

해결방안 핵심 내용
예방 (Prevention) - 상호배제 조건, 점유와 대기조건, 비선점 조건 및 환형대기 조건의 부정
회피 (Avoidance) - Banker’s Algorithm(은행가 알고리즘), Wait-die, wound-wait 알고리즘
발견 (Detection) - 시스템의 상태를 감시 알고리즘 통해 교착상태 검사
- 자원할당 그래프, Wait for Graph
회복 (Recovery) - Deadlock이 없어질 때까지 프로세스를 순차적으로 Kill하여 제거
- 프로세스 종료비용 최소화 : 우선순위, 진행비용, 복귀비용 등
- 자원의 우선순위 할당 : 희생자 선택, 복귀, 기아 상태

 

나. 교착상태 해결방안 상세설명

1) 교착상태의 예방

구분 설명 단점
상호배제 조건의 부정 - 공유할 수 없는 자원을 사용할 때 성립 프로그램 구조의 복잡화
동일 자원의 필수적 상호 배제 상황 발생 시 문제 해결의 어려움
점유와 대기조건의 부정 - 프로세스가 자원을 요청할 때는, 다른 자원들을 점유하지 않을 것을 보장함 자원낭비 및 비용증가
자원공유 불가능
Starvation 발생가능
비선점 조건의 부정 - 어떤 자원을 가진 프로세스가 더 이상 자원할당 요구가 받아지지 않으면 점유자원을 반납 비용증가
Starvation 발생가능
일부 자원은 안전하게 선점 불가
환형대기 조건의 부정 - 모든 프로세스에게 각 자원의 유형별로 할당순서를 부여하는 방법 새로운 자원 추가 시 재구성 필요

- 사전에 교착 상태의 발생 가능성을 모두 제거하도록 시스템을 제어

 

2) 교착상태의 회피

알고리즘 설명
자원할당 그래프
알고리즘		 종류별 자원이 한 개인 경우 자원 종류마다 한 개의 자원 요청가능
자원할당 그래프+예약간선(claim edge)
프로세스가 자원 요청하면 예약간선은 요청간선으로 전환

이 요청간선을 할당간선으로 변환해도 cycle이 없을 때만 할당
자원 할당 그래프(resource allocation graph) : 프로세스와 자원간의 관계를 나타내는 그래프
Banker’s
알고리즘		 - 운영체제가 자원의 상태를 감시하고 프로세스가 사전에 필요한 자원의 수를 제시 관리하는 교착상태 회피 알고리즘
- 종류별 자원이 여러 개인 경우 프로세스의 최대자원 요구량, 현재 할당된 자원의 수 등을 이용하여 프로세스의 자원 할당이 안전한지 여부를 확인 후 할당

- 교착 상태 발생 가능성을 인정하고 교착 상태가 발생하려고 할 때 이를 적절하게 피해가는 방법

 

3) 교착상태의 발견
- 시스템 상태를 감시하는 알고리즘을 통해 교착상태를 검사하는 알고리즘

- 시스템 운영 중에 교착 상태가 발생했는지를 결정하고 교착 상태에 관련된 프로세스와 자원을 발견

 

4) 교착상태의 회복

구분 항목 설명
프로세스 종료 교착 상태 프로세스들을 모두 중지 교착 상태에 빠진 모든 프로세스들을 종료함으로써 확실하게 교착 상태의 사이클을 해결하지만 비용이 많이 소요

한 프로세스씩 중지 교착 상태에 빠진 프로세스들 중에서 한 프로세스씩 순서대로 종료 시켜 가면서 교착 상태를 해결하는 방법

희생자 선택의 원칙 최소 비용의 원칙으로 희생자(victim) 프로세스를 선정
자원 선점 대상 선택 희생자 선정 문제 교착 상태에 빠진 프로세스들 중에서 최소의 피해를 주면서 어느 프로세스 자원을 선점할 것인지를 결정

복귀 문제 자원을 선점 당한 프로세스를 안전 상태로 복귀시키고, 종료된 지점부터 다시 재시작

기아 상태 문제 자원들이 항상 동일한 프로세스로부터 선점되면, 기아(starvation) 상태가 발생

- 시스템으로부터 교착 상태를 제거하여 이후로는 시스템이 교착 상태에 빠지지 않고 계속 진행되게 하는 것

 

IV. Deadlock 해결을 위한 전체 시스템 설계

항목 설명
내부 시스템 자원 순서화 PCB, 버퍼, Semaphore등의 자원 순서화
사용자 작업에 대한 주기억장치 선점 - 선점은 Paging, Segmentation, Swapping 시스템에서 가장 효율적인 접근법
- 선점이 불가능하면 주기억 장치를 작업자원의 부류에 포함시킴
자원필요량 산정 작업이나 작업단계의 자원필요량 산정
교체 가능 공간 사전 할당 요구된 기억장치를 사전에 할당

 “끝”

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

Banker's Algorithm(은행가알고리즘)  (1) 2023.11.27
모니터/Monitor 동기화  (1) 2023.11.26
우선순위 역전  (0) 2023.11.24
Semaphore  (1) 2023.11.23
Mutual Exclusion(상호배제)/뮤텍스  (1) 2023.11.22
상 우선순위 역전
(세마포어 문제)		 [우선순위 역전(Priority Inversion) 정의]
낮은 우선순위를 가진 Task에 의해 높은 우선순위를 가진 Task가 임계 영역 대기 때문에 Block 되어 수행되지 못하는 현상
해결방법: 우선순위 상속(Priority Inheritance) 기법, 우선순위 올림(Priority Ceiling) 기법
토픽 이름 우선순위 역전
분류 OS > 병행 제어 > 우선순위 역전
키워드(암기) - 정의 : 높은 우선순위 Task가 임계영역 대기, 블록 되어 수행되지 않는 현상
- 우선순위 역전의 해결방안
1) 우선순위 상속 (Priority Inheritance)
2) 우선순위 올림 (Priority Celling)
암기법(해당경우)  

 

기출문제

번호 문제 회차
1 실시간 스케줄링(Real Time Scheduling) 문제 중 하나인 우선순위전도(Priority Inversion) 상황 시나리오를 설명하고 이에 대한 해결기법 2가지를 제시하시오. 기99-응-4-1
2 3개 태스크 (task1, task2, task3)가 실행되고 이들의 우선순위는 task1 > task2 >task3 이다. 우선순위 역전 (Priority Inversion) 이 발생하는 경우와 이를 해결하기 위한 방법을 위 3 개 태스크를 예로 들어 설명하시오 기108-응-4-3
3 우선순위 역전현상 에 대해 설명하시오. 모1111-응-1-15
4 우선순위 역전(Primary Inversion)을 설명하고 해결방안 두 가지를 설명하시오. 모1207-응-1-3
5 우선순위 역전(Priority Inversion)현상의 해결방법을 설명하시오. 모1305-응-1-4
6 실시간 스케줄링 기법에 대하여 다음을 설명하시오.
가. RM과 EDF를 각각 설명하시오.
나. 우선순위 역전현상(Priority Inversion)의 발생원인을 설명하시오.
다. 우선순위 역전현상의 해결방안 2가지를 설명하시오.		 합105-2일-2-7
7 우선순위 역전(Priority Inversion) 현상에 대해 설명하시오. 합111-3일-1-6
8 4. 운영체제 Task의 우선순위 역전현상이 발생하는 경우와 이를 해결하는 방법에 대하여 설명하시오. 모의_2018.07.관.2
9 7. Task1, Task2, Task3 이 실행 중일 때 발생 가능한 우선순위 역전(Priority Inversion)현상을 설명하고, 이에 대한 해결 기법을 설명하시오.
(단, Task의 우선 순위는 Task 1 > Task 2 > Task 3 이다.)		 합숙_2019.08-응-3일

 

I. 실시간 스케줄링의 문제점, 우선순위 역전의 개요

 - 낮은 우선순위를 가진 Task에 의해 높은 우선순위를 가진 Task가 임계영역 대기 때문에 블록 되어 수행되지 않는 현상

II. 우선순위 역전의 발생 개념도

순서 설명
1 task3이 공유자원을 액세스하기 위해 바이너리 세마포어를 가지고 수행
2 운영체제 스케줄러에 의해 우선순위가 높은 task1이 수행됨
3 task1이 task3이 먼저 획득한 세마포어를 얻으려 하고, task3이 그 세마포어를 반환할 때까지 WAITING 상태가 됨
4 스케줄러에 의해 task3이 수행됨
5 스케줄러에 의해 task2가 수행됨(중간에 중간순위인 task2가 들어와 CPU 차지)
이 때, task3의 우선 순위가 task2보다 높음에도 불구하고 task2가 먼저 수행되는 우선순위 역전 현상이 발생함
6 task2의 수행이 종료되면 다시 task3이 수행됨
7 task3이 세마포어를 반환
8 task1 수행

- task 1이 가장 높은 우선순위를 가졌으나 결국 가장 나중에 수행됨

 

III. 우선순위 역전의 해결방안

가. 우선순위 상속 (Priority Inheritance)


 - 우선순위 낮은 Task3을 임시로 자원요청한 상위우선순위를 부여해서 먼저 실행
- Deadlock 걸릴 확률 있음
(Task3이 Task1 점유자원을 요청하는 경우)

나. 우선순위 올림 (Priority Celling)


 - 어떤 스레드가 세마포어(뮤텍스)를 소유하고 있는 동안은 지정된 우선순위에서 동작
- 단, 스레드의 우선순위가 지정된 우선순위 올림 값보다 작은 경우에만 우선순위 변경
- 세마포어(뮤텍스)를 이미 잠근 쓰레드는 다른 쓰레드들에 의해 선점되지 않고 자신의 작업을 종료 가능

 

“끝”

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

모니터/Monitor 동기화  (1) 2023.11.26
교착상태(Deadlock)  (0) 2023.11.25
Semaphore  (1) 2023.11.23
Mutual Exclusion(상호배제)/뮤텍스  (1) 2023.11.22
RAID  (1) 2023.11.21
상 Semaphore [정의]운영체제또는프로그램내에서공유자원에대한접속을제어하기위해사용되는신호로병행내지병렬로동작되는둘이상의프로세스사이에서공유자원의사용을통제하는방법
[키워드] P, V 연산, 2가지 세마포어 유형
이진, 계수형세마포어		  
토픽 이름 세마포어(Semaphore)
분류 OS > 병행 제어 > Semaphore
키워드(암기) P(), V(), S
암기법(해당경우)  

 

기출문제

번호 문제 회차
1 세마포어(Semaphore)의 P 연산과 V 연산을 설명하시오 기86-관-1-2
2 세마포어(Semaphore)와 모니터(Monitor)의 상호관계를 설명하시오. 기98-응-1-11
3 계수형 세마포어(Countin semaphore)에 대하여 설명하시오 기99-관-1-9
4 세마포어(Semaphore)를 이용한 리소스 공유 방법과 태스크간 동기화 방법에 대하여 설명하시오. 기108-응-3-4
5 12. 세마포어(Semaphore)와 뮤텍스(Mutex)를 비교 설명하시오. 기120-응-1
6 세마포어(Semaphore)와 모니터(Monitor) 기122-관-1

 

I. 상호배제 원리를 응용한 busy waiting 해결책, 세마포어 개요

가. 세마포어 정의

- 운영 체제 또는 프로그램 내에서 공유 자원에 대한 접속을 제어하기 위해 사용되는 신호로 병행 내지 병렬로 동작되는 둘 이상의 프로세스 사이에서 공유 자원의 사용을 통제하는 방법

나. 세마포어 특징

특 징 설 명
병렬 프로세스 동기화 프로세스간의 접근을 동기화 처리
원자적 실행 P연산과 V연산은 하나의 과정으로 수행
교착상태 방지 자원이 사용중일 때 다른 프로세스의 접근을 막고 끝난 후 접근 허용

 

II. 세마포어의 동작 원리 및 유형

가. 세마포어의 동작 원리
종류 의미 내용
초기화 Initialize - 세마포어(S)에 하나의 대기 큐를 할당하고 초기화
- S = 1
P 연산 Wait - P(S) 연산(wait()) 수행
- 변수의 값을 하나 줄인 후 변수의 값이 0보다 작으면 프로세스를 대기열에 집어 넣음
- S = S – 1
- S < 0 : 프로세스를 대기열에 넣음
- S > 0 : 프로세스는 계속 진행
- S=0, 자원 할당 상태
V 연산 Signal - V(S) 연산(Signal()) 수행
- 0보다 크면 프로세스를 계속 진행, V명령은 변수의 값을 하나 증가
- 변수가 음이면 대기, 양수이면 실행을 의미
- S = S+1
- S > 0 : 프로세스 계속 진행
- S < 0 : 대기열의 프로세스 하나를 준비상태로 프로세스 계속
- S=1, 자원 해제 상태

- 세마포어 s는 정수값을 가지며 p와 v에 의해서만 접근되는 정수형 공용변수

나. 세마포어의 유형

유형 목적 내용
이진 세마포어
Binary Semaphore		 - Semaphore 변수가 0과 1 두 종류의 값만 갖는 경우
- 상호배제, 프로세스 동기화		 세마포어 변수 : 0 or 1
계수형 세마포어
Count Semaphore		 - Semaphore 변수가 0 이상의 모든 정수 값을 가질 수 있는 경우
- 초기에 동시 진행 가능한 프로세스 개수를 정의 가능		 0,1,2, …

 

III. 세마포어를 이용한 리소스 공유 방법

가. 리소스 공유 메커니즘

- N개의 Task와 M개의 Resource를 공유할 때, 세마포어(계수형) 초기값을 N개로 설정

나. 리소스 공유 절차

- Task가 세마포어를 획득하여도 Mutex를 획득해야 리소스 접근 가능

 

IV. 세마포어를 이용한 태스크간 동기화 방법

1. TaskA가 동기화 전처리를 시작


2. TaskB는 동기화 세마포어가 POST 시그널 줄 때까지 WAIT


3. TaskA가 동기화 전처리를 완료


4. TaskA, Taskb 동기화 완료

- 태스크간 동기화(Synchronization) : 여러 개의 Task가 공유 데이터에 접근하는 경우 동일한 값을 얻을 수 있도록 맞추는 작업

- 계수형 세마포어인 경우, TaskA의 전처리 결과에 따라 계수가 증가하고 Task는 누적된 계수만큼 처리 수행

 

V. 세마포어의 사용시기 및 비교

가. 세마포어의 사용시기

구분 설명 비고
메시지 전송 프로세스 간 메시지를 전송하거나, 혹은 공유메모리를 통해서 특정 data를 공유하게 될 경우 발생하는 문제는, 공유된 자원에 여러 개의 프로세스가 동시에 접근 하면서 발생한다. 단지, 한번에 하나의 프로세스만 접근 가능하도록 만들어 줘야 하고, 이때 Semaphore를 쓴다. Data 공유
사용 특화 Thread 에서는 뮤텍스, 프로세스에서는 세마포어 뮤텍스,
세마포어
교착상태 방지 교착상태를 방지하기 위해, A 프로세스가 접근했을 때 다른 프로세스의 접근을 막고, 끝난 후 접근을 풀어준다. 이때 세마포어로 접근을 막고 접근을 허용할 수 있다 Dead Lock
방지

나. 세마포어와 뮤텍스 비교

구분 세마포어(Semaphore) 뮤텍스(Mutex)
원리 화장실이 n칸(접근할 수 있는 최대 허용치 만큼 동시에 사용자 접근을 할 수 있게 함), 세마포어 카운트가 0이면 대기 화장실에 들어가기 위한 열쇠를 한 사람이 가지고 있다면, 그 사람만이 들어갈 수 있다
대기열(큐)에 기다리게 됨. → 세마포어의 일종.
목적 Dead Lock을 피하기 위한 기술 중 하나 Critical Section을 가진 Thread 들이 running time이 서로 겹치지 않게, 각각 단독으로 실행하게 하는 기술
특징 공유 리소스에 접근할 수 있는 최대 허용치 만큼 동시에 사용자 접근을 할 수 있게 하는 기술
동기화 대상이 여러 개일 경우에 사용		 한 번에 하나의 Thread만이 실행되도록 하는 재 입장할 수 있는 코드 섹션 직렬화된 접근이 가능하게 할 때 사용
뮤텍스 객체는 제어되는 섹션에 하나의 Thread만을 허용하기 때문에 해당 섹션에 접근하려는 다른 Thread들을 강제적으로 막음으로써 첫 번째 Thread가 해당 세션을 빠져 나올 때까지 기다린다.

다. Semaphore와 Event Count/Sequence 비교

구분 특징 및 설명
Semaphore - 긴급 영역과 상호배제 원리를 지키기 위한 방법
- 무기한 연기의 문제점
- Semaphore 큐에서 대기중의 프로세스들의 Wake up 순서는 결정 되지 않음
Event Count/Sequence - Busy Waiting 문제 해결
- FIFO 스케쥴링에 의해서 Block 된 순서대로 Wake up 됨
- 무기한 연기의 문제점 해결

“끝”

[참고] 강멘토님 교재

라. 작동 원리 설명

- 최초 S 값은 1

- P(S)를 먼저 수행하는 프로세스가 S를 0으로 해놓고, Critical Section 진입

- 나중에 도착하는 프로세스는 P에서 더 이상 진행하지 못하고 대기함

- 먼저 들어갔던 프로세스가 V(S)를 하면 P(S)에서 대기하고 있던 프로세스가 그때 Critical Section에 들어갈 수 있음

- S의 초기값을 “N”으로 하면 최대 N개의 프로세스가 P(S)를 통과하게 됨 이것을 계수(Counting) Semaphore 라고 하며, 자원할당에 사용

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

교착상태(Deadlock)  (0) 2023.11.25
우선순위 역전  (0) 2023.11.24
Mutual Exclusion(상호배제)/뮤텍스  (1) 2023.11.22
RAID  (1) 2023.11.21
HA(High Availability)  (1) 2023.11.20
상 Mutual Exclusion(상호배제)/뮤텍스 [정의] 다중 프로그래밍 환경에서 공유 불가능한 자원의 동시 사용을 피하기 위한 Locking/Unlocking을 사용해 동시성을 제어하는 기법
[요구조건] 상호배제 조건, 진행 조건, 한정 대기 조건, 가정 조건
[구현기술]
HW방식: TAS ( Test And Set )
SW방식: 데커알고리즘, 피터슨알고리즘, 램포트베이커리 알고리즘		  
토픽 이름 Mutual Exclusion   
분류 OS > 병행 제어 > Mutual Exclusion
키워드(암기) 램포트, 피터슨, 데커알고리즘, 세마포어 , swap, test and set, 인터럽트 금지
암기법(해당경우)  

 

기출문제

번호 문제 회차
1 분산처리 시스템에서 Mutual Exclusion을 구현하기 위한 Time Ring 알고리즘과 Time Ordering 알고리즘의 동작을 설명하시오 기96-응-2-3
2 운영체제(OS)에서의 상호배제(Mutual Exclusion)개념을 설명하고 이를 구현하는 방법을 하드웨어적 해결방안 및 소프트웨어적 해결방안으로 구분하여 설명하시오. 기98-응-1-8
3 상호배제에 대하여 설명하고 상호배제 구현을 위한 데커(Dekker), 피터슨(Peterson) 알고리즘에 대해 설명하시오. 모1410-응-2-4
4 운영체제(OS)에서의 상호배제(Mutual Exclusion)개념을 설명하고, 세마포어(Semaphore)를 통한 프로세스 동기화에 대해 설명하시오. 모1610-응-2-1
5 병행프로세스의 동시성 제어를 위한 상호배제 기법을 HW기법과 SW기법으로 나누어서 설명하시오. 모1704-응-4-1
6 운영체제(OS)에서 상호배제(Mutual Exclusion)에 대해 설명하고, 상호배제 구현 방안인 데커 알고리즘, 피터슨 알고리즘에 대해 설명하시오. 합숙2018-관-2일-2-5

 

I. 병행프로세스의 동시성 제어를 위한 상호배제(Mutual Exclusion)의 개요

가. 상호배제(Mutual Exclusion) 정의

- 경쟁조건을 방지하기 위해 특정 프로세스가 공유자원을 사용하고 있을 경우 다른 프로세스가 해당 공유자원을 사용하지 못하게 제어하는 기법

- 상호배제 해결을 위한 요구조건과 상호배제에 대한 소프트웨어적 또는 하드웨어적 해결방안 연계

나. 상호배제 해결을 위한 요구조건

구분 설명 관련사항
상호배제 조건 두 개 이상의 프로세스들이 동시에 임계영역에 있어서는 안됨 임계영역
진행 조건 임계영역 밖의 프로세스가 다른 프로세스의 임계영역 진입을 막아서는 안됨 교착상태
기아상태
한계대기 조건 어떤 프로세스도 임계구역 진입이 무한정 연기되어서는 안됨  
상대속도 조건 프로세스들의 상대적인 속도에 대해서는 어떠한 가정도 하지 않음  

 

II. 상호배제 해결방안

가. 상호배제 해결을 위한 SW 방법

해결방안 설명
데커(Dekker)
알고리즘		 - 두 개 프로세스를 위한 상호배제에 대한 최초 소프트웨어 해결법
- 공유변수 : 두 개 boolean flag(사용의사)와 int turn(차례)
- 차례설정 : turn(차례)를 자신 프로세스에게 설정
피터슨(Peterson)
알고리즘		 - 공유변수 : 두 개 boolean flag(사용의사)와 int trun(차례)
- 의사표시 : 임계영역에 진입하려면 먼저 flag(사용의사)를 true 설정 후 임계영역 진입
- 차례양보 : turn(차례)를 다른 프로세스에게 양보
램포트(Lamport) 알고리즘 - 분산처리 환경에서 유용한 알고리즘으로 수행순서를 위한 번호를 부여받고 낮은 번호가 먼저 수행되는 알고리즘
세마포어(Semaphores) - 운영 체계 또는 프로그램 작성 내에서 상호배제를 지원하는 메커니즘
- 세마포어 변수(S) 및 두 개의 연산(P, V)으로 임계영역에 접근하는 잠금장치에 대한 이론적 기반

나. 상호배제 해결을 위한 HW 방법

해결방안 설명
인터럽트 사용금지 - 공유 변수가 변경되는 동안 인터럽트 발생을 허용하지 않음
- 단일 프로세서에서 가능하고 멀티 프로세서에는 적용할 수 없음
Test and Set - HW에서 한 워드(word)의 내용을 검사하고 변경하는 명령어의 제공

function Test-and-Set(var target: boolean): boolean:
begin
    Test-and-Set := target:
        Target := true;
end;
Swap - HW에서 두 워드간에 내용을 원자적으로 교환할 수 있는 명령어 제공

Procedure Swap (var a, b: boolean);
    var temp: boolean;
    begin
        temp := a;
        a := b;
        b := temp;
    end;

 

III. 상호배제 기법의 발전

- 상호배제 기법은 예전 기법의 단점을 보완하면서 점점 진화 발전해오고 있음

- 더 많은 프로세스가 공유자원을 공유하는 환경에서 개발자가 쉽게 상호배제를 구현할 수 있도록 더욱 진화 발전해갈 것으로 예상됨

반응형
저작자표시 비영리 변경금지

'정보관리기술사 > CA_OS' 카테고리의 다른 글

우선순위 역전  (0) 2023.11.24
Semaphore  (1) 2023.11.23
RAID  (1) 2023.11.21
HA(High Availability)  (1) 2023.11.20
결함허용 컴퓨터(FTS)  (2) 2023.11.19

+ Recent posts

티스토리툴바