명제 $P \rightarrow Q$는 가정인 $P$와 결론인 $Q$로 정의할 수 있다.
명제 $P \rightarrow Q$가 참이면
$$
P \Rightarrow Q
$$
로 표현할 수 있다.
이때 조건 $P$는 $Q$이기 위한 충분조건이라하고, 조건 $Q$는 조건 $P$이기 위한 필요조건이라 한다.
만약 $P \Rightarrow Q$이면서 $Q \Rightarrow P$이면
$$
P \Leftrightarrow Q
$$
로 표현할 수 있다.
이때 조건 $P$는 $Q$이기 위한 필요충분조건이라하고, 마찬가지로 조건 $Q$는 조건 $P$이기 위한 필요충분조건이라 한다.
| 중국인의 나머지 정리 (0) | 2020.03.09 |
|---|
조건1 ~ 조건3이 기본적으로 필요하다.조건4까지 만족되면 교착상태가 발생할 수 있는 필요충분조건이 된다.조건4는 조건1 ~ 조건3의 결과에 의해 발생한다.운영체제 교제에 따라 교착상태의 조건으로
조건1 ~ 4를 동일하게 다루고 있다.하지만 교착상태 예방과 교착상태 회피의 명확한 구분을 위해
조건1 ~ 3과조건4는 다르게 다루어야 한다.
조건1 ~ 3은 정책이며,조건4는 이러한 정책에 의해 발생한 상태이기 때문이다.
조건1 ~ 4를 동일하게 다루면 이후 논의할 교착상태 예방과 교착상태 회피의 명확한 구분이 어려워 진다.
교착상태를 해결하기 위한 다양한 접근 방법들이 제안 되었다.
두 자원 $R_i$ 와 $R_j$ 가 있으며, 운영체제가 $i<j$ 인 할당 순서를 정했다고 하자.
$i<j$ 는 $R_i$ 가 먼저 할당되어야 하며 그 이후에 $R_j$ 가 할당될수 있다는 것을 의미한다.
프로세스 $P$ 가 자원 $R_i$ 를 할당하고 $R_j$ 를 요청했다고 하자.
이 상황에서 교착상태가 발생하려면 다른 프로세스 $Q$ 는 $R_j$ 를 할당하고 $R_i$ 를 요청해야 한다.
하지만, 이것은 운영체제의 자원 할당 순서에 위배개기 때문에 나타날수 없다.
결국, 자원들의 할당 순서를 정하면 교착상태가 발생하지 않는 것이다.
교착상태 회피를 위한 두가지 방법
교착상태 회피를 위해 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정상태와 불안정한 상태로 나누고 시스템이 안정상태를 유지하도록 자원을 할당
COMMING SOON
자원의 접근에 대한 제한이나 프로세스의 행위에 제한을 두지않기 때문에 교착상태가 발생할수 있다.
따라서
의 기능을 지원해야한다.
COMMING SOON
자원 선점에 앞서 어떤 자원과 어느 프로세스가 선점될 것인가?
만약 특정 프로세스을 자원을 강제로 방출하고 선점시켰다면, 그 프로세스를 어떻게 처리 할 것인가?
필요한 자원을 읽은 프로세스는 정상적으로 실행할 수 없으므로, 프로세스를 안정상태로 복귀시키고 다시 시작해야 함.
자원 선점을 통해 기아상태가 발생하지 않을까?
동일한 프로세스가 자원들을 항상 선점하지 않도록 보장할 때, 비용에 근거한 시스템은 동일한 프로세스가 희생자로 선택되기 쉬움.
프로세스가 짧은 시간 동안만 희생자로 지정됨을 보장해야 함.
일반적인 해결 방법은 비용 요소에 복귀 횟수를 포함시키는 것.
『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미
『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미
『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL
| 08. CPU 스케줄링 알고리즘 (0) | 2019.12.23 |
|---|---|
| 07. CPU 스케줄링 개요 (0) | 2019.12.22 |
| 05. 상호배제와 동기화 [2/2] (0) | 2019.12.15 |
| 05. 상호배제와 동기화 [1/2] (0) | 2019.12.15 |
| 04. 병행 프로세스 (0) | 2019.12.15 |
제출일 : 2019-12-16
문제 풀이 시간 : 25M
난이도 : ★★
link : https://swexpertacademy.com/main/learn/course/subjectDetail.do?subjectId=AWWxyoNqAiQDFAW4
그러나 비싼 비용의 문제에 부딪혀, 정부는 최소 비용으로 모든 도시 간을 이동할 수 있게 하고 싶어한다.
또한 하나의 제약이 더 있는데, 언덕 등을 깎지 않는 친환경 건설을 위해 어떤 도시끼리는 직접 도로를 이을 수 없다.
친환경 건설을 위해 이을 수 있는 도로의 목록이 주어질 때, 정부를 도와 모든 도시 간을 잇는 고속도로를 건설하는 최소 비용을 알아내자.
첫 줄에 테스트케이스의 개수 T가 주어진다. (1 ≤ T ≤ 8)
각 테스트 케이스의 첫 번째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 50,000)
각 테스트 케이스의 두 번째 줄에 도로 후보의 수 M이 주어진다. (1 ≤ M ≤ 200,000)
각 테스트 케이스의 세 번째 줄부터 M개의 줄에 걸쳐 각 도로 후보의 정보 s, e, c가 주어진다.
s와 e는 도로 후보가 잇는 각 도시의 번호이고, c는 그 도로를 건설하는데 드는 비용이다. (1 ≤ c ≤ 10,000)
항상 모든 도시를 잇는 고속도로를 건설할 수 있는 입력만 주어진다.
각 테스트케이스마다 한 줄에 걸쳐, 테스트케이스 수 “#(TC) “를 출력하고, 모든 도시를 잇는 고속도로를 건설하는데 드는 최소 비용을 출력한다.
1
5
8
1 2 4
1 3 9
1 4 21
2 3 8
2 4 17
3 4 16
5 2 20
5 4 30
#1 48
크루스칼 알고리즘을 이용하여 구현하였다.
시간 복잡도를 줄이기 위해 PriorityQueue를 이용하여 가장 적은 비용의 간선을 추출하고 Union-Find알고리즘을 이용 싸이클을 검사했다.
MST 알고리즘은 예전에 확실히 개념을 공부하고 기억하고 있어 쉽게 구현이 가능했다.
언어 : JAVA
import java.io.FileInputStream;
import java.util.PriorityQueue;
import java.util.Scanner;
public class Solution {
final static int MAX = 50009;
static PriorityQueue<Edge> pq;
static int parents[] = new int[MAX];
static int N, M, ans;
static class Edge implements Comparable<Edge> {
int start, end, cost;
public Edge(int start, int end, int cost) {
this.start = start;
this.end = end;
this.cost = cost;
}
@Override
public int compareTo(Edge o) {
return this.cost > o.cost ? 1 : -1;
}
}
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("res/input.txt"));
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int tc = 1; tc <= T; tc++) {
N = sc.nextInt();
M = sc.nextInt();
pq = new PriorityQueue<>();
for (int i = 1; i <= M; i++) {
pq.add(new Edge(sc.nextInt(), sc.nextInt(), sc.nextInt()));
}
ans = 0;
makeSet();
while (!pq.isEmpty()) {
Edge e = pq.poll();
int x = find(e.start);
int y = find(e.end);
if (x == y)
continue;
else {
ans += e.cost;
union(x, y);
}
} // end of while
System.out.println("#" + tc + " " + ans);
}
}// end of main
private static void union(int x, int y) {
if (x > y)
parents[x] = parents[y];
else
parents[y] = parents[x];
}
private static int find(int x) {
if (x == parents[x])
return parents[x];
else
return x = find(parents[x]);
}
private static void makeSet() {
for (int i = 1; i <= N; i++) {
parents[i] = i;
}
}
}| [SWEA] 2819. 격자판의 숫자 이어 붙이기 (D4) (Java) (0) | 2020.02.18 |
|---|---|
| [SWEA] 1204. [S/W 문제해결 기본] 1일차 - 최빈수 구하기 (D2) (0) | 2020.01.12 |
| [SWEA] 3813. 그래도 수명이 절반이 되어서는... (0) | 2019.12.13 |
| [SWEA] 3816. 아나그램 (0) | 2019.12.11 |
| [SWEA] 3819. 최대 부분 배열 (0) | 2019.12.10 |
| 수준 | 방법 | 종류 | |
|---|---|---|---|
| 고급 | 소프트웨어로 해결 | 데커 알고리즘 | 다익스트라 알고리즘 |
| 크누스 알고리즘 | 램포트의 베이커리 알고리즘 | ||
| 핸슨 알고리즘 | 소프트웨어가 제공 - 프로그래밍 언어와 운영체제 수준에서 제공 |
세마포어 | 모니터 |
| 저급 | 하드웨어로 해결 - 원자 수준의 연산 |
테스(TES, TestAndSet) | |
01 program dekkersalgorithm;
02 var fprocess: (first, second); // 공유 변수
03 P1_enter, P2_enter : boolean;
04 procedure P1; // 프로세스 P1의 임계영역 진입 절차
05 begin
06 while true do
07 begin
08 P1_enter := true; // P1이 임계영역 진입 시도
09 while P2_enter do; // P2의 임계영역 진입 여부 확인
10 if fprocess = second then // P2의 진입 차례(기회)라면
11 begin
12 P1_enter := false; // P2에게 진입 순서 양보
13 while fprocess = second do; // 순서 기다림(P2 완료)
14 P1_enter := true // P1이 임계영역 재진입 시도
15 end;
16 criticalsectionone; // 임계영역
17 fprocess := second; // P2에게 진입 순서 양보
18 P1_enter := false; // P1의 임계영역 사용 완료 지정
19 otherstuffone // P1의 잔류영역 수행
20 end;
21 end;
22 procedure P2;
23 begin
24 while true do
25 begin
26 P2_enter := true;
27 while P1_enter do;
28 if fprocess = first then
29 begin
30 P2_enter := false;
31 while fprocess = first do;
32 P2_enter := true;
33 end;
34 criticalsectiontwo;
35 fprocess := first;
36 P2_enter := false;
37 otherstufftwo
38 end;
39 end;
40 begin
41 P1_enter := false;
42 P2_enter := false;
43 fprocess := first;
44 parbegin
45 P1;
46 P2;
47 parend;
48 end.// target을 검사하고, target 값을 true로 설정
boolean TestAndSet(boolean *target){
boolean temp = *target; // 이전 값 기록
*target = true; // true로 설정
return temp; // 값 반환
}do{
while(TestAndSet(&lock)) // lock을 검사하여 true이면 대기, false이면 임계 영역 진입
; // 아무것도 하지 않음
lock = false; // 다른 프로세스의 진입 허용 의미로 lock을 false로
}while(true);do{ // 프로세스 Pi의 진입 영역
waiting[i] = true;
key = true;
while(waiting[i] && key)
key = TestAndSet(&lock);
waiting[i] = false;
//임계 영역
//탈출 영역
j = (i + 1) % n;
while((j != i) && !waiting[j]) // 대기 중인 프로세스를 찾음
j = (j + 1) % n;
if(j == i) // 대기 중인 프로세스가 없으면
lock = false; // 다른 프로세스의 진입 허용
else // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입
waiting[j] = false; // Pj가 임계영역에 진입할 수 있도록
//나머지 영역
}while(true);프로세스를 대기시키는 wait 동작으로 임계 영역에 진입하기 위한 연산
P(S) : wait(S)
while S <= 0
; // 바쁜 대기, S > 0 이 될때까지 대기
S--;
}대기 중인 프로세스를 깨우는 신호를 보내는 signal 동작으로 임계 영역에서 나오기 위한 연산.
V(S) : signal(S){
S++; // 다른 프로세스의 접근 허용
}세마포어 S에 적용된 두 연산 P, V는 동시에 두 가지 동작이 실행되는 것을 예방하는 상호 배제를 의미함.
n개의 프로세스는 1로 초기화된 공통 세마포어인 mutex(Mutual Exclusion)를 공유.
do{
wait(mutex);
//임계영역
signal(mutex);
//나머지 영역
}while(true);조건 : S2는 S1이 끝난 후에만 수행되도록 구현함.
S1;
signal(synch);
wait(synch);
S2;
유한한 자원에 접근 제어 가능, 여러 번 획득, 해제할 수 있도록 count 자원의 사용 허가 값으로 사용
사용 가능한 자원 수로 초기화하므로, count를 초기의 세마포 수로 초기화
각 프로세스가 자원 사용하려면 P 연산 수행
프로세스가 자원 해제할 때 V 연산 수행
세마포어는 제어된 변수로, P와 V의 초기 작업 때만 값이 변할 수 있음.
이진 세마포어는 0, 1 값만 가짐.
한 프로세스가 임계 영역에 있을 때, 임계영역에 들어가기를 원하는 다른 프로세스가 진입코드를 계속 순환하여 프로세스 시간 낭비함.
struct semaphore{
int count;
queueType queue;
}
semaphore S;wait(S){
S -> count--;
if(S->count < 0){
add this process to S -> queue; // 프로레스를 준비 큐에 추가
block(); // 프로세스 중단(일시정지)
}
}signal(S){
S->count++;
if(S->count <= 0){
remove a process P from S -> queue; // 준비 큐에서 P 프로세스를 제거
wakeup(P); // 신호를 보내 프로세스를 실행
}
}P와 V 연산을 수행하는 중에 인터럽트를 금지함
인터럽트 금지할 수 없어, 다른 프로세스의 명령어가 임의의 방법으로 끼어들 수 있음.
하드웨어가 특별한 명령을 제공하지 않으면, 소프트웨어적 해결 방법을 사용해야 함.
응용 프로그램의 진입 영역에서 임계 영역까지 바쁜 대기 제거 해야 함.
바쁜 대기는 아주 짧은 기간 동안만 일어나지만, 어떤 응용 프로그램에서는 임계 영역 이 아주 길거나 항상 점유되어 있는 상황이 발생할 수 있음.
모니터는 3번째 특징에 의해 상호배제기능을 제공하게 된다.
/* 생산자/소비자 프로그램 */
monitor boundedbuffer;
char buffer [N]; /* N개의 문자가 저장될 수 있는 버퍼 */
int nextin, nextout; /* 버퍼 포인터 */
int count; /* 버퍼 내부에 추가된 문자수 */
cond notfull, notempty; /* 동기화를 위한 조건 변수 */
void append(char x)
{
if (count == N) /* 버퍼에 문자가 가득 찬 경우, 오버플로 방지 */
cwait(notfull);
buffer[nextin] = x;
nextin = (nextin + 1) % N;
count++; /* 버퍼에 문자 하나를 추가 */
csignal(notempty); /* not empty 조건 변수에서 대기하고 있는 프로세스를 꺠움 */
}
void take(char x)
{
if (count == 0) /* 버퍼가 빈 경우, 언더플로 방지 */
cwait(notempty);
x = buffer[nextout];
nextout = (nextout + 1) % N;
count--; /* 버퍼에서 문자 하나를 삭제 */
csignal(notfull); /* not full 조건 변수에서 대기하고 있는 프로세스를 깨움 */
}
{ /* 모니터 몸체(body) */
nextin = 0; /* 버퍼 변수 초기화 */
nextout = 0;
count = 0;
}
void producer()
{
char x;
while(true)
{
produce(x);
append(x);
}
{
void consumer()
{
char x;
while (true)
{
take(x);
consume(x);
}
}
void main()
{
parbegin(producer, consumer);
}『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미
『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미
『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL
| 07. CPU 스케줄링 개요 (0) | 2019.12.22 |
|---|---|
| 06. 교착상태 (0) | 2019.12.16 |
| 05. 상호배제와 동기화 [1/2] (0) | 2019.12.15 |
| 04. 병행 프로세스 (0) | 2019.12.15 |
| 03. 스레드(Thread) (1) | 2019.12.15 |
병행 프로세스에서 프로세스 하나가 공유 자원 사용 시 다른 프로세스들이 동일한 일을 할 수 없도록 하는 방법
읽기 연산은 공유 데이터에 동시에 접근해도 문제 발생하지 않음.
프로세스는 아래 세 가지 형태로 상호작용 함.
공유 데이터의 선언
#define BUFFER_SIZE 10 //버퍼 크기
typedef struct{
DATA data;
} item;
item buffer[BUFFER_SIZE];
int in = 0;
int out = 0;
int counter = 0;생산자와 소비자 프로세스
생산자 프로세스는 생산하는 새로운 원소를 지역변수 nextProduced에 저장, 소비자 프로세스는 소비하는 원소를 지역변수 nextConsumed에 저장 각 프로세스 구현
item nextProduced;
while(true){
//버퍼가 가득 차 아무 일도 하지 않음
while(counter == BUFFER_SIZE);
buffer[in] = nextProduced;
in = (in + 1) % BUFFER_SIZE;
counter++;
}
item nextConsumed;
while(true){
//버퍼가 가득 차 아무 일도 하지 않음
while(counter == 0);
nextConsumed = buffer[out];
out = (out + 1) % BUFFER_SIZE;
counter--;
}
counter++와 counter-- 기계어
두 코드의 동시 수행시 counter 값이 맞는기 기계어로 작성 확인
rigister1 = counter;
register1 = register1 + 1;
counter = register1;
rigister2 = counter;
register2 = register1 - 1;
counter = register2;
T1 : 생산자가 register1 := counter를 수행 (register1 = 5)
T2 : 생산자가 register1 := counter1 + 1을 수행 (register2 = 6)
T3 : 소비자가 register2 := counter를 수행 (register2 = 5)
T4 : 소비자가 register2 := register2 – 1을 수행 (register2 = 4)
T5 : 생산자가 counter := register1을 수행 (counter = 6)
T6 : 소비자가 counter := register2를 수행 (counter = 4)
둘 이상의 프로세스가 공유할 수 없는 자원을 임계자원이라 하며, 프로그램에서 이를 이용하는 부분.
프로세스 하나가 임계 영역에 있으면 다른 프로세스가 임계 영역에 들어가지 못하게 하는 것.
임계 영역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야 함.
임계 영역을 떠나는 프로세스는 출구 상호배제를 수행함으로써 다른 프로세스가 임계 영역에 들어갈 수 있도록 함.
『IT CookBook, 운영체제』, 구현회 집필, 한빛아카데미
『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미
『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL
| 06. 교착상태 (0) | 2019.12.16 |
|---|---|
| 05. 상호배제와 동기화 [2/2] (0) | 2019.12.15 |
| 04. 병행 프로세스 (0) | 2019.12.15 |
| 03. 스레드(Thread) (1) | 2019.12.15 |
| 02. 프로세스 (0) | 2019.12.14 |
프로세스 여러 개가 동시에 실행되는 것.
비동기적 병행 프로세스
상호 작용
다수의 프로세서를 이용하여 작업을 수행하며, 다중 프로세싱 시스템, 분산 처리 환경, 다중 프로그래밍 운영체제에서 매우 중요함.
시스템의 신뢰도 향상과 처리 속도 개선을 통한 처리 능력 증대에 매우 중요함.
프로세스는 프로세스 집합과 이들의 선행 제약(Precedence Constraint)의 두 가지 요소로 정의
간단한 산술 연산을 수행하는 알고리즘
a := x + y; → S1
b := z + 1; → S2
c := a - b; → S3
w := c + 1; → S4
프로그램의 여러 문장의 선행 관계 명시를 위해 두 가지 언어구조 제시
선행 그래프는 연산 부분의 선행 제약을 정의하는데 유용하나, 2차원이므로 프로그래밍 언어에서 사용하기에 어려움.
병행을 최초로 언어적 표현으로 명시.
count := 2;
fork L1;
a := x + y;
go to L2;
L1 : b := z + 1;
L2 : join count;
c := a – b;
w := c + 1;
일반적인 형태
parbegin S1; S2; ......; Sn; parend;보다 효과적인 병행 문장은 S0과 Sn+1 문장을 추가하여 아래와 같이 정의 가능.
S0; parbegin S1; S2; ......; Sn; parend; Sn+1;위의 간단한 산술연산의 예를 parbegin/parend로 표현하면 아래와 같다.
parbegin
a := x + y;
b := z + 1;
parend;
c := a – b;
w := c + 1;『IT CookBook, 운영체제(개정3판)』, 구현회 집필, 한빛아카데미
『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미
『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL
| 05. 상호배제와 동기화 [2/2] (0) | 2019.12.15 |
|---|---|
| 05. 상호배제와 동기화 [1/2] (0) | 2019.12.15 |
| 03. 스레드(Thread) (1) | 2019.12.15 |
| 02. 프로세스 (0) | 2019.12.14 |
| 01. 운영체제의 개요 (0) | 2019.12.13 |
프로세스의 작업 과정
- 프로세스의 생성: OS는 코드와 데이터를 메모리에 가져오고, PCB를 생성하고 작업에 필요한 메모리를 확보
- CPU 스케줄러가 프로세스가 해야하는 일을 CPU에 전달하고 실제 작업을 수행한다.
- 이때, CPU에 전달 하는 일 하나를 스레드라고 한다.
스레드는 프로세스의 실행 단위라고 할 수 있습니다.
한 프로세스 내에서 동작되는 여러 실행 흐름으로프로세스 내의 주소 공안이나 자원을 공유할 수 있습니다.
스레드는 스레드 ID, 프로그램 카운터, 레지스터 집합, 그리고 스택으로 구성됩니다.
같은 프로세스에 속한 다른 스레드와 코드, 데이터 섹션, 그리고 열린 파일이나 신호와 같은 운영체제 자원들을 공유합니다.
스레드별로 실행 환경 정보가 따로 있지만 서로 많이 공유하므로, 프로세스보다 동일한 프로세스의 스레드에 프로세서를 할당하거나 스레드 간의 문맥 교환이 훨씬 경제적
하나의 프로세스를 다수의 실행 단위로 구분하여 자원을 공유하고 자원의 생성과 관리의 중복성을 최소화하여 수행 능력을 향상시키는 것
프로세스 내 작업을 여러 개의 스레드로 분할함으로써 작업의 부담을 줄이는 프로세스 운영 기법
운영체제가 소프트웨어적으로 프로세스를 작은 단위의 스레드로 분할하여 운영하는 기법
운영체제가 CPU에 작업을 줄 때 시간을 잘게 나누어 배분하는 기법
CPU를 여러 개 사용하여 여러 개의 스레드를 동시에 처리하는 작업 환경으로 이는 병렬 처리에서 슈퍼 스칼라 기법과 같다.
멀티 프로세싱은 하나의 컴퓨터에 여러 개의 CPU 혹은 하나의 CPU 내 여러 개의 코어(core)에 스레드를 배정하여 동시에 작동시키는 것
네트워크로 연결된 서로 다른 컴퓨터에 여러 개의 스레드가 나누어져 협업하는 분산 시스템도 멀티 프로세싱이라 부른다.
스레드는 멀티태스킹의 낭비 요소를 제거하기 위해 사용된다. 비슷한 일을 하는 2개의 프로세스를 만드는 대신, 코드, 데이터 등을 공유하면서 여러 개의 일을 하나의 프로세스 내에서 하는 것이다.
프로세서는 크게 정적인 영역과 동적인 영역으로 구분된다.
정적인 영역은 코드 전역 데이터 파일등 프로세스가 실행되는 동안 바뀌지 않는 영역
동적인 영역은 스레드가 작업을 하면서 값이 바뀌거나 새로 만들어지거나 사라지는 영역
커널 스레드: 커널이 직접 생성하고 관리하는 스레드
사용자 스레드: 라이브러리에 의해 구현된 일반적인 스레드
『IT CookBook, 운영체제(개정3판)』, 구현회 집필, 한빛아카데미
『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미
『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL
| 05. 상호배제와 동기화 [2/2] (0) | 2019.12.15 |
|---|---|
| 05. 상호배제와 동기화 [1/2] (0) | 2019.12.15 |
| 04. 병행 프로세스 (0) | 2019.12.15 |
| 02. 프로세스 (0) | 2019.12.14 |
| 01. 운영체제의 개요 (0) | 2019.12.13 |
프로세스의 상태 변화는 운영체제가 프로세서 스케줄러 이용하여 관리
작업 스케줄러는 스풀러가 디스크에 저장한 작업 중 실행할 작업 선정하고 준비 리스트에삽입하여 다중 프로그래밍의 정도 결정
프로세스 스케줄러는 선정한 작업의 상태를 변화시키며 프로세스의 생성에서 종료까지 과정 수행
프로그램이 메모리에 올라오고 운영체제로부터 프로세스 제어 블록을 할당받은 상태
생성된 프로세스는 바로 실행되는 것이 아니라 준비 상태에서 자기 순서를 기다리며, 프로세스 제어 블록도 같이 준비 상태로 옮겨짐
대부분의 프로세스는 생성, 준비, 실행, 대기, 완료 상태로 운영되며 이 다섯가지 상태를 활성 상태(active stauts)라고 한다.
| 상태 | 설명 | 작업 |
|---|---|---|
| 생성 | 프로그램을 메모리에 가져와 실행 준비가 완료된 상태 | 메모리 할당, 프로세스 제어 블록 생성 |
| 준비 | 실행을 기다리는 모든 프로세스가 자기 차례를 기다리는 상태 실행될 프로세스를 CPU 스케줄러가 선택한다. |
dispatch(PID): 준비 → 실행 |
| 실행 | 선택된 프로세스가 타임 슬라이스를 얻어 CPU를 사용하는 상태 프로세스 사이의 문맥 교환이 일어난다. |
timeout(PID): 실행 → 준비 exit(PID): 실행 → 완료 block(PID): 실행 → 대기 |
| 대기 | 실행 상태에 있는 프로세스가 입출력을 요청하면 입출력이 완료될때까지 기다리는 상태 입출력이 완료되면 준비상태로 간다. |
wakeup(PID): 대기 → 준비 |
| 완료 | 프로세스가 종료된 상태 사용하던 모든 데이터가 정리됨 정상종료인 exit와 비정상 종료인 abort를 포함 |
메모리 삭제, 프로세스 제어 블록 삭제 |
각 프로세스의 고유 식별자
운영체제 내에 있는 여러 프로세스를 구현하기 위한 구분자
fork() 시스템 호출은 실행 중인 프로세스를 복사하는 함수이다. 이때 실행하던 프로세스는 부모 프로세스 새로 생긴 프로세스는 자식 프로세스로서 부모-자식 관계가 된다.
기존의 프로세스를 새로운 프로세스로 전환(재사용)하는 함수
exec() 시스템 호출을 사용하는 목적은 프로세스의 구조체를 재활용 하기 위함.
『IT CookBook, 운영체제(개정3판)』, 구현회 집필, 한빛아카데미
『IT CookBook, 쉽게 배우는 운영체제』, 조성호 집필, 한빛아카데미
『운영체제 : 내부구조 및 설계원리 (6판)』, WILLIAM STALLINGS 저, PEARSON HALL
| 05. 상호배제와 동기화 [2/2] (0) | 2019.12.15 |
|---|---|
| 05. 상호배제와 동기화 [1/2] (0) | 2019.12.15 |
| 04. 병행 프로세스 (0) | 2019.12.15 |
| 03. 스레드(Thread) (1) | 2019.12.15 |
| 01. 운영체제의 개요 (0) | 2019.12.13 |