9 February 2022 / OS

OS(9) - Midterm

OS 관련 포스팅

1.

프로세스 P1, P2, P3 의 CPU burst time 은 각각 4, 2, 8 msec 이며,
세 프로세스는 각각 다른 시간에 ready queue 에 도착했다.
즉 P1 은 0 msec에, P2 는 1 msec에, P3 는 5 msec 에 각각 도착했다.
CPU scheduling 에 대한 아래 물음에 답하라.
(※ 각 경우마다 Gantt chart를 그리고 수식도 적어라.
답은 계산하지 않아도 되지만, 반드시 단위는 기록해야 한다).

→ 먼저, process별로 알아보기 쉽게 표를 작성

process	Arrival Time(msec)	Burst Time(msec)	Priority
P1	0	4	3
P2	1	2	2
P3	5	8	1

(a) FCFS 스케쥴링을 사용하면 평균 대기시간(average waiting time)은 얼마인가?
→ First Come First Served
→ AWT = ( 0 + 3 + 1) / 3 = 4/3msec

P1	P2	P3
0 1 4 ↑ ↑ P1 P2	5 6 ↑ P3	14

(b) 선점형(preemptive) SJF 스케쥴링을 사용할 때 평균반환시간(average turnaround time)은 얼마인가?
→ Shortest Job First
→ P1의 burst time은 4로 P2보다 길지만 0msec에 P1만 도착해있으므로 P1부터 실행함
→ 1msec에서 burst time이 짧은 것은 P2이므로 P2실행
→ preemptive이므로 강제전환 가능
→ ATT: 도착부터 서비스가 끝나서 나가기까지 걸리는 시간
→ ATT = ( 6 + 2 + 9) / 3 = 17/3msec

P1	P2	P1	P1	P3
0 1	3	5	6	14

(c) Time quantum 이 무한대 (∞) 인 Round-Robin scheduling을 적용하면 평균반환시간은 얼마인가?
→ Time quantum = ∞ 이므로 FCFS와 같은 scheduling 양상을 보임
→ AWT = ( 4 + 5 + 9) / 3 = 18/3 = 6msec

(d) 비선점형(nonpreemptive) 우선순위(priority) 스케쥴링을 사용하면 처리율(throughput)은 얼마인가? 단, 프로세스 P1, P2, P3 의 우선순위는 각각 3, 2, 1 이며, 숫자가 작을수록 우선순위가 높다.
→ Priority scheduling이지만 non-preemptive이므로 강제전환 불가
→ priority가 더 낮은 P1이 끝나야 P2실행 가능
→ throughput: 단위 시간당 처리한 작업의 수
→ throughput = 3/14 jobs/msec

2.

프로세스 P1, P2, P3 의 코드는 각각 다음과 같다. 세마포(semaphore)를 사용하여 아래 조건이 각각 만족되도록 프로세스의 코드를 수정하라. 세마포의 초기값도 나타내어야 한다. 세마포는 한 개 또는 여러 개를 사용할 수 있다.

P1: S1
P2: S2
P3: S3

(a) S1 이 끝나야 S2 나 S3 가 실행된다. S2, S3 의 순서는 상관없다.

sem.value = 0;
P1: S1; sem.release(); sem.release();
P2: sem.acquire(); S2;
P3: sem.acquire(); S3;

(b) S1 과 S2 가 모두 끝나야만 S3 가 실행된다. S1, S2 의 순서는 상관없다.

semaphore 2개 쓰는 경우,
sem.value = 0;
sem2.value = 0;
P1: S1; sem.release();
P2: S2; sem2.release();
P3: sem.acquire(); sem2.acquire(); S3;
semaphore 1개 쓰는 경우,
sem.value = 0;
P1: S1; sem.release();
P2: S2; sem.release();
P3: sem.acquire(); sem.acquire(); S3;

(c) S1, S2, S3 의 순서대로 실행된다. 즉 S1 → S2 → S3 의 순서를 따라야 한다.

sem.value = 0;
sem2.value = 0;
P1: S1; sem.release();
P2: sem.acquire(); S2; sem2.release();
P3: sem2.acquire(); S3;

3.

a) 프로세스 동기화(process synchronization)란 무엇을 의미하는가?
→ 올바른 계산 결과가 나올 수 있도록 임계구역(Critical Section) 문제를 해결하는 것
→ process의 실행 순서를 제어하는 것

b) 세마포의 내부 구조를 그림으로 나타내고 간략히 설명하라.
→ 어떤 process가 acquire()를 호출하면 value가 1감소하고 그 결괏값이 0보다 작으면 해당 process를 queue에 가둠
→ 어떤 process가 release()를 호출하면 value가 1증가하고 그 결괏값이 0보다 작거나 같으면 queue에 갇혀있는 process를 깨움(= ready queue에 넣음)

c) 어떤 세마포에 다섯 개의 프로세스가 블록(block)되어있다고 가정하자.
이때 세마포 내부의 정수 값(value)은 얼마인가?
→ 처음 sem.value = 0; 일때, 어떤 process가 acquire()를 호출하면 value = -1이 되고 block 됨. 이 원리로 5개의 process가 acquire()를 호출하면 value = -5가 되고 모두 block됨

4.

a) 시스템 콜(system call)과 소프트웨어 인터럽트(software interrupt)는 어떤 관련성이 있는가?
→ 시스템 콜은 운영체제 서비스를 받기 위해 호출하며 s/w interrupt로 만듦

b) 유닉스/리눅스 운영체제에서 fork() 시스템 콜은 어떤 용도로 사용되는가?
→ 하나의 parent process에서 여러 개의 child process를 만드는 목적으로 사용함

c) 자신이 알고 있는 유닉스/리눅스 시스템 콜의 종류를 세 가지 나열하고 간략히 설명하라.
→ exit(): process 종료
→ open(): file 열기
→ close(): file 닫기
→ read(): file 읽기
→ write(): file 쓰기
→ exec(): 생성된 process에 실행 파일을 복사해 넣음

5.

다음 용어의 의미를 간략히 설명하라.
a) parent process
→ process는 process에 의해 만들어지는데, 자신을 만든 process를 parent process라고 함

b) command interpreter
→ 사용자에게 명령을 받아 그 명령을 번역한 뒤 실행함. os에서는 shell이라고 함

c) job scheduler
→ job queue 안의 여러 process 중 어떤 것을 main memory로 올려보낼지 결정함.
long-term scheduler

d) multi-level queue scheduling
→ 여러 개의 queue가 존재. 각각의 queue에 절대적인 우선순위가 존재하거나 CPU time을 차등배분하여 독립된 scheduling 정책을 시행함

6.

생산자-소비자 문제는 mutex, empty, full 등 세 가지 세마포를 사용하여 해결할 수 있다. mutex 는 상호배타 목적, empty 와 full 은 각각 버퍼의 빈 공간 및 차있는 공간에 대한 접근목적으로 사용한다.

a) 버퍼에서 데이터를 빼내어 소비하는 동작을 위 세마포를 포함한 코드로 작성하라.

full.acquire();
mutex.acquire();
buf
count–;
mutex.release();
empty.release();

b) 생산자와 소비자는 프로세스, 각 세마포는 자원이라고 가정하자.
생산자는 버퍼에 대한 접근 허용을 기다리고 있고, 소비자는 버퍼에서 데이터를 빼내어 소비하는 상황을 나타내는 자원할당도(resource allocation graph)를 그려라.
단, 버퍼 크기는 10이고 그 중 8개가 차있다고 가정한다.
→

7.

a) 교착상태(deadlock)가 일어나기 위한 네 가지 필요조건 중 보유 및 대기(hold and wait) 란 무슨 의미인가?
→ 한 가지 자원을 가지고 있으면서 또 다른 자원을 가지려고 대기하는 것

b) 식사하는 철학자 문제(dining philosopher problem)에서 보유 및 대기 조건이 만족되지 않게 하려면 어떻게 해야 하는가?
→ 1. 젓가락 두 개를 동시에 집도록 함
→ 2. 한 젓가락을 집고, 다른 하나는 이미 사용 중이라면 가지고 있던 젓가락을 내려 놓음
(일부 자원만 이용가능하면 보유 자원을 모두 포기)

cf.

a) 교착상태(deadlock)가 일어나기 위한 네 가지 필요조건 중 환형대기(circular wait) 란 무슨 의미인가?
→ 자원할당도 상에 원이 만들어짐

b) 식사하는 철학자 문제(dining philosopher problem)에서 환형대기 조건이 만족되지 않게 하려면 어떻게 해야 하는가?
→ 자원에 번호를 부여하고 오름(또는 내림) 차순으로 요청하기
→ 짝수번 철학자는 왼쪽에서 오른쪽 순서로, 홀수번 철학자는 오른쪽에서 왼쪽 순서로 젓가락 들기

8.

아래 문제에서 변수 n, i, s 는 각 프로세스의 지역변수이며, value 는 모든 프로세스가 공통적으로 사용하는 전역변수이다. 프로세스 P1 과 P2 의 코드는 각각 다음과 같다.

P1 while (true) {
    value = value + n;
    n++;
    }

P2 while (true) {
    for (i = 0; i < 100; i++)
        s = s + i;
        value = value - s;
    }

(a) 프로세스 동기화 문제에서 임계구역(critical section)이란 무엇을 의미하는가?
→ 공통 변수(common variable)를 업데이트 하는 구간

(b) 위 P2 프로세스의 코드 내용 중 임계구역에 해당되는 부분은 어디인가? 이유도 설명하라.
→ value = value - s;
→ 이유: 임계구역은 공통변수를 업데이트하는 구간임.
value는 모든 프로세스가 공통 사용하는 공통변수

(c) 세마포어(semaphore)를 사용하여 P1, P2 코드의 임계구역 문제를 해결하라. 세마포어의 초기 값도 나타내어라.

sem.value = 1; // mutual exclusion용 semaphore  
P1 while(true) {  
    sem.acquire();  
    value = value + n;  // Critical Section
    sem.release();  
    n++;  
}  
P1 while(true) {  
    for(i = 0; i < 100; i++)  
        s = s + i;  
        sem.acquire();  
        value = value - s;  // Critical Section
        sem.release();  
}

(d) 프로세스 스케쥴링 방식과 관계없이 항상 P1 이 P2 보다 전역변수 value 값을 먼저 업데이트 하도록 세마포어를 사용하여 위 P1, P2 의 코드를 수정하여라. 세마포어의 초기 값도 나타내어라.

sem.value = 1; // mutual exclusion용 semaphore
sem2.value = 0; // ordering용 semaphore
P1 while(true) {
    sem.acquire(); 
    value = value + n; // Critical Section
    sem.release(); 
    sem2.release();
    n++;
}
P1 while(true) {
    for(i = 0; i < 100; i++)
        s = s + i;
        sem.acquire();
        sem2.acquire();
        value = value - s; // Critical Section
        sem.release();
}

9.

프로세스(process)와 쓰레드(thread)의 유사점 및 차이점을 각각 설명하라.

process → 메모리 공간이 따로 존재
thread → 동일한 메모리 공간을 공유
유사점 → context switching이 일어남

10.

a) 프로세서(processor)의 이중모드(dual mode)란 무엇을 의미하는가?
→ 한 컴퓨터를 여러 사람이 동시에 접속하거나, 한 사람이 여러 프로그램을 동시에 사용하는 환경에서 사용자 모드와 관리자 모드를 나누는 것. 관리자 모드에서만 특권명령과 하드웨어 접근이 가능함

b) 이중모드를 사용한 입출력장치(i/o devices) 보호 방법에 대해 설명하여라.
→ I/O 명령을 관리자(시스템)모드로 만들어 사용자 모드에서 I/O명령 사용시 SW interrupt가 발생해 해당 process를 종료함

11.

프로세스의 상태는 new, ready, running, waiting, terminated 등 다섯 종류로 나눌 수 있다.
a) 프로세스 상태 변화를 보여주는 상태천이도(state transition diagram)를 그려라.
→

b) ready 와 waiting 상태는 어떻게 다른지 구분하여 설명하라.
→ ready: CPU 서비스를 받기 위해 기다리는 것
→ waiting: I/O 서비스를 받기 위해 기다리는 것

OS(9) - Midterm

1.

2.

3.

4.

5.

6.

7.

cf.

8.

9.

10.

11.

OS(10) - Main Memory Management

OS(8) - Monitor

1.

2.

3.

4.

5.

6.

7.

cf.

8.

9.

10.

11.

백엔드 개발자의 노트