운영체제 문제풀이

Solaris: 선 마이크로시스템즈사의 유닉스 운용 체계 버전으로 주로 웹 서버용으로 많이 사용

 

하드웨어 -> 운영체제 -> 응용 프로그램 -> 사용자

 

커널: 컴퓨터가 가동중인 상태에서 주기억장치에 상주하면서 컴퓨터 하드웨어를 제어하고 프로세스 등 여러 자원을 배분하고 관리하는 핵심 역할

 

프로세스 종류

1. 운영체제 프로세스: 프로세스 실행 순서를 제어하거나 사용하고 있는 프로세스가 다른 사용자나 운영체제 영역을 침범하지 못하게 감시하는 기능을 가짐

2. 사용자 프로세스: 사용자 코드를 수행한다.

3. 병행 프로세스: 프로세스 여러 개가 동시에 실행되면 병행 프로세스

 

프로세스 상태:

생성 상태: 사용자가 요청한 작업이 커널에 등록되어 커널 공간에 PCB가 만들어진 상태

준비 상태: 입출력 완료 또는 신호의 수신 같은 사건이 일어나기를 기다리는 상태

살행 상태: 프로세스의 프로그램코드가 기억장치로부터 일겨지면서 프로세서에 의해 실행되고 있는 상태

대기 상태: 프로세스가 임의의 자원을 요청한 후 이를 할당받을 때까지 기다리고 있는 상태

완료 상태: 프로세스가 자신의 연산을 모두 마치면, 완료 상태로 전환되고 그 프로세스에게 할당되었던 기억장치, CPU등 모든 자원이 해제된다.

 

프로세스가 전이되는 시기와 이유

1) 디스패치(Dispatch): 준비상태 -> 실행상태

- 준비 상태의 프로세스들 중에서 우선순위가 가장 높은 프로세스를 선정하여 CPU를 할당한다.

- 단기 Scheduler에 의해 선택된 프로세스가 실질적으로 CPU를 할당받는 기능

 

2) 할당시간 초과(Time Run out): 실행 상태 -> 준비 상태

지정된 CPU의 할당시간을 모두 사용한 프로세스는 다른 프로세스가 CPU를 선점하고, 그 프로세스는 준비 상태로 전환된다.

 

3) 대기(Block): 실행 상태 -> 대기 상태

실행중인 프로세스가 입출력 명령을 만나면 인터럽트가 발생하여 입출력 전용 프로세서(DMA)에게 CPU를 양도하고, 자신은 스스로 대기 상태로 전환한다. 나머지는 모두 프로세스 자의가 아닌 외적 조건에 의해 발생한다.

 

4) 깨움(Wake Up): 대기 상태 -> 준비 상태

입출력 완료를 기다리다가 입출력 완료 신호가 들어오면, 대기 중인 프로세스는 준비 상태로 전환한다.

 

프로세스 제어 블록(PCB)

PCB(Process Control Block)는 운영체제에게 프로세스에 대한 모든 정보를 제공해주는 자료구조

운영체제가 CPU를 다른 프로세ㅅ에 넘겨주고자 할 떄, 프로세스에 관한 모든 정보를 PCB에 저장시키고 나서 다시 실행하고자 할 때에는 PCB에 보관된 정보를 재사용

(프로세스 상태, 프로세스 식별자, 프로세스의 부모 프로세스에 대한 포인터, 프로세스의 우선순이, 프로그램 카운터, 중아처리장치 레지스터 보관 장소)

 

스레드

프로세스의 구성을 크게 제어흐름 부분(실행 부분)과 실행 환경 부분으로 나눌 때, 스레드는 프로세스의 실행 부분을 담당함으로써 실행의 기본단위

 

- 각각의 스레드는 독립적인 제어흐름을 가지고 자신만의 스택과 레지스터를 가진다. 하지만 한 프로세스 안에 있는 다른 스레드들과 코드, 데이터, 운영체제 자원 등을 공유한다.

 

공유영역: 코드, 정적전역 데이터, 힙, 커널 데이터

사유영역: 스택, 프로그램 카운터, 레지스터 집합, 지역 데이터

 

다중스레드 장점

응답성/ 자원공유/ 경제성/ 구조의 활용

 

스레드의 구현 방법

1) 커널 수준(시스템 호출) 스레드

커널이 스레드를 관리하기 떄문에 스레드가 봉쇄형 시스템 콜을 수행하면, 커널은 응용프로그램 내의 다른  스레드 수행x

인터럽트를 통한 이전이므로 수행시간이 많이 걸린다

 

2) 사용자 수준(라이브러리 호출) 스레드

커널 위에서 지원되며 사용자 수준의 스레드 라이브러리에 의해 구현되므로, 커널의 지원 없이 스레드의 생성과 스케줄링 관리 지원

모든 스레드 생성과 스케줄링은 커널의 개입 없이 사용자 공강에서 이루어지므로 수행속도가 매우 빠르다.

운영체제는 스레드를 인식하지 못하므로 -> 프로세스에서 운영체제의 호출 시에 프로세스 전체가 기다리게 되므로 스케줄링이 불공평

 

프로그램 실행 시 메모리 영역

 

 

다중 쓰레드(multi thread) 프로그래밍을 할 때 다음 C언어의 변수들 중에서 임계구역(critical section) -> 전역 변수

 

프로세스 스케줄링

 

CPU 자원을 언제, 어느 프로세스에게 배당할 것인지를 결정하는 작업을 프로세서(CPU) 스케줄링(Scheduling)

 

중앙처리장치 이용률(Utilization): CPU 수행 시간 또는 시스템  구동 시간

처리량(Throughput): 단위 시간당 완료되는 프로세스 수

대기시간(Waiting Time): 준비 큐에서 대기하는 시간

응답시간(Response Time): 작업을 제출한 후 첫 응답이 올 떄까지의 시간

반환시간(Turnaround Time): 프로세스가 시스테ㅁ에 진입하여 완료되는 시간

 

선점 스케줄링(Preemptive Scheduling)

한 프로세스가 CPU를 차지하고 있을 때 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 차지할 수 있다.

 

장점: 높은 우선순위를 가진 프로세스들이 빠른 처리를 요구하는 시스템에서 유용하다

단점: 응답시간의 예측이 어렵다, 빠른 응답시간을 요구하는 시분할 시스템에 유요하지만, 문맥교환으로 많은 오버헤드를 초래할 수 있다.

 

기법: RR(Round-Robin), SRT(Shortest-Remain-Time), MLQ(MultiLevel Queue), MFQ(Multilevel Feedback Queue), 우선순위 스케줄링

 

RR 스케줄링

FCFS에 의해서 프로세스들이 내보내지며 각 프로세스는 같은 크기의 CPU 시간(Time Quantum)할당

- 다중 프로그래밍 시스템이나 시분할 시스템에 효과적 / 할당 시간이 너무 길며 FCFS방식과 동일하게 된다, 할당시간이 너무 짧으면 문맥교환이 자주발생하여 부하가 증가

 

SRT(Shortest Remaining Time) 스케줄링

가장 짧은 시간이 소요된다고 판단되는 프로세를 먼저 수행

- 현재 실행 중인 프로세스라도, 남은 처리 시간이 더 짧다고 판단되는 프로세스가 생기면 언제라도 실행중인 프로세스가 선점 당하기 때문에 기아상태가 발생할 수있다.

- 적은 대기시간을 제공하지만, 선점 오버헤드로 인하여 SJF가 더 좋은 성능을 가질 수 있다.

MLQ 다단계 큐 스케줄링

작업들을 여러 그룹으로 나누어 여러 개의 큐를 이용하는 기법, 그룹화 된 직업들은 각각의 준비 큐에 넣고 각 큐의 독자적인 스케줄링 알고리즘에 따라서 CPU를 할당받는 방법

- 대화형 프로세스들은 상위 단계의 큐에 머무렉 되고, 배치(Batch) 프로세스들은 하위단계의 큐에 머물게 된다.

 

MFQ 다단계 피드백 큐

 

프로세스가 큐들 사이를 이동하는 기법, 새로운 프로그램이 들어오면 높은 우선순위를 할당해주어 단계1에서 즉시 수행 -> ㄱ작업이 완료될 떄까지 라운드 로빈으로 순환한다.

 

 

 

 

 

비선점 스케줄링(Non-preemptive Scheduling)

한 프로세스가 CPU를 할당 받으면 CPU는 그 프로세스로부터 빠져 나올 수 없다.

모든 프로세스들에 대한 대우는 짧은 직업이든 긴 작업이든 간에 공정히 처리한다.

 

장점: 응답시간이 예측 가능함.

단점: 짧은 작업이 긴 작업을 기다리는 경우가 종종 발생한다.

기법: FIFO(First-In-First-Out), SJF(Shortest-Job-First), HRN(Hightest Response Time), 우선순위 스케줄링

 

FCFS/FIFO

SJF -> 기아상태 발생

HRN(Highest Response ratio Next) SJF 스케줄링의 긴 작업과 짧은 작업 간의 지나친 불평등을 보완한 에이징 기법

우선순위 = 대기시간 + 서비스받을 시간 /서비스를 받을 시간

 

 

프로세스 간 동기화

임계 영역: 하나의 프로세스가 수정 가능한 공유 자원을 액세스 하고 있을 때, 그 프로세스에 의해 참조되는 프로개름 부분 의미

하나의 프로세스가 공유 데이터 접근 -> 다른 프로세스는 그 공유 데이터를 접근하면 안된다. 무결성을 보장해야 한다.

임계 영역을 수행 중에 있는 프로세스는 인터럽트, 교착상태(Deadlock), 무한 교착상태가 해제될 때까지 임계 영역을 벗어날 수 없다.

 

코드지역(영역)

프로세스가 임계 영역에 진입하려면 진입하기를 청 이런 요청을 현하는 코드 부분을 진입 영역

 

요구조건

 

상호 배제 조건

한 프로세스가 공유 자원을 사용하고 있을 때, 다른 프로세스들이 사용하지 못하도록 배제시키는 제어 기법

임계 영역의 개념을 이용하여 두 프로세스가 하나의 공유 자원을 상호 배타적으로 사용할 수 있게 하면서 동시에는 수행할 수 없도록 하는 것

 

제한된 대기 조건

어떤 프로세스도 제한된 대기를 한 뒤에는 임계 영역으로 진입할 수 있어야 한다는 뜻,  즉 프로세스가 세마포어 내에서 무한히 기다리는 바쁜 대기(BusyWaiting)을 방지한다.

어떤 프로세스가 임계 영역 진입을 요청하면 다른 프로세스들의 임계 영역 진입 허용 횟수에 제한을 두어야 한다.

 

진행 조건

임계 구역(영역)을 실행하는 프로세스가 없고, 임계 영역으로 진입하려는 프로세스들이 있다며느 이들 중 어느 하나만 선택되어 자신의 임계 영역으로 진입할 수 있ㅇ어햐 하며, 이 선택이 무한정 연기될 수 없도록 하는 것

 

동기화 기법

 

1. 상호 배제 : 여러 개의 병렬 프로세스가 공통의 자원에 접근할 떄 그 조작을 정당하게 실행하기 위하여 접근 중인 임의의 시점에서 하나의 프로세스만이 그 접근을 허용하도록 하는 것

 

2. 세마포어: 상호배제의 좀 더 복잡한 문제를 해결하기 위해 사용한다. 

wait(s) : if (s > 0) s= s -1

                  else 현재의 프로세스를 블록하고 대기 큐에 추가

 

signal(s) : if (1개 이상의 프로세스가 s에서 대기 중이면) 그 중 한 개 프로세스만 진행

                 else s = s + 1;

 

프로세스 사이의 동기를 유지하고 상호 배제의 원리르 보장할 수 있다.

세마포어에 대한 연산은 처리 도중에 인터럽트 되어서는 안 된다. 즉 여러 프로세스가 동시에 세마포어의 값을 수정할 수 있다.

프로세스 사이의 동기를 유지하고 상호 배제의 원리를 보장할 수 있다.

동일한 공유자원이 여러 개 있는 경우 signal(s) 연산을 먼저 수행했을 때 교착상태가 발생할 수 있다.

 

3. 모니터

순차적으로만 사용할 수 있는 공유자원을 할당하는 데 사용되는 데이터와 데이터를 처리하는 연산의 집합으로 이루어진 병행성 고급 구조체, 자원관리 기능을 수행하려는 프로세스는 반드시 해당 모니터 진입부를 호출, 모니터 자체는 상호 배제가 엄격하게 되어있다.

 

교착상태

 

다중 프로그래밍 시스템에서 아무리 기다려도 결코 일어나지 않을 사건을 기다리고 있는 하나 또는 그 이상의 프로세스드이 있는 상태

둘 이상의 서로 다른 프로세스가 자신이 요구한 자원을 할당받아 점유하고 있으면서 상호간에 상대방 프로세스에 할당되어 있는 자원을 요구하는 경우에 발생

 

교착상태의 4가지 필요조건

 

 

상호배제

프로세스들이 자원을 배타적으로 점유하고 있어, 다른 프로세스들이 자원을 사용할 수 없도록 만든다.

한 번에 한 프로세스만이 자원을 사용할 수 있으며, 다른 프로세스가 그 자원을 요구하면, 자원을 요구한 다른 프로세스는 자원이 해제될 때까지 임계영역바깥에서 대기한다.

 

점유와 대기

프로세스들은 동일한 자원이나 다른 종류의 자원을 부가적으로 요구하면서, 이미 어떤 자원을 점유하고 있다.

 

비선점

자원은 그 자원을 점유하고 있는 프로세스로부터 도중에 벗어나지 못한다. 단지 프로세스 자신만이 점유한 자원을 해제할 수 없다.

 

환형 대기

프로세스 간에 닫힌 체인(closed chain)이 존재하여, 체인 내의 각 프로세스는 체인 내의 다른 프로세스가 소유하고 있는 자원을 요청 대기

대기하고 있는 프로세스 집합

 

 

 

교착상태 해결방법

 

예방

사전에 교착상태의 가능성을 없애는 것

교착상태 4가지 조건을 모두 만족했을 떄 교착상태가 발생 -> 교착상태 발생 필요조건들 중 적어도 하나를 부정함으로써 교착상태의 발생 가능성을 제거

 

회피

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

은행가 알고리즘(프로세스가 현재 가용한 자원들을 요청할 때마다, 시스템은 자원이 즉시 할당될 수 있는지 또는 대기해야 되는지를 결정해야 한다. 자원을 할당한 다음에도 시스템이 항상 안정 상태에 있을 때만 요청

 

발견

여러 시스템에서 사용되는 방법으로서, 원하는 것이든지 아니든지 일단 교착상태가 발생하도록 허용한다.

교착상태가 발생하면 그 교착상태에 관련된 프로세스와 자원을 조사하여 결정해 내는 방법

 

회복

시스템으로부터 교착상태를 제거하여, 이후로는 시스템이 교착상태에 빠지지 않고 잘 진행되게 한다.

교착상태에 빠진 프로세스가 완료되고 그 프로세스에 할당된 자원을 회수 할 수 있도록 한다.

 

기억장치 할당기법 관리정책

주기억장치

 

주기억장치: 

고정 분할:

 

내부 단편화:

하나의 분할 영역에 작업을 할당하고 남은 빈 공간 의미

 

외부 단편화:

기억장치가 너무 많은 수의 매우 작은 공간들로 단편화되어 있어 공간 중 일부를 사용할 수 없는 빈 공간, 어떤 요구를 만족시킬 수 있는 충분한 전체 기억 공간은 남아있지만 공간이 연속되어 있지 않았을 때 발생

 

가변(동적)분할 기억장치

 

주기억장치 사용자 영역을 각 작업에서 가장 합리적인 분할의 크기를 결정하여 주기억장치를 할당

 

단편화 해결

기억장치 통합: 이웃되는 가용공간을 하나의 커다란 가용공간으로 만드는 것

기억장치 집약: 기억장치 모든 내용들 한 군데로 몰고 모든 자유 공간들을 다른 한 군데로 몰아서 큰 블록

쓰레기 수집(Garbage Collection): 여러 개의 작은 단편화 공간, 즉 가용 공간을 모아서 하나의 큰 가용 공간을 만드는 것

 

기억장치 관리

반입 정책

배치 정책

교체 정책

 

 

가상기억장치:

하나의 프로그램을 여러 개 블록 또는 조각으로 나누어 주기억장치 내 분산시켜 배치되는 방식으로, 그 조각들이 반드시 인접하지 않아도 된다

 

페이징:
블록 사이즈가 고정한 방식으로 사용자가 작성한 프로그램은 하드웨어에 의해 페이지 단위로 분해

물리적 주소 공간은 가상기억장치의 페이지 크기와 같은 페이지 프레임으로 나누어 사용

 

장점:

1. 세그먼트 테이블과 달리 페이지 테이블은 블록의 크기를 나타낼 필요가 없다

2. 보조기억장치의 페이지 크기와 주기억장치의 페이지 프레임의 크기가 동일하므로, 외부 단편화가 발생하지 않는다.

 

단점:

1. 내부 단편화는 발생할 수 잇다.

2. 세그먼트 기법에 비해 주소변환테이블을 기억하기 위한 많은 기억장소가 필요

3. 페이지는 프로그램에 상응하는 논리적 의미X, 세그먼트에 비해 공유, 보호를 지원하기 어렵다

 

세그멘테이션:

블록 사이즈가 가변적인 방식으로서, 가변 사이즈 블록을 세그먼트(Segment)라 한다.

세그먼트는 프로그램에서 서브루틴과 같은 의미 -> 최초, 최적, 최악 적합등 배치 필요

세그먼트 테이블의 각 항목은 세그먼트 기준과 한계를 가지고 있는데 세그먼트 기준은 세그먼트가 메모리 내에 존재하는 시작 물리 주소를 가지고 있ㅁ으며 세그먼트 한계는 세그먼트 길이를 명시

 

장점:

내부 단편화는 발생X

페이징시스템에 비해 세심한 액세스 제어가 가능

 

단점:

외부 단편화가 발생 -> 세그먼트 크기가 고정되지 않고 가변적

세그먼트 크기가 가변적이기 떄문에 세그먼트 영역이 다른 세그먼트 영역을 침범하지 않기 위한 특별한 하드웨어 관리가 필요

 

페이징/세그먼테이션 혼용 기법

프로그램을 논리적인 세그먼트 단위로 분할하고, 분할된 각 세그먼트들은 다시 각각 페이지 단위로 분할

 

TLB:

변환 색인 버퍼는 프로세스 내부에 있는 장치로 가상 메모리 주소를 물리적인 주소로 변환하는 속도를 높이기 위해 사용되는 캐시의 일종