정보처리산업기사 용어 정리2

스케줄링

스케줄링이란, 어떤 프로세스가 어떤 우선순위로 CPU를 얼만큼 사용할 것인지 결정하고 수행하는 과정이다.

 

스케줄링의 목적

• 모든 프로세스들에게 CPU를 공평하게 배정하기 위해서 (공평성)
• 단위 시간당 일을 최대한 많이 처리하기 위해서 (처리율을 극대화시키기 위함)
• 수행해야하는 일에 대해 빠른 응답을 하기 위해서
• * 오버헤드를 최소화하기 위해서
• 프로세스 무한대기를 최소화하기 위해서(교착상태Deadlock)

* 오버헤드 : 어떤 일을 수행하기 하기 위해 들어가는 처리 시간이나 메모리

 

 

 

 

스케줄링의 종류

 

선점형(Preemptive)
프로세스가 점유한 CPU를 다른 프로세스가 빼앗을 수 있다.
대화형, 시간 분할, 실시간 시스템에서 쓰인다.
대표적으로 RR(Round Robin), SRT(Shortest Remaining Time), MFQ(Multi level Feedback Queue) 등이 있다.

 

 

비선점형(Non preemptive)
점유된 CPU를 다른 프로세스가 빼앗을 수 없다.
일괄처리 방식에서 쓰인다.

대표적으로 FIFO, SJF, HRN, 우선순위, 기한부 방식이 있다.

 

 

RR(Round-Robin) 스케줄링 - 선점형

 

RR(Round-Robin, 라운드로빈) 스케줄링

할당 받은 시간(Time Slice, Time Slot) 동안 번갈아가면서 작업하는 스케줄링 방식이다.

선점형 방식이다.

시간 할당량이 무한대이면 FIFO 방식과 동일하다.

 

 

 

 

SRT(Shorest Remaining Time) 스케줄링 - 선점형

작업이 끝나기까지 남아 있는 시간이 가장 작은 프로세스를 먼저 실행하는 방식이다.
선점형 방식이다.

 

 

 

 

MFQ(Multi level Feedback Queue, 다단계 피드백) 스케줄링 - 선점형

 

짧은 작업이나 입출력 위주의 작업에 우선권을 부여하는 것이다.

선점형 방식이다.

SJF스케줄링(Shortest Job First) - 비선점형

 

최단 작업 우선 스케줄링이다.

일을 처리하는 데 시간이 가장 적게 걸리는 작업을 먼저 처리한다.

비선점형 방식이다.

 

 

 

HRN(Highest Response-ratio Next)스케줄링 - 비선점형

 

우선 순위를 적용해서 우선 순위 값이 클 수록 먼저 처리하는 방식이다.

우선순위 = (대기시간 + 실행시간) / 실행시간

비선점형 방식이다.
FIFO와 SJF를 개선한 방식이다.

 

 

 

 

임계 구역

 

임계 구역(Critical Section) == 임계 지구(지역, 영역)
임계 구역이란, 두 개 이상의 프로세스가 동시 접근이 불가능한 영역이다(공유 자원에 접근할 때).

동시 접근에 따른 문제를 방지하기 위하여 지정된 영역이다.

 

한 순간에 여러 개의 프로세스에 의하여 공유되는 데이터 및 자원이 있다고 가정을 해보자.

임계 구역은 프로세스가 서로 동시 접근과 독점할 수 없다.

한 번에 한 프로세스만 접근해서 사용할 수 있다.

그래서 임계 구역을 접근할 때에는 반드시 가용 상태를 확인해야 한다.

 

 

 

 

Mutual Exclusion

 

한 프로세스가 공유 메모리 혹은 공유 파일을 사용하고있을 때, 다른 프로세스들이 사용하지 못하도록 배제시키는 제어 기법이다.(상호배제)
대표적인 예로 Semaphore, 잠금(Lock / Unlock), 엄격한 교대(Dekker) 등이 있다.

 

 

 

 

Semaphore

 

E.J. Dijkstra에 의해 고안된 방식으로,

프로세스간 상호배제 및 동기화 문제 해결한다.
근본적으로 공유 자원에 대하여 동시 접근을 막는다.

(자주 틀리는 문제)

세마포어의 동작(operation)과 관련이 없는 것은?
답 : C연산

 

 

Monitor

공유 자원을 내부로 숨기는 것이다.
모니터의 경계에서 상호 배제가 시행된다.

 

 

교착상태(Dead Lock)

 

교착상태(Dead Lock)란, 2개 이상의 프로세스가 서로 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태이다.

즉, 어떤 프로세스도 오고 가지 못하는 상황이다.

병렬처리 기술과 자원 공유에 따라 발생된 부작용 중의 하나이다.

 

+ 아사(기아) 현상 : 특정 프로세스의 작업이 끊임없이 지연되는 문제

 

교착상태의 필요조건

 

1. 상호 배제(mutual exclusion) : 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원
2. 비선점(non-preemptive)
3. 점유와 대기(hold and wait)
4. 순환(환형) 대기(circular wait)

 

 

 

 

교착상태 해결 방안

1. 예방(Prevention) : 사전에 조치를 취하는 방안, 교착상태 발생의 네 가지 조건 중 하나를 제거

2. 회피(Avoidance) : 시스템의 상태를 계속 감시
   자원의 요청이 있는 프로세스에 대하여 Dead Lock 상태가 될 가능성이 있는 경우 요청을 보류한다.
   시스템을 항상 Safe State로 유지한다.
   ex) 은행원 알고리즘 : 프로세스가 요구한 자원의 수가 현재 가용한(남은) 자원의 수보다 작을 때 할당

 

3. 회복(Recovery) : 프로세스 종료(Process Termination), 자원 선점(Resource Preemption)

 

 

가상 기억 장치(Virtual Memory)

 

보조 기억 장치의 일부를 주기억 장치 처럼 사용하는 것을 말한다.
프로그램 크기의 제약을 극복할 수 있지만 아무래도 하드디스크의 공간을 RAM처럼 사용하는 거라서 실행 속도가 떨어진다.

 

 

 

 

가상 디스크(Virtual Disk)

 

가상 기억 장치와 반대로 주기억 장치의 일부를 보조기억 장치처럼 사용하는 것이다.

ex) 램드라이브(RAM Drive)

 

 

 

 

인터리빙(Interleaving)

 

기억 장치의 연속된 위치를 서로 다른 뱅크로 구성하는 것이다.
동시에 여러 개의 위치에 접근이 가능하기 때문에 속도가 향상된다.

 

 

DMA(Direct Memory Access)

 

CPU를 거치지 않고 주변장치가 직접 주기억 장치에 접근하는 것이다.
그래서 입출력 속도가 향상된다.

* 사이클 스틸링(Cycle Stealing사이클 훔치기) 기법이 사용된다.

 

 

Cycle Stealing(중요!!)
CPU와 주기억장치가 주기억장치의 동일한 곳을 접근할 때 수행되는 기법이다.
입출력 장치에 더 높은 우선순위를 부여한다.(주기가 느리니까)

 

 

 

 

폴링(Polling)

 

하나의 장치가 독립적인 기능을 하는 다른 장치의 상태를 계속하여 감시(또는 허가)하는 것이다.

 

메모리 공간

 

운영체제 내 각 프로세스는 분리된 메모리 공간을 가진다.
다른 프로세스 공간의 접근(침입)을 차단 <- 보안성 제공

 

기억 장치 분할

 

기억 장치를 분할 하는 방법에는 2가지가 있다.

 

1. 고정 분할(정적 분할, Fixed Partitions)

고정 분할 == 페이징, Page, Paging

고정된 크기를 갖는 블록으로 주기억 장치의 공간을 분할하는 것이다.

자원을 고정된 블록 안에다 넣으면 어쩔 수 없이 블록의 남는 공간 생기는데, 이 남는 공간이 생기는 것을 내부 단편화라고 한다.

프로세스 하나가 여러 개로 나뉘어 메모리에 할당된다.

비연속 메모리 할당 기법을 사용한다.

페이지 부재(Page Fault) : 프로그램에서 접근하려고 하는 페이지가 주기억 장치에 있지 않을 경우 발생하는 것이다.

 

2. 가변 분할(동적 분할)
== 동적 분할, Segment, Segmentation

프로그램에 따라 크기를 동적으로 분할하는 것이다.
가변 크기를 같는 블록을 할당하면 블록 간의 남는 공간(hole)이 생김이것을 외부 단편화(External Fragmentation)라고 한다.(프로세스를 적재하거나 소멸 과정에서 생김)
프로세스를 동적의 크기를 갖는 여러 개의 세그먼트(Segmentation)로 나누었다.
세그먼트를 나눌 때, 프로그램을 구성하는 서브루틴(subroutine), 프로시저(procedure), 함수 (function) 단위로 한다.

 

 

 

 

배치 전략(Placement Strategy)

내부 단편화 : 자원을 고정된 블록 안에다 넣으면 남는 공간 생김
외부 단편화 : 가변 크기를 같는 블록을 할당하면 블록 간의 남는 공간(hole)이 생김

 

내부 단편화와 외부 단편화가 생겼을 때 새로 들어온 프로세스를 어디에 배치할 지 정하는 전략을 
배치 전략(Placement Strategy)이라 한다.

 

배치 전략에는 3가지 방법이 있다.

 

1. First-Fit: 프로세스가 들어갈 수 있는 첫번째 hole를 선택
2. Best-Fit: 점유할 때 가장 작은 hole이 발생될 수 있는 공간을 선택
3. Worst-Fit: 가장 큰 hole을 선택
   
   

 

메모리 통합(Coalescing)

메모리 통합(Coalescing)이란, Hole들이 인접해 있을 때, 하나의 홀로 통합하는 것이다.

이렇게 하면 커다란 hole이 생기는데 그 곳에다가 새로 들어온 프로세스를 배치한다.

 

 

메모리 집약(압축, Compaction, Garbage-collection)

분산된 프로세스 영역을 이동시켜서 한 곳으로 몰아서 정리하는 것이다.

이렇게 하면 마찬가지로 충분한 크기의 hole이 생겨서 새로 들어온 프로세스를 넉넉하게 배치할 수 있다.

단점은 성능 저하된다.

 

공유 페이지

다중 태스크환경에서 공유되는 명령코드들에 대한 공간이다.

오직 읽을 수만 있으며 스스로 수정하지는 못한다.

 

 

 

 

스래싱(Thrashing)

스래싱(Thrashing)이란, 프로세스가 작업 수행 과정 중 지나치게 페이지 부재 시 전체 시스템의 성능이 저하되는 현상이다.
필요한 페이지가 없으면 직접 페이지를 가져와야하는 교체작업을 해야하는데, 이 교체 작업이 많아지면 속도가 저하된다.

그렇기 때문에 스래싱이 생기게 된다.


스래싱 예방하는 방법

 

• 다중 프로그래밍의 정도를 낮춘다.
• 동시 실행 프로그램 수 줄인다.
• CPU 이용률을 낮춘다.
• 페이지 부재(Page Fault)율을 조절한다.
• 자주 사용하는 페이지들을 주기억 장치에 미리 갖다 놓음 (* Working Set)

 

Working Set(작업 집합) -> 중요!!
원활한 프로세스 동작을 위한 주기억 장치에 유지되어야 할 페이지들의 집합(많이 사용될 페이지 집합)
페이지 부재 최소화를 위함

 

 

 

 

구역성(Locality)

구역성(Locality)이란, 앞으로 사용가능성이 높은 페이지 들을 미리 가져와두는 것이다.

시간 구역성 : 최근 참조를 중점 : 반복문...
공간 구역성 : 접근한 장소에 중점 : 배열 접근...

 

 

 

기억 장치 관리 전략

 

기억 장치 관리 전략에는 3가지가 있다.

 

1. 반입 전략(Fetch Strategy)

보조기억장치 내 프로그램/데이터를 주기억 장치로 가져오는 시기 결정하는 것이다.
종류 :

요구 반입 - 요구가 있을 때마다 주기억 장치로 옮기는 방식
예상 반입 - 앞으로 요구될 데이터 또는 프로그램을 미리 주기억 장치에 적재


2. 배치 전략(Placement Strategy)
프로그램/데이터를 주기억 장치에 배치하는 것이다.
종류 : 최초(First Fit), 최적(Best Fit), 최악(Worst Fit)  <-- 위에서 설명함

 

3. 교체(재배치) 전략(Replacement Strategy)

빈 공간 확보를 위해 제거할 프로그램/데이터를 선택하는 것이다.

종류 : 최적화(OPT), FIFO(FCFS), LRU, LFU, NUR, PFF

 

 

 

 

OPT 전략

== OPTimal Replacement, 최적 재배치 전략
앞으로 가장 오랫동안 사용되지 않을 페이지와 교체 하는 것이다.(미래만 봄)
Belady가 만든 알고리즘이다.

미래는 예측할 수 없기 때문에 실현 가능성이 희박하다. 

 

 

FIFO 전략

 

== First In First Out

먼저 들어온 프로세스를 먼저 실행하는 전략이다.

 

 

 

LRU 전략

 

== Least Recently Used

      최소   최근   사용됨

최근에 사용한걸 남기는 전략이다.(미래는 안봄)
참조된 지 가장 오래된 페이지를 대체한다.

 

 

LFU 전략

 

== Least Frequently Used

     최소     자주     사용됨     

사용 횟수가 가장 적은 페이지를 교체하는 것이다.(미래는 안봄, 과거 ~ 지금까지)
참조 횟수가 가장 적은 페이지를 교체한다.

 

 

NUR 전략

== Not Used Recently

      사용안됨  최근에

최근에 사용(참조)하지 않은 페이지를 가장 먼저 제거하는 전략이다.
오래전 호출, 오래전 변형된 것이 교체 대상 1순위이다.
두 개의 비트(bit)로 페이지 사용과 변형 상태를 관리한다.

0은 없음, 1은 있음 뜻한다.

 

 

 

 

PFF 전략

 

== Page Fault Frequently

자주 사용(참조)하는 페이지들을 주기억 장치에 미리 배치하는 것이다.

Page fault를 낮춘다.

 

 

 

Second Chance

 

FIFO의 2차 기회를 부여하는 것이다.

 

 

 

디스크 접근 시간

탐색 시간(Seek Time)
회전 지연시간(Latency Time, Rotational Delay, RPM 지연 시간)
전송 시간(Transmission Time)

 

 

 

 

 

 

 

출처 : 시스템분석설계(21-2학기)김병국교수 강의 내용 변형 및 요약