IT/OS

운영체제 1차 정리 - 스케줄링

김효랑이 2018. 10. 26. 10:32
728x90
반응형

 호야의 블로그 

[OS] 운영체제 1차 정리

작년에 정리한 운영체제 과목을 공유하고자 합니다. 최대한 간단히 정리하였습니다.


OS - Scheduling

1. 멀티프로그래밍

-CPU사용/IO ->메모리 사용 ->실행 우선권


2. 타임 쉐어링(Time Sharing): 동일 시간으로 배분


3. 계층 접근 방식(layered approaches): OS를 여러 계층으로 나누고 각 계층의 하위 계층에 놓음

app        장점: 모듈화 / 단점: 정의가 어렵다

HW

OS ->user/kernel


4. 프로세스: 실행중인 프로그램, 능동적이다. 일의 기본 단위(unit of working)

프로그램: 수동적인 동작을 하며 메모리에 미리 안 올라가있다.

프로세스의 주기: 탄생-활동-죽음(상태 변화로 일어남)


new  -> ready <--> run -> terminate 

new queue: 디스크에 위치하는 상태이며, CPU에 프로세스를 올리기 전 상태로 프로세스의 탄생이다.

ready Q: new에서 넘어온 프로세스를 대기하는 상태이다. 대기 중인 상태에서 I/O이벤트가 끝나면 다시 레디 상태가 된다.

run Q: 레디 큐에서 CPU로 가져와서(dispatcher) 동작하고, 잠시 끊어서(time-out; 일시정지) 레디 큐로 갈 수 있다.

waiting Q: I/O 이벤트가 멈추거나 방해가 일어날 때 대기하는 상태이다.

terminate Q: running 중인 프로세스가 CPU에서 내려온 상태. 프로세스의 죽음이다.


이 과정은 메모리(가상 메모리) 사이에서 지속적인 스와핑이 일어나며 이 과정은 mid-term 스케줄러.


#cpu와 메모리 사이에 일어나는 일

- cpu는 run 상태인 주소번지를 가져온다. 메모리에서 해당 데이터를 가져오고, 데이터 레지스터를 CPU가 불러와 명령어를 실행한 후 메모리에 writing한다.


5. PCB(Process Control Block)

-프로세스 상태

-CPU 레지스터

-메모리 관리 정보

-프로그램 카운터

-CPU 스케줄링 정보

-액세스 정보

-I/O 상태 정보


#콘텍스트 스위칭

- dispatching과정은 PCB에서 CPU로 정보를 로드한다.

- I/O 이벤트 발생 시와 time-out과정은 정보를 writing하여 PCB로 내보낸다.

이러한 과정을 콘텍스트 스위칭이라 함. ex) 친구랑 얘기 중 전화 받아도 친구와 대화내용이 메모리에 저장되어있음.


6. 스케줄링 알고리즘

-스케줄링 큐

a. job Q: 메인 메모리에 있고, mass 스토리지(disk)에서 가져온다.

b. ready Q: 메인메모리에 있는 프로세스를 CPU에 올림

c. device Q: 키보드 큐, 프린트 큐(버퍼가 있음) I/O


7. CPU 스케줄링(시스템 전체에 퍼포먼스를 고려한 공평성을 위함) 

 long-term 스케줄러: new->ready 사이

 midium-term 스케줄러: swap에 관여

 short-term 스케줄러: CPU 스케줄링, ready -> run (CPU에서 동작해서 속도가 제일 빠르다)

 

8. 스케줄링 알고리즘-스케줄러가 활성화 될 때(involking)

1.레디 큐에 2개 이상 프로세스

2.상태가 변할 때

3.이벤트가 발생할 때

4.PCB에 접근량이 증가할 때

5.run상태가 될 때(dispatching)

6.run->ready(time-out)

7.프로세스가 종료(terminated)

8.I/O가 발생할 때(waiting)

(5~8까지는 run state에서 스케줄러가 동작)


-time-out과 dispatching은 강제 집행된다.(프로세스가 CPU의 명령을 받음;preemptive)-I/O 이벤트와 종료는 비강제적이다.(이미 이전에 인터럽트가 발생하기 때문에;non-preemptive)short-term 알고리즘에서 강제로 하는 것(강제 kill)과 비강제로 하는 알고리즘이 존재


9. 평가기준(performance criteria)

- CPU utilization(사용량) = running T(cpu동작시간)/running T + idle T(전체 동작시간)

- thru-put: 단위시간 당 처리한 프로세스 수 = #process/총 시간

- response time: 일을 시작해서 결과가 다 나올 때까지 시간(응답시간) 대기시간 포함

mean response time = Σresponse time(총 응답시간)/#process

-waiting time: 레디 큐에서 소비한 시간

- turn around time = 종료시간 – 도착시간 -> I/O까지 고려한 시간


10. FCFS(first come first service;FIFO) -> 중간에 강제로 바뀌는 것이 없어서 non-preemptive

-먼저 들어오는 것 먼저 처리; arrival time이 빠른 것 순서대로 처리한다.


#convoy effect: 긴 프로세스가 큐에 있어서 뒤에 짧은 프로세스가 오래 대기하는 현상


11. SJF(shortest job first): 동작시간이 제일 작은 것 우선 처리. 

중간에 큐에서 강제로 내보내지 않아서 non-preemptive

-동작시간(burst T)을 아는 방법은 그 프로세스에 대한 정보, 로그를 통한 예측으로 서비스한다.


#starvation: 이 알고리즘에서는 프로세스 처리 중에 계속 짧은 프로세스가 들어오면 긴 프로세스는 계속 서비스를 못 받고 기아 현상이 발생한다.


12. SJF with preemptive(SRT; shortest remaining Time First)

시간마다 프로세스의 burst time을 비교하여 남은 burst T이 짧은 프로세스를 우선 처리하는 알고리즘.

중간에 큐애서 강제로 빼기 때문에 preemptive

-SRT는 매시간 비교하기 위해 정보를 항상 유지하고 있어야하기 때문에 부하가 올 수 있다. 같은 remaining time을 가지는 경우 먼저 들어온 프로세스를 먼저 처리한다.(FCFS)


#오래 기다리는 프로세스를 위한 대책(starvation)->aging으로 해결


13. aging: ready Q에 오래있는(나이 든) 프로세스에게 우선권을 주는 정책.


14. HRN(highest Response ratio Next) 

컨셉: shortest job, long waiting job -> highest priority

Dynamic Priority = (WT+BT)/BT가 높을수록 우선 처리


15. 라운드 로빈 알고리즘: Quantum을 이용(CPU가 서비스하는 시간)

#run -> ready에서 일어나는 time-out은 퀀텀이 빠지는 것과 같다.

만약 한 큐에 여러 개의 프로세스가 있으면 도착한 순서가 빠른 것(FCFS)


16. Priority 알고리즘

-유저 레벨이 높다.

-도착시간이 짧다.

-동작시간이 짧다.

-대기시간이 길다.

-> starvation 문제 발생은 aging으로 해결


17. Multi-Level Queue(큐가 여러 개;지금까진 큐가 1개였다)

프로세스의 성격에 따라 큐에 나누어져서 들어감(중간에 성격이 변해도 큐 이동은 불가)

한 큐에서 일정 기간 반복하며 머무르다가 다음 큐로 이동하는 것도 가능하다.


후기 및 정리

여러분들이 공부하는데 조금이라도 도움이 되고 싶습니다.



조금의 도움이 되셨다면 로그인 없이도 가능한 댓글과

왼쪽 아래 ♥공감 버튼을 꾹 눌러주세요! 




728x90
반응형
저작자표시

'IT > OS' 카테고리의 다른 글

운영체제 3차 정리 - Memory Management (1)  (0) 2018.10.26
운영체제 2차 정리 - 데드락(Deadlock)  (0) 2018.10.26
운영체제 CPU 스케줄러  (0) 2018.10.24
진짜 간단히 정리한 OS 프로세스 개념  (2) 2018.10.24
운영체제에 대해서  (0) 2018.10.18

'IT/OS'의 다른글

  • 현재글운영체제 1차 정리 - 스케줄링

관련글

티스토리툴바