제3,4,5장 프로세스, 스레드 관리 CPU 스케줄링.

Presentation on theme: "제3,4,5장 프로세스, 스레드 관리 CPU 스케줄링."— Presentation transcript:

1 제3,4,5장 프로세스, 스레드 관리 CPU 스케줄링

2 개요 중앙처리장치(CPU)는 컴퓨터 자원 중 가장 중요한 자원 중앙처리장치 스케줄링 정의 목적
사용자로부터 의뢰받은 작업을 처리하기 위해 프로세스들에게 중앙처리장치 또는 프로세서들을 할당하기 위한 정책 목적 중앙처리장치 효율 및 처리율(throughput)의 최대화와 반환시간(turnaround time)의 최소화

3 프로세스 관리 프로세스의 정의 프로세스 관리 실행(executing, running) 중인 프로그램
PCB(process control block)를 지닌 프로그램 프로그램 카운터(program counter)를 지닌 프로그램 능동적 개체(entity)로, 순차적으로 수행하는 프로그램 프로세스 관리 사용자 프로세스와 시스템 프로세스의 생성과 삭제 프로세스의 일시 중지와 재 수행 프로세스 스케줄링 프로세스의 동기화 프로세스 간 통신 교착상태 처리

4 프로세스 구성 요소 프로세스의 저장 영역 코드(code) 영역 데이터 영역 스택(stack) 영역 힙 영역
프로그램의 코드 자체가 바이너리 코드로 저장되는 공간 데이터 영역 프로그램의 전역 변수(global variable)나 정적 변수(static variable)의 할당을 위한 공간 스택(stack) 영역 지역 변수(local variable) 할당과 함수 호출 시 전달되는 인수(argument) 값의 저장공간 힙 영역 동적 할당을 위한 저장공간

5 프로세스 구성 요소 프로세스 구성 요소

6 프로세스의 상태 실행 상태(running) 준비완료 상태(ready) 대기 상태(block)
프로세스가 중앙처리장치를 차지하고 있는 상태 준비완료 상태(ready) 중앙처리장치가 사용 가능하게 될 때 그것을 할당 받을 수 있는 상태 대기 상태(block) 프로세스가 입출력 처리 등을 하게 되면 중앙처리장치를 양도하고 입출력 처리가 완료될 때까지 대기해야 한다

7 프로세스의 상태 프로세스의 상태 전이 디스패치(dispatch) : 준비완료 상태 → 실행 상태
timer runout : 실행 상태 → 준비완료 상태 block : 실행 상태 → 대기 상태 wake­up : 대기 상태 → 준비완료 상태 프로세스의 상태 전이

8 프로세스 제어 블록(PCB) 정의 PCB 내용 모든 프로세스는 각기 고유의 PCB 지님
프로세스에 관한 모든 정보를 가지고 있는 데이터베이스 PCB 내용 프로세스의 현재 상태(실행, 준비완료, 대기 등) 프로세스의 고유 이름(identifier) 프로세스의 우선순위 프로세스가 적재된 기억장치의 주소를 가지는 포인터 할당된 자원(장치 등)을 가리키는 포인터 중앙처리장치의 각종 레지스터 상태를 저장하기 위한 공간 모든 프로세스는 각기 고유의 PCB 지님

9 프로세스 제어 블록(PCB) 프로세스 제어 블럭(PCB)

10 프로세스 생성 유닉스 환경에서 프로세스를 생성시키는 것은 fork( ) 명령어 프로세스 생성 명령어 fork()

11 프로그램 예

12 프로세스 스케줄링 스케줄링의 목적 공정성 응답 시간의 최소화 예측 가능 오버헤드(overhead)의 최소화
자원 사용의 균형유지 응답과 이용 간의 균형 유지 실행의 무한지연을 피할 것 : 에이징(aging)기법 우선순위제의 실시 주요 자원들을 차지하고 있는 프로세스에게 우선권을 부여 좀 더 바람직한 동작을 보이는 프로세스에게 더 좋은 서비스를 제공 과중한 부하를 감소

13 프로세스 스케줄링 스케줄링 기법의 고려기준 입출력 위주의 프로세스인가? 연산 위주의 프로세스인가?
프로세스가 일괄 처리형인가 대화형인가? 긴급한 응답이 요구되는가? 프로세스의 우선순위 프로세스가 페이지 부재를 얼마나 자주 발생시키는가? : 작업세트 확보 높은 우선순위를 지니는 프로세스에 의해서 얼마나 자주 프로세스가 선점(preempted) 되는가? 프로세스가 받은 실행 시간은 얼마나 되는가? 프로세스가 완전히 처리되는 데 필요한 시간은 얼마나 더 요구되는가?

14 프로세스 스케줄링 단계별 분류 상위 단계 스케줄링(high­level scheduling)
작업(job) 스케줄링이라고도 불림 어떤 작업에게 시스템의 자원들을 차지할 수 있도록 할 것인가를 결정 중간 단계 스케줄링(intermediate level scheduling) 시스템 전체의 성능향상을 위하여 허용되는 시스템부하 내에서 짧은 순간에 프로세스들에 대한 일시적인 활동의 중단 및 재개를 수행 하위 단계 스케줄링(low level scheduling) 어떤 준비완료 프로세스(ready process)에게 중앙처리장치를 할당할 것인가를 결정

15 프로세스 스케줄링 큐를 이용하여 재구성한 스케줄링 단계

16 프로세스 스케줄링 방법·환경별 분류 선점/비 선점(preemptive/non­preemptive) 스케줄링 비 선점스케줄링
하나의 프로세스에 중앙처리장치가 할당되면 그 프로세스의 수행이 끝날 때까지 중앙처리장치는 그 프로세스로부터 빠져나올 수 없다. 선점스케줄링 하나의 프로세스가 중앙처리장치를 차지하고 있을 때 다른 프로세스가 현재 수행 중인 프로세스를 중지시키고 자신이 중앙처리장치를 차지할 수 있음 시분할 시스템에서는 선점 스케줄링으로 빠른 응답 시간을 보장해 주는 것이 중요함

17 프로세스 스케줄링 방법·환경별 분류 우선순위(priority) 스케줄링
각 프로세스에게 우선순위를 부여하여 우선순위가 높은 순서대로 처리하는 방법 정적 우선순위(static priority) 기법 상대적으로 오버헤드는 적으나, 주위 여건의 변화에 적응하지 않고 우선순위를 바꾸지 않는다. 동적 우선순위(dynamic priority) 기법 필요에 따라 우선순위 재구성

18 프로세스 스케줄링 기한부(deadline) 스케줄링 작업들이 명시된 시간이나 기한 내에 완료되도록 계획
실시간 시스템에는 두 가지 종류 경성 실시간 시스템(hard real-time system) 정한 시간 내에 완료할 수 있도록 해주는 강한 형태의 실시간 시스템 연성 실시간 시스템(soft real time system) 시간적 제한이 다소 약한 형태의 실시간 시스템 정적(static)스케줄링 방식 시스템에 의해 실행되는 태스크집합이 미리 정의되어 있는 경우 주기적인 연성 실시간 태스크 집합에 유용 동적(dynamic)스케줄링 방식 태스크의 발생 시간이나 특성을 미리 예측할 수 없을 경우에 유용 보장된 주기의 시간 내에 서비스를 보장받기 위해서는 경성 실시간 스케줄링이 요구됨

19 프로세스 스케줄링 기한부(deadline) 스케줄링 RM(Rate Monotonic) 알고리즘 대표적인 정적 스케줄링 방식
주기가 짧을수록 더 높은 우선순위를 부여 EDF(Earliest-Deadline First) 알고리즘 대표적인 동적 스케줄링 방식 임계 시간이 가장 근접한 태스크를 가장 먼저 수행하는 방식

20 프로세스 스케줄링 다중 프로세서(Multiple Processor) 스케줄링 프로세서들의 형태는 동질 시스템 또는 이질 시스템
이질 시스템의 경우 각 프로세서는 자신의 큐가 있으며 자신의 스케줄링 알고리즘을 가진다 프로세서들이 동질일 경우 부하 공유(load sharing) 두 가지 스케줄링 방식 각 프로세서가 스스로 스케줄링하며, 공동 준비 큐를 조사하여 실행할 프로세스를 선택 한 프로세서가 다른 프로세서를 위한 스케줄러로서 지정되어 주­종 구조(master­slave structure)를 구성

21 프로세스 스케줄링 알고리즘 FCFS(First Come First Served) 스케줄링 가장 간단한 스케줄링 방식
가장 간단한 스케줄링 방식 비선점 스케줄링방법 프로세스들은 대기 큐에 도착한 순서에 따라 중앙처리장치를 할당 호위 효과(convoy effect) 첫 번째 프로세스가 끝날 때까지 매우 긴 시간을 기다리게 되는 것  CPU와 장치 이용률이 낮아진다

22 프로세스 스케줄링 알고리즘 SJF(Shortest Job First) 스케줄링
프로세스 중에서 수행시간이 가장 짧은 것을 먼저 수행하는 비선점 스케줄링 방식 긴 프로세스보다 짧은 프로세스에게 더 유리하다. 문제점 수행될 프로세스나 프로세스가 얼마나 긴 것인가를 정확히 알아야 하는데, 이 정보를 얻기가 어려움 시분할방식의 시스템 상황에서는 적당하지 못하다. FCFS 와 SJF 방식의 평균 반환시간 비교

23 프로세스 스케줄링 알고리즘 우선순위(Priority) 스케줄링
각 프로세스에게 주어지며, 중앙처리장치는 가장 높은 우선순위를 가진 프로세스로 할당 주요 문제 무한 대기(indefinite blocking) 또는 기아 현상(starvation) 낮은 우선순위의 프로세스들이 중앙처리장치를 무한히 대기하게 하는 경우 낮은 우선순위의 프로세스들의 무한 대기 문제에 대한 해결책  에이징(aging)

24 프로세스 스케줄링 알고리즘 라운드 로빈(Round-Robin) 스케줄링 시분할 시스템을 위하여 고안된 선점 스케줄링 방식
각 프로세스는 같은 크기의 중앙처리장치 시간을 할당 받음 할당시간(time quantum)의 크기는 보통 10에서 100ms 사이 라운드 로빈 스케줄링

25 프로세스 스케줄링 알고리즘 라운드 로빈(Round-Robin) 스케줄링 할당시간에 따른 문맥 교환의 횟수

26 프로세스 스케줄링 알고리즘 SRT(Shortest Remaining Time) 스케줄링 SJF 기법에 선점 방식을 도입한 방법
시분할 시스템에서 유용 새로 도착한 프로세스를 포함하여 처리가 완료되는 데 가장 짧은 시간이 소요된다고 판단되는 프로세스를 먼저 수행 SRT 방식으로 평균 반환시간과 평균 대기시간 구하기

27 프로세스 스케줄링 알고리즘 다단계 큐(Multilevel Queue) 스케줄링
작업들을 여러 그룹으로 나누어 여러 개의 큐를 이용하는 기법 전면작업 프로세스들은 후면작업 프로세스들 보다도 높은 우선순위 부여됨 후면작업 큐가 선입선출 알고리즘에 의해 스케줄 되는 반면 전면작업 큐는 라운드 로빈 알고리즘에 의해 스케줄 됨 큐별로 스케줄링 전면작업 큐에는 자신의 프로세스들 사이에서 라운드 로빈 스케줄링을 위해 중앙처리장치 시간의 80% 후면작업 큐는 자신의 프로세스들을 선입 선 처리 방식으로 중앙처리장치 시간의 20% 등의 방법으로 처리

28 프로세스 스케줄링 알고리즘 다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링
대부분의 다단계 피드백 체계에서는 프로세스가 하위 단계의 큐로 옮겨갈수록 주어진 할당시간은 점차 크게 설정 다단계 피드백 큐

29 프로세스 스케줄링 알고리즘 HRN(High Response ratio Next) 스케줄링
SJF의 약점, 특히 긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법 일단 한 작업이 중앙처리장치를 차지하면 그 작업은 완성될 때까지 실행하며, 대기시간이 고려되어 긴 작업과 짧은 작업 간의 불평등을 어느 정도 완화됨

30 스레드(Thread) 다중 스레드를 사용하는 유닉스의 경우 특성
스레드는 각각 독립적으로 실행할 수 있고, 각 스레드의 실행 순서는 시그널이나 동기화 방법을 통해서 제어 특성 각 스레드는 서로 독립적 스레드의 실행/종료 순서는 예측할 수 없음 스레드들은 수행을 위해 스케줄 되고 결과들은 프로세스에게 전달 프로그램에 있는 스레드의 수는 다른 스레드에게 알려지지 않음 스레드는 프로그램의 외부에서는 보이지 않음 스레드는 서로 독립적이지만, 한 스레드가 취한 행동은 프로세스에 있는 다른 스레드에 영향을 미침 스레드는 프로세스의 일부분이기 때문에 프로세스의 자원들을 공유하지만 그 자신의 처리시간과 스택, 레지스터들이 할당 한 프로세스가 exit( ) 시스템 콜을 통해 종료되면, 모든 스레드들도 종료

31 스레드(Thread) 스레드와 프로세스

32 스레드(Thread) 스레드와 프로세스 포함 정보

33 스레드(Thread) 프로세스와 다중 스레드

34 스레드(Thread) 다중 스레딩 다수의 스레드를 이용하여 하나의 프로그램을 동시에 처리하는 것
하나의 프로세스 자체에 다수의 실행 단위들이 존재하여 작업의 수행에 필요한 자원들을 공유하기 때문에 자원의 생성 및 관리가 중복되는 것을 최소화 중량 프로세스(HWP : Heavy Weight Process)는 하나의 스레드를 가진 프로세스 경량 프로세스(LWP : Light Weight Process)는 프로세스 내에 두 개 이상의 스레드를 포함하고 있을 경우 KLT(Kernel-level threads)방법 Mach, OS2, Linux, Unix, Windows 등에서는 스레드들이 커널에 의하여 지원 ULT(User-level threads)방법 POSIX(Portable OS Interface)는 사용자 수준에서 라이브러리 호출 집합을 통하여 커널의 상위 수준에서 지원