가. 선점 스케쥴링
특정 프로세스가 중앙처리장치를 효율적으로 사용할 수 없는 시점에 이를 때마다 중 앙처리장치의 사용권이 다른 프로세스로 옮겨지는 방식으로 높은 우선순위의 프로세 스들이 급하게 실행해야 할 경우에 유용하다.
① 대화식 시분할 시스템에서 빠른 응답시간을 유지하는 데에 필요하다.
② 경비가 많이 들고 오버헤드까지 초래한다.
③ 효과적인 선점을 하려면 준비 상태의 프로세스가 많아야한다.
④ 우선순위를 고려해야 한다.
⑤ 문맥교환의 횟수가 비선점 방식에 비해서 많다.
나. 비선점 스케쥴링
어떤 자원이 어떤 프로세스에 할당이 되면 실행을 종료할 때까지 그 프로세스가 중앙처 리장치의 사용권을 독점하여 사용하는 것으로 짧은 작업들을 기다리게 되는 경우가 있 지만 모든 프로세스 관리에 공정하다.
① 응답시간의 예측이 쉽다.
② 문맥교환의 횟수가 적다.
③ 일괄처리 방식에 적합한 방식이다.
참조) 우선순위(Priority)
① 정적 우선순위(static priority): 프로세스 실행중 우선순위가 변하지 않는 것으로 구현이 용이하고 동적 우선순위에 비해 오버헤드가 적다.
② 동적 우선순위(dynamic priority): 처음에 정해진 우선순위를 상황에 맞게 계속조정하여 사용하므로 구현이 복잡하고 정적 우선순위에 비해 오버헤드가 크다.
10. 프로세서 스케쥴링의 종류
선점
Preemption | RR
Round
Robin | ① FIFO스케쥴링과 같이도착 순으로 디스패치되는 방식
② 타임 슬라이스(time slice) 혹은 시간 할당량(time quantum)에 의해 시간 제한을 받음
시간할당량이 클 경우 : FIFO스케쥴링 방법과 차이가 없게 됨
시간할당량이 적은 경우 : 문맥교환 오버헤드가 상대적으로 커지게 되어 시스템은 대부분의 시간을 문맥교환(context switching)에 소비하게 됨
③ 대화식으로 사용하는 시분할 시스템에 적합
④ FIFO를 선점 스케쥴링으로 변형시킨 방법 |
SRT
Shortest
Remaing
Time | ① SJF스케쥴링기법을 선점 기법으로 변형시킨 방법
② 시분할 시스템에 유용하다.
③ 작업이 끝나기까지 남아 있는 실행시간의 추정치가 가장 작은 프로세스를 먼저 실행함
④ SJF스케쥴링기법보다 오버헤드가 큼 |
Multilevel
Feedback
Queue | ① 짧은 작업에 우선권
② 입출력 위주의 작업들에게 우선권
③ 큐에서 FIFO 형태로 이동
(마지막 단계의 큐에서는 프로세스가 종료될 때까지 RR방식으로 순환)
④ 낮은 단계로 내려갈수록 프로세스의 시간 할당량이 커짐 |
비선점
Non -
preemption | FIFO
First In
First Out | ① 준비 큐(ready queue)에서 도착한 순서에 따라 디스패치 됨
② 응답시간 차가 적기 때문에 예측이 쉬움
③ 대화식 시스템에는 적합하지 않음 |
SJF
Shortest
Job First | ① 작업이 끝나기까지의 실행시간의 추정치가 가장 적은 작업을 먼저 실행 함 (짧은 작업들에 우선적으로 서비스)
② 평균 대기시간을 최소화 시킬수 있음 |
우선순위
Priority | ① 각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리함
② 우선순위가 같을 때는 FIFO또는 SJF을 도입하여 실행 함 |
기한부
Deadline
Scheduling | 작업들을 마감시간까지 완성하도록 계획한 스케쥴링 |
HRN
Highest
Response
Ratio
Next | ① SJF스케쥴링기법의 약점인 긴 작업과 짧은 작업간의 지나친 불평등들을 어느 정도 보완한 방법
② 각 작업의 우선순위는 그 작업이 서비스를 받을 시간뿐 아니라 그 작업이 서비스를 기다린 시간 두 가지의 함수로 결정됨
응답률 = (대기한 시간 서비스 받을 시간)/ 서비스 받을 시간 |
프로세스
1. 병행(concurrent)프로세스
시스템 내에 다수의 프로세스들이 동시에 실행되는 것으로 프로세스들이 시스템 내에 동시에 존재하나 어느 한 순간에 단지 한 프로세스만 CPU에서 실행된다.
가. 병행성의 종류
① 단일 프로세스내에서의 병행성 : 우선순위 그래프나 Fork Join구조, 병행문
② 프로세스들간의 병행성(비동기적) : 완전히 독립하여 수행되거나 다른 프로세스들과 가끔 협력 하는 기능
나. 병행 프로세스의 종류
① 독립적 프로세스(independent process)
어떤 프로세스가 시스템에서 실행중인 다른 프로세스에게 영향의 주거나 다른 프로세스로부터 영향을 받지 않을 때의 프로세스
특징)
- 프로세스의 상태는 다른 프로세스에 의해서 공유되지 않는다.
- 프로세스의 실행은 결정적이다. 즉, 실행결과는 입력에 의해서만 결정
- 실행은 재생가능한 것으로 실행결과는 같은 입력에 대해서는 항상 동일하다.
- 실행은 나쁜 영향을 발생하지 않고 중단되고 재시작될 수 있다.
② 협력 프로세스(cooperating process)
어떤 프로세스가 시스템에서 실행중인 다른 프로세스에 영향을 받거나 줄 때의 프로세스
특징)
- 프로세스의 상태는 다른 프로세스들과 공유된다.
- 프로세스의 실행은 비결정적이다. 즉, 실행결과는 상대적 실행 순서에 의존하고 미리 예측될 수 없다.
- 실행은 재생 불가능하다. 즉, 실행결과는 같은 입력에 대해 항상 같지 않다.
다. 병행문(concurrent statement)
Dijkstra[1965]의 parbegin/parend문에서 볼 수 있으며
parbegin
S₁;
S₂;
Sn ;
parend;
와 같이 표시한다.
S₁, S₂, ... Sn은 각각 단일문이고 병행으로 수행된다.
병행 문의 예제) x := (-b (b**2-4*a*c)**.5)/(2*a)
Parbegin
temp1 := -b;
temp2 := b**2;
temp3 := 4*a;
temp4 := 2*a;
Parend
라. 임계영역(critical section) 문제
① 임계영역이란 프로세스가 사용하면서 수정 가능한 자원을 나타내며 하나의 프로세스가 임계구역에서 수행중일 때 다른 어떠한 프로세스도 이 임계영역에서 수행 할 수 없다. 실생활에서 예를 들자면 화장실이나 공중 전화를 예로 들 수 있다.
② 이러한 임계영역 보호를 위하여 각 프로세스는 그 임계영역에 들어갈 수 있는지 미리 요청하여야 하는 모니터 구조를 사용한다.
진입영역(Entry Section) | 임계영역 사용을 요구하는 부분 |
임계영역(Critical Section) | 수정 가능 자원을 이용하는 코드 부분 |
출구영역(Exit Section) | 임계영역 사용을 끝낸 후 처리 부분 |
잔류영역(Remainder Section) | 나머지 코드부분 |
③ 임계영역은 3가지의 조건
- 상호배제 : 하나의 프로세스가 임계구역에서 수행중일 때 다른 어떤 프로세스도 임계영역에서 수행될 수 없다.
- 진행(Progress) : 하나의 프로세스가 임계영역 사용을 끝내면 다른 프로세스가 선택되어 임계영역을 사용한다.
- 제한된 대기 : 한 프로세스가 임계구역에 대한 요청 후 일정한 기간 내에 요청이 받아들여져야 한다. 이를 위해 하나의 프로세스가 임계구역을 수행할 수 있는 횟수에 제한을 둘 수 있다.
마. 상호배제의 해결
① 소프트웨어적인 방법
- 2개의 프로세스를 상호배제 하기 위한 방법 : Peterson
- N개의 프로세스를 상호배제 하기 위한 방법
- Dijkstra
- Kunth
- Eisenberg & Macguire
- Lamport - 제과점 알고리즘 : 분산환경을 위해 개발되었음
② 하드웨어적인 방법
- Test And Set : 원자적(atomic) 명령
- Burns
바. 세마포어
① 공유변수 : S
② P(s) 연산 : 조건을 검사하여 프로세스의 임계영역으로의 진입을 검토하여 불가능한 경우의 프로세스를 대기 행렬(Queue)에 넣는다.
③ V(s) 연산 : 임계영역에 실행중이던 프로세스가 종료시 대기 행렬(Queue)에 대기 중인 프로세스가 있으면 임계영역에서 실행할 수 있도록 한다.
④ 대기 행렬 Queue : 임계영역의 사용을 위하여 대기하는 작
repeat
wait(mutex); P(s)
critical section(임계구역)
signal(mutex); V(s)
remainder section(잔류구역)
until false; |
P(s)
s = s-1;
if s < 0
then begin
wait(s)
end;
else
임계영역 | V(s)
s = s 1;
if s <= 0
then begin
signal(s)
end; |
사. 프로세스간의 통신
① 공유기억장치기법
- 통신을 하는 프로세스들간에 변수를 공유하여 사용하도록 하는 방식이다.
- 운영체제는 기억장소만 제공하며, 응용프로그래머가 동기화 등의 책임을 진다.
- 공유기억장치 기법의 사용예는 세마포어의 S변수에서 볼 수 있다.
② 메시지 시스템기법
- 프로세스들 간에 send, receive등을 이용하여 메시지를 교환할 수 있도록 하는 방식이다.
- 운영체제 자체가 전달의 책임까지 진다.
- 분산시스템에서 이용하기 좋은 방식이다.
- 직접 프로세스간에 전송하는 기법과 우편함을 통한 간접 기법이 있다.
3. 교착상태(Deadlock) ( = 무한대기)
다중 프로그래밍 환경에서 두 개의 프로세스가 서로 다른 프로세스가 가지고 있는 자원을 기다리고 있으며 자신이 차지하고 있는 자원을 내놓지 않는 현상으로 이 두 프로세스에게는 영원히 처리기를 줄 수 없게 된다.
가. 교착상태 필수조건
① 상호배제(mutual exclusion) : 어느 자원에 대해 한 프로세스가 이미 사용중이면 다른 프로세스는 기다려야 하는 것
② 점유와 대기(wait for) : 하나 이상의 자원을 할당받은 채로 나머지 자원을 할당 받기 위해 다른 프로세스의 자원이 해제되기를 기다리는 프로세스가 존재하는 경우
③ 비중단(no Preemption) : 자원을 할당받은 프로세스로부터 자원을 강제로 빼앗지 못하는 것
④ 환형대기(circular wait) : 자원 할당 그래프 상에서 프로세스의 환형 사슬이 존재하는 것
나. 자원할당 그래프
G = {E, V} E는 간선의 집합을 V는 프로세스의 집합을 말한다.
P={P1, P2, P3,...,Pn} : 프로세스의 집합
R={R1, R2, R3,...,Rm} : 자원의 집합
기호 | 뜻 |
원 | 프로세스 |
네모 | 자원 |
자원→프로세스 | 할당 |
프로세스→자원 | 요청 |
다. 교착상태 발견기법
① 자원할당 그래프에서 환형 대기를 나타내는 사이클(cycle)이 있으면 교착상태가 존재할 수 있다. (자원할당 그래프가 사이클을 포함하지 않으면 교착상태는 발생하지 않는다.)
② 사이클이 존재할 경우 그 사이클이 제거 될 수 있는지 검사한다.
(각 프로세스가 요구하는 자원을 모두 할당받았을 경우 제거 가능)
③ 사이클이 제거 될 수 있을 경우는 교착상태가 아니며, 제거 될 수 없을 경우는 교착상태이다.
라. 교착상태 예방 및 해결 방법
① 교착상태 예방(deadlock prevention) = 교착상태 필요조건의 부정
- 상호배제조건의 부정
자원을 공유할 수 있도록 한다. 자원을 공유할 수 없는 자원인 프린터등은 상호배제조건 부정을 할 수 없다. - 점유 및 대기조건의 부정
프로세스가 수행을 하기에 필요한 모든 자원을 한꺼번에 요청하고 할당받는다. - 비중단조건의 부정
원래 갖고 있던 자원을 일단 반납하고 필요하다면 다시 그 자원이나 다른 자원을 요구한다. - 환형대기조건의 부정
각 자원 유형별로 고유번호를 부여하여 번호가 큰순으로 자원을 요구하도록 한다.
② 교착상태 회피(deadlock avoidance)
교착 상태가 발생할지 하지 않을지의 상태를 사전정보를 가지고 예측하여 안전하다고 판단될 경우 처리하는 방법이다. 이 경우 불안정하다고 판단이 되더라도 교착상태가 발생되지 않을 수도 있다.
- 안정상태(safe state): 전체자원의 상황이 작업을 완료할 수 있는 상태
- 불안전 상태 : 교착상태가 일어날 수 있는 상태.
③ 교착상태 발견(deadlock detection)
교착상태가 일어났는지를 자원할당 그래프를 이용하여 알아내는 과정이다.
④ 교착상태 복구(recovery from deadlock)
교착상태를 발견하고 교착상태에 있는 하나 이상의 프로세스들로부터 몇 개의 자원 선점(resource preemption) 시키는 것에 의해 복구 하는 방법으로 조작자에게 교착상태가 발생했음을 알려주어서 직접 수작업으로 처리 하도록 하거나 시스템으로 하여금 교착상태를 자동적으로 복구하도록 하는 방법이 있다.
- 선점 방법
- 모든 교착상태 프로세스들을 종료하는 것 : 이것은 교착 상태 사이클을 분해시키지만 회복하는데 많은 비용이 소요된다.
- 프로세스를 하나씩 종료하는 것 : 교착상태 사이클이 제거될 때까지 하나씩 종료하는 방식으로 상당한 오버헤드를 요구한다. - 선점 프로세스(=희생자) 선택 기준
회복시 필요한 비용이 가장 적은 것을 선점의 대상(=희상자)으로 선택한다. - 복귀(rollback)
프로세스로부터 자원을 선점한다면, 그 프로세스를 어떤 상태로 놓을 것인지를 결정해야한다. 그러나 정상적인 수행을 계속할 수 없을 때에는 그 프로세스를 안전한 상태로 되돌려 놓고, 그 상태로부터 재시작해야 한다.(예: 완전복귀) - 기아상태(starvation)
비용 요소에 기초를 두는 시스템에서 희생자 선택은 주로 동일한 프로세스가 매번 선택 될 수 있는데 이 경우 특정 프로세스가 반복해서 희생자로 선택될 경우 그 프로세스는 지정된 작업을 오랫동안 완료하지 못하는 상황이 되며, 이러한 상황을 기아상태라 한다.
4. 대기의 종류
① 제한된 대기
- 일정한 시간 내에 프로세스가 작업을 실행할 수 있는 상태(dispatch)가 되어야 한다는 조건이다.
② 바쁜 대기
- 임계영역에 진입할 수 있는지에 대한 조건을 계속 검사하면서 대기하는 상태를 말한다.
③ 무한 대기
- 상대방 프로세스의 상태를 모르고 실행을 멈추고 계속하여 기다리고 있는 상태를 말한다.
④ 점유 및 대기
- 실행하는데 필요한 자원을 일부만을 할당 받고 일부는 요청하고 있는 상태를 말한다.
⑤ 환형 대기
- 자원할당그래프를 그려서 할당과 요청의 상태를 보았을 때 환형(cycle)의 그림이 보이는 상태를 말한다.
3장 주기억장치 관리
1. 기억장치의 계층구조
2. 연속할당과 불연속 할당기법
가. 연속할당(contiguous storage allocation)
① 프로그램을 연속된 메모리 공간에 할당하는 방법으로 초기의 주기억장치 할당 방법으로 사용되었다.
② 기억장치의 공간보다 더 큰 프로그램은 적재하지 못 한다.
→ 이런 문제 해결을 위해서 Overlay기법 등을 사용하였다.
나. 불연속 할당(non-contiguous storage allocation, = 산재할당)
① 프로그램을 한 개 이상의 조각(Page, Segment)으로 나누어 필요한 조각만 주기억장치에 할당하는 방법으로 최근 사용하는 방법이다.
② 가상기억장치 기법으로 사용한다.
③ 프로그램의 크기에 상관없이 적재하여 실행할 수 있다.
3. 주기억장치 관리 : 연속 할당의 경우
단일 사용자 연속 기억장치 할당 |
다중 프로그래밍 | 고정분할 방식
① 절대 번역 및 적재 방식
② 재배치 가능 번역 및 적재 방식 |
가변분할 방식 |
가. 단일 사용자 연속 기억장치 할당(single user contigious storage allocation system)
① 한번에 한 사용자만 메모리를 사용하는 방법으로 컴퓨터 시스템의 모든 자원은 한 사용자가 마음대로 사용할 수 있다.
② 프로그램의 크기는 주기억장치 용량보다 클 수 없다.
단, Overlay 기법을 이용하여 주기억장치 용량보다 큰 프로그램을 실행 할 수 있다.
③ 경계레지스터(limit register, bound register, fence register)를 사용하여 시스템 영역보호를 한다.
나. 다중 프로그래밍(multiprogramming)
① 고정분할 다중 프로그래밍(fixed partition multiprogramming)
- 주기억장치를 여러 사용자가 동시에 사용할 수 있도록 하여 CPU의 이용률을 높이고 처리량(Throughtput)을 늘릴 수 있는 방법이다.
- ·사용전에 미리 영역을 나누어 놓고 적당한 곳에 프로세스를 할당한다.
(가) 절대번역(absolute translation)과 적재(loading)
절대번역이 되어 정해진 영역에서만 실행되는 것으로 기억장치를 낭비가 있을 수 있지만 구현하기가 쉽다.
(나) 재배치 가능번역(relocatable translation)과 적재(loading)
어떤 영역에서도 그 영역에 수용될 프로그램이 있으면 실행 가능한 경우를 말한다. 절대번역과 적재 상에서 발생하는 기억장치의 낭비를 막을 수 있으나 운영체제를 구현하는 측면에서 더 복잡하다.
② 가변분할 다중 프로그래밍(variable partition multiprogramming)
- 실행 중에 프로세스가 필요로 하는 크기만큼의 메모리를 할당하여 적재하는 방식이다.
- 가변분할 방식은 단편화 문제를 줄이기 위해서 고안이 되었지만 단편화 문제를 해결하지 못했다. (초기에는 단편화 현상이 나타나지 않지만 기억장소의 사용과 반납이 반복되면서 단편화 공간이 생긴다.)
4. 기억장치 관리기법
가. 반입기법(fetch strategy) : When
보조기억장치에서 주기억장치로 언제 프로그램과 데이타를 이동할 것인가에 관한 문제
① 요구호출(demand fetch)
현재 실행되는 프로그램에 의해 참조될 때 프로그램과 데이타를 주기억장치로 옮기는 기법
② 예상호출(anticipatory fetch)
실행되는 프로그램에 의해 참조될 가능성이 있는 프로그램과 데이터를 예측하여 미리 옮겨놓아 효율성을 향상시키기 위한 기법, 예상이 맞지 않을 경우 오버헤드가 발생 하게 된다.
나. 배치기법(placement strategy) : Where
새로 반입된 프로그램을 주기억장치 내의 어느 곳에 둘 것인가에 관한 문제
① 최초적합(first-fit) : 주기억장치 내에 분할된 공간 중 반입된 프로그램을 수용할 수 있는 첫번째 빈 공간에 배치하는 기법
② 최적적합(best-fit) : 주기억장치 내의 분할된 공간 중 적재시 단편화 공간이 가장 적게 발생하는 공간에 배치하는 기법
③ 최악적합(worst-fit) : 주기억장치 내의 분할된 공간 중 적재시 단편화 공간이 가장 크게 발생하는 공간에 배치하는 기법
다. 교체기법(replacement strategy, swapping) : What
새로 반입된 프로그램이 들어갈 장소가 없을 경우 주기억장치상의 어떤 프로그램이나 데이타를 교체대상으로 할 것인가를 결정하는가에 관한 문제
5. 단편화(fragmentation) 문제
연속으로 기억장치를 할당하여 사용할 경우 크기가 맞지 않아서 사용되지 못하는 공간이 생길 수 있는데, 이러한 공간을 단편화 공간이라고 한다.
가. 단편화의 종류
① 내부 단편화(internal fragmentation)
분할의 사용하고 남은 일부분을 말한다. 예를 들어 '100'크기를 갖는 분할에 '80'크기를 갖는 프로그램을 배치하였을 경우 '20'의 공간이 내부 단편화 공간이 된다.
② 외부 단편화(external fragmentation)
분할의 크기가 프로그램의 크기보다 작아서 사용되지 못한 것을 말한다. 예를 들어 '100' 크기를 갖는 분할이 있을 때 '120' 크기를 갖는 프로그램은 배치 되지 못하며 '100'의 공간이 외부 단편화 공간이 된다.
나. 단편화의 해결 : 재배치(relocation)를 이용한 해결
기억장치의 단편화 공간을 주소 재배치를 통하여 묶는 방법인 통합(coalescing)과 압축(compaction)을 사용하여 해결 할 수 있다.
① 기억장치의 통합(coalescing)
- 인접된 공백들을 하나의 공백으로 만드는 것
- 통합을 하여도 공백이 분산되어 있는 경우(사용공간이 사이에 있는 경우)는 큰공간이 생기지 않으므로 단편화 문제를 해결하지 못할 수도 있음
② 기억장소의 압축(compaction)
- 주기억장치내의 모든 공백들을 하나의 공백으로 모으는 작업
- 기억장소의 트림(burping the storage) 또는 쓰레기 수집(garbage collection)이라고도 함
- 압축하는 동안 시스템은 모든 일을 중단해야 함
- 압축은 기억장치상의 모든 작업들을 재배치시키게 되며, 프로그램이 로드 될 때 잃기 쉬운 재배치 관련 정보를 즉각 사용할 수 있는 형태로 유지하여야 함
- 압축을 하므로 소모되는 시스템 자원이 압축을 통해 얻는 이익보다 더 커질 수 있음
4장. 가상 기억장치
1. 가상기억 장치 기법
- 가상기억장치의 개념은 Atlas 컴퓨터시스템에서 처음 나타났다.
- 가상기억장치를 구현하는 가장 일반적인 두 가지 방법은 페이지 기법과 세그먼트기법이다.
페이징 기법(Paging) 세그먼트 기법(Segmentation) |
- 실행 프로세스가 참조하는 주소를 가상주소(virtual address)라 한다.
- 주기억장소에서 사용할 수 있는 주소를 실주소(real address)라 한다.
- 프로세스는 오직 가상주소만을 참조하지만, 그들은 실제로 실기억장치에서 실행되어야 하므로, 프로세스가 실행되면 가상주소는 실 주소에 사상되어야 한다.
- 프로세스가 실행되는 동안 가상주소를 실주소로 바꾸는 절차를 동적주소 변환(DAT:Dynamic Address Translation)이라고 한다.
- 프로세스의 가상주소공간에서 연속인 주소가 실주소에서 연속일 필요가 없다는 인위적 연속성을 가지고 있으며, 사용자는 프로시쥬어와 데이터가 실기억장치의 어디에 위치할 것에 대해 염려할 필요가 없다.
2. 기억장치 구성의 변천
① 실(real)기억장치
- 단일사용자 전용 시스템
- 다중프로그래밍
- 고정분할 : 절대 번역 및 배치, 재배치가능 번역 및 배치
- 가변분할
② 가상(virtual)기억장치
- 순수 페이지 기법
- 순수 세그먼트 기법
- 페이지 기법과 세그먼트 기법의 혼용
3. 블럭사상
① 주소의 구조 v = (b, d)
② 실제주소 r = 블럭 b의 시작을 나타내는 실제주소 b' 변위 d
4. 페이지 기법
- 주소의 구조 v = (p, d)
- 페이지는 블럭단위로 보조기억장치로부터 주기억장치로 옮겨져서 페이지 프레임이라 불리는 주기억장치의 블럭에 위치하게되며, 각 페이지 프레임은 입력되는 페이지와 같은 크기이다.
- 페이지 프레임은 고정된 페이지 크기의 정수배에 해당하는 실기억장치 주소에서 시작한다.
- 실제주소 r = 페이지 p를 나타내는 페이지 프레임 p' 변위 d
- 페이지 사상 테이블
페이지
존재 비트 | 보조기억장치주소
(페이지가 실기억 장치내에 없을 때) | 페이지프레임 번호
(페이지가 실기억 장치내에 있을 때) |
r | s | p' |
r = 0 : 페이지가 실기억장치내에 없는 경우
r = 1 : 페이지가 실기억장치내에 있는 경우
- DAT 기법
- 직접사상에 의한 페이지 기법
- 연관사상에 의한 페이지 기법 : 위치지정이 아닌 내용지정의 연관기억장치(associative storage)에 모든 페이지 사상 테이블을 놓은 것이다.
- 연관 / 직접 사상에 의한 페이지 기법 : 한 프로세스의 전체 페이지 사상표의 일부분만 수용할 수 있는 크기의 연관기억장치를 이용(가장 최근에 참조한 페이지 항목만을 유지)
5. 세그먼트 기법
- 프로그램(및 데이타)가 여러개의 분리된 실기억장치 블럭을 차지 할 수 있도록 해주며 각 블럭은 같은 크기일 필요는 없으나 연속된 기억장소로 구성되어야하며, 서로 다른 블럭이 서로 인접할 필요는 없다.
- 페이지기법에 비해 물리적 개념보다 논리적이라는 장점을 가진다.
- 세그먼트 기법의 위치지정 방법은 first-fit, best-fit, worst-fit방법과 동일하다.
- 세그먼트 기법 시스템에서 기억장치보호를 구현하는 한 가지 방법은 기억장치 보호 키(storage protection key)를 사용하는 것이다.
- 순수 세그먼트 기법에서의 가상주소 양식
세그먼트 번호 s | 변위 d | 가상주소 v=(s,d) |
- 세그먼트 기법에서의 액세스 제어
- 각 프로세스에게 세그먼트를 액세스할 권리를 주거나 다른 많은 세그먼트를 액세스하지 못하게 한다.
- 액세스 제어형태
엑세스 유형 | 약자 |
판독(Read) | R |
기록(Write) | W |
수행(Execute) | E |
첨가(Append) | A |
- 직접사상에 의한 세그먼트 기법
- 고속 캐쉬 기억장치에 전체 세그먼트 사상표를 기억시키고 직접사상을 하는 세그먼트 주소 변환
세그먼트
존재비트 | 보조기억장치 | 세그먼트 길이 | 보호비트 | 세그먼트
시작주소 | | | |
r | a | l | R | W | E | A | s' |
. r = 0 : 세그먼트가 실기억장치내에 없는 경우
. r = 1 : 세그먼트가 실기억장치내에 있는 경우
. 보호비트 : ( 1 - 예, 0 - 아니오)
. R : 판독액세스 W : 기록액세스 E : 수행액세스 A : 첨가액세스
6. 가상기억장치 관리기법
① 호출기법(Fetch strategy)
- 페이지나 세그먼트가 언제 보조기억 장치로부터 주기억장치로 옮겨지는지에 관한 문제
- 요구호출(Demand Fetch) : 실행중인 프로세스에 의하여 참조된 페이지나 세그먼트만이 주기억장치로 옮겨지는 기법
- 예상호출(Anticipatory fetch) : 프로세스에 의하여 어떤 페이지나 세그먼트들이 참조될지를 미리 예상하여 그 페이지나 세그먼트가 가까운 장래에 참조될 가능성이 높고 또 그 페이지나 세그먼트가 적재될 수 있는 여지가 있다면 그 페이지나 세그먼트가 실제로 참조되기 전에 미리 주기억장치에 옮겨지는 기법
② 배치기법(Placement strategy)
- 주기억장치에 적재되어야 할 페이지나 세그먼트를 주기억장치의 어느 곳에 적재시킬지를 정하는 기법
- 페이징 시스템 : 주기억장치에 적재될 페이지가 사용 가능한 페이지 프레임이면 어디에 적재되어도 무관하므로 결정의 여지가 없음
- 세그먼테이션 시스템 : 가변분할 다중 프로그래밍 시스템에서 필요로 한 만큼의 기억장소를 할당하는 기법
③ 교체기법(Replacement strategy)
주기억장치가 이미 모두 할당 되어 있는 경우 새로 주기억장치에 적재되어야 할 페이지나 세그먼트를 위해 기존의 페이지나 세그먼트 중에서 어느 하나를 선택하여 주기억장치로 부터 제거하는 기법
7. 페이지 교체기법
운영체제의 기억장치 관리 루틴은 새로 주기억장치에 적재되어야 할 페이지를 위하여 기존의 어느 페이지가 주기억장치로부터 제거되어야 할지를 결정하는 전략
① 최적화 원칙(principle of OPTimality)
② 무작위 페이지 교체(random page replacement)
어느 페이지도 교체될 수 있음을 뜻하며 최악의 경우, 바로 뒤에 참조될 페이지도 교체될 수 있기 때문에 거의 사용치 않음
③ FIFO(First-In First-Out) 페이지 교체
- 각 페이지가 주기억장치에 적재될 때마다 그때의 시간을 기억시켜 한 페이지가 교체될 때에는 주기억장치내에 가장 오래 있었던 페이지를 교체함
- FIFO변칙( FIFO Anomaly 혹은 belady's Anomaly) : FIFO 페이지 교체 기법하에서 프 로세스에 더 많은 수의 페이지들을 할당할 경우 오히려 더 많은 페이지 부재가 발생하는 현상
④ LRU(Least Recently Used)페이지 교체기법
⑤ LFU(Least Frequently Used)페이지 교체기법
⑥ NUR(Not Used Recently)페이지 교체기법
- 근래에 쓰이지 않은 페이지들은 가까운 미래에도 쓰이지 않기 쉽다는 전략
- NUR페이지 교체기법은 각 페이지당 2개의 하드웨어 비트로 구성
- 참조비트 = 0 : 그 페이지가 참조되지 않았을 때
참조비트 = 1 : 그 페이지가 참조된 적이 있을때 - 변형비트 = 0 : 그 페이지 내용이 변형되지 않았을 때
변형비트 = 1 : 그 페이지 내용이 변형되었을 때
8. 국부성(locality)
- 국부성 : 프로세스들은 기억장치내의 정보를 균일하게 액세스하는 것이 아니라 어느 한 순간에 특정부문을 집중적으로 참조하는 성질
① 시간 국부성
- 처음에 참조된 기억장소가 가까운 미래에도 계속 참조될 가능성이 높다.
- 순환(looping), 서브루틴(subroutine), 스택(stack), 계산(counting)과 집계(totaling)에 사용되는 변수
② 공간 국부성
- 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조될 가능성이 높다.
- 배열순회(array traversal), 순차적 코드 실행(sequential code execution), 프로그래머들이 관련된 변수들을 근처에 선언하는 경향
9. Working Set
- 페이지 폴트를 감소시키기 위해 Denning이 제안한 시스템으로 하나의 프로세스가 자주 참조하는 페이지들의 집합
- Working Set는 프로세스를 효과적으로 실행하기 위하여 주기억장치에 유지되어야 하는 페이지들의 집합
10. PFF(Page Fault Frequency) 페이지 교체
- 페이지 부재율은 페이지 기법 환경에서 프로세스가 얼마나 잘 실행하는가의 한 척도.
- PFF 알고리즘은 프로세스의 상주 페이지 세트를 바꿈. 즉, 두 페이지 부재가 일어난 사이의 시간에 따라 빈도를 계산함
11. 페이지 크기
- 페이지의 크기가 작으면 페이지 테이블이 커지며 결국 페이지 테이블 단편화(table fragmentation)를 초래한다.
- 페이지 크기가 크면 실제로 참조되지 않는 명령문이나 데이타들이 주기억장치체 불필요하게 수반되어 적재된다.
- 입출력 전송은 많은 시간을 소비하게 되므로 프로그램이 실행되는 동안 페이지 전송의 횟수를 줄이는 것이 좋다. 즉, 입출력 전송은 큰 페이지가 더 효율적이다.
- 프로그램들이 참조에 있어서 국부성은 작아지는 경향이 있다.
- 작은 페이지를 사용하면 내부 단편화(internal fragmentation)가 감소한다.
5장. 보조기억장치
1. 이동 헤드 디스크
- 회전지연시간(rotational latency time;= 대기시간) : 데이타가 현재 위치에서 판독/기록 헤드에 인접한 위치까지 회전하는 데 걸리는 시간
- 탐색시간(seek time) : 고정축을 새로운 실린더로 옮기는 과정
- 전송시간(transmission time) : 판독/기록 헤드에 의해서 판독, 기록되는 시간
2. 디스크 스케쥴링
① 디스크 스케쥴링
탐색시간을 최소화하기 위해, 대기중인 디스크 요청을 적절히 배열하는 작업. 즉, 레코드를 탐색하는 시간을 최소화하기 위하여 요구 대기행렬의 순서를 정하는 작업
② 작은부하의 상황에서는 FCFS가 요구를 처리하는 데 적당하고, 부하가 큰 상황하에서는 스케쥴링이 FCFS보다 더 좋은 수행결과를 가져옴
③ 스케쥴링 정책을 분류하는 기준
- 처리량(throughput) : 단위시간당 처리되는 요구의 수를 극대화
- 평균응답시간(mean response time) : (평균대기시간 평균 서비스시간)을 최소화
- 응답시간 편차(variance of response time = 예견성: predictability) : 각각 의 항목이 얼마만큼 평균에서 벗어나 있는가를 나타내는 것으로 편차가 작을수록 예상 가능성이 커짐.
3. 디스크 스케쥴링 종류
① FCFS(First-Come First-Served) 스케쥴링
- 먼저 도착한 요구가 먼저 서비스를 받는 것
- 디스크가 작은 부하일 경우는 FCFS가 사용할 만하다. 그러나 부하가 커질수록 FCFS는 장치를 포화시키가 쉽고 응답시간이 길어진다.
② SSTF(Shorest-Seek-Time-First) 스케쥴링
- 최단 탐색거리(탐색시간)를 가져오는 요구는 비록 대기 행렬의 제일 앞에 있지 않더라도 먼저 처리한다. 즉 실린더 지향의 방법.
- FCFS보다 처리량이 많고, 중간정도의 부하량에서는 평균응답시간이 짧다.
- SSTF 탐색 패턴은 중간범위의 트랙에 비해 최내각과 최외각 트랙이 서비스를 절대로 받지 못하는 심각한 국부성을 갖는 경향이 있다. → 특정요청들을 차별하는 경향으로 응답시간에 큰 편차가 생긴다. <
[ppt] 메모리 할당에 관한 좋은 자료.ppt
釉
嫄몄
嫄몄
移