2017 운영체제 CHAPTER 02 프로세스와스레드관리 SEOKRAE KIM
내용 I. 프로세스와스레드관리... 1 1. 개요... 1 1) 중앙처리장치 (CPU)... 1 2) 중앙처리장치스케줄링... 1 2. 프로세스관리... 1 1) 프로세스의정의... 1 3. 프로세스구성요소... 2 4. 프로세스의상태... 2 1) 실행상태 (running)... 2 2) 준비완료상태 (ready)... 2 3) 대기상태 (block)... 2 5. 프로세스제어블록 (PCB)... 3 6. 프로세스생성... 3 7. 프로세스스케줄링... 4 1) 스케줄링의목적및기준... 4 2) 단계별분류... 4 3) 방법 환경별분류... 5 8. 프로세스스케줄링알고리즘... 6 1) FCFS(First Come First Served) 스케줄링... 6 2) SJF(Shortest Job First) 스케줄링... 6 3) 우선순위 (Priority) 스케줄링... 7 4) 라운드로빈 (Round-Robin) 스케줄링... 8 5) SRT(Shortest Remaining Time) 스케줄링... 8 6) 다단계큐 (Multilevel Queue) 스케줄링... 9 7) 다단계피드백큐 (Multilevel Feedback Queue) 스케줄링... 9 8) HRN(High Response ratio Next) 스케줄링... 9 9. 스레드 (Thread)... 10 요약... 13
I. 프로세스와스레드관리 1. 개요 1) 중앙처리장치 (CPU) - 컴퓨터에서중앙처리장치 (CPU) 는컴퓨터자원중가장중요한자원이다. 2) 중앙처리장치스케줄링 (CPU Scheduling) - 프로세스스케줄링 (Process Scheduling) - 사용자로부터의뢰받은작업을처리하기위해프로세스들에게중앙처리장치또는프로세서들을할당하기위한정책을설정하는것이다. - 준비완료 (ready) 상태에있는프로세스들중어느것을중앙처리장치에할당시킬것인가를결정하는문제를취급하는것 - 중앙처리장치효율및처리율 (throughput) 의최대화와반환시간 (turnaround time) 의최소화에그목적을두고있다. 2. 프로세스관리 1) 프로세스의정의 - 실행 (executing, running) 중인프로그램 - PCB(Process Control block) 를지닌프로그램 - 프로그램카운터 (program counter) 를지닌프로그램 - 능동적개체 (entity) 로, 순차적으로수행하는프로그램 - 일반적으로하나의프로세스는 CPU가수행하는작업단위이다. 2) 프로세스의기능 - 사용자프로세스와시스템프로세스의생성과삭제 - 프로세스의일시중지와재수행 - 프로세스스케줄링 - 프로세스의동기화 - 프로세스간통신 - 교착상태처리 1
3. 프로세스구성요소 저장영역 코드영역 데이터영역 내용 - 프로그램코드자체 - 프로그램실행전주기억장치에 CPU 가해석할수있는바이너리코드상태로저장 - 프로그램의전역변수나정적변수의할당을위해존재 힙영역 동적할당을위해저장되는곳 스택영역 지역 (local) 변수할당과함수호출시전달되는인수 (argument) 값이저장되는곳 4. 프로세스의상태 1) 실행상태 (running) - 프로세스가중앙처리장치를차지하고있는상태 2) 준비완료상태 (ready) - 중앙처리장치가사용가능하게될때그것을할당받을수있는상태 3) 대기상태 (block) - 프로세스가중앙처리장치를차지하고처리하다가입출력처리등을하게되면중앙처리장치를양도하고입출력처리가완료될때까지기다리고있는상태
1 작업이시스템에제시되었을때스풀러에의해디스크에수록되어보류상태가됨, 시행될프로세스로만들어준비완료리스트 ( 큐 ) 의가장뒤에삽입된다. 2 프로세스스케줄러는준비완료상태에있는여러프로세스중실행될프로세스를선정하여중앙처리장치를할당하며, 그프로세스는준비완료상태에서실행상태로변환된다.( 디스패치 : Dispatch) 3 프로세스가할당시간 (time quantum) 이지나도록계속중앙처리장치를차지해야할경우, 그프로세스로하여금중앙처리장치를일단포기하게함으로써프로세스는준비완료상태로전환이일어난다. 이때프로세스스케줄러는준비완료리스트 ( 큐 ) 에서다시중앙처리장치를사용할프로세스를선정하여할당시간을배정한후그프로세스를실행한다. 4 실행상태의프로세스가할당시간을초과하기전에입출력이발생하면중앙처리장치를양도하고입출력이완료될때까지대기상태로변환된다 (block) 5 입출력처리가완료되면대기상태의프로세스에게입출력처리완료를알려준비완료상태로전환시켜야한다 (wakeup). * 프로세스의상태에대한조사와통보는트래픽제어기 (traffic controller) 가담당 - 디스패치 (dispatch): 준비완료상태 -> 실행상태 - timer runout: 실행상태 -> 준비완료상태 - block: 실행상태 -> 대기상태 - wakeup: 대기상태 -> 준비완료상태 5. 프로세스제어블록 (PCB) - 모든프로세스는각기고유의 PCB 를갖게된다. 1) 정의 - PCB 내용의변경은프로세스의상태변화가일어난경우트래픽제어기에의하여행 해진다. - 프로세스에관한모든정보를가지고있는데이터베이스 2) PCB 내용 - 프로세스의현재상태 ( 실행, 준비완료, 대기등 ) - 프로세스의고유이름 (identifier) - 프로세스의우선순위 - 프로세스가적재된기억장치의주소를가지는포인터 - 할당된자원 ( 장치등 ) 을가리키는포인터 - 중앙처리장치의각종레지스터상태를저장하기위한공간 6. 프로세스생성 - 새로운프로그램을생성시키는프로그램을부모프로세스 (parent process) 라하고, 생 성된프로그램은자식프로세스 (child process) 라한다.
- 즉, 부모프로세스가 fork() 명령어를실행하게되면부모와똑같은자식프로세스가생성된다. 7. 프로세스스케줄링 1) 스케줄링의목적및기준 (1) 목적 1 2 3 4 5 6 7 8 9 10 공정성응답시간의최소화예측가능오버헤드 (overhead) 의최소화자원사용의균형유지실행의무한한지연을피할것우선순위제의실시주요자원들을차지하고있는프로세스에게우선권을부여좀더바람직한동작을보이는프로세스에게더좋은서비스를제공과다한부하를감소 (2) 기준 1 입출력위주의프로세스인가? 2 연산위주의프로세스인가 3 프로세스가일괄처리형인가대화형인가? 4 긴급한응답이요구되는가? 5 프로세스의우선순위 6 프로세스가페이지부재를얼마나자주발생시키는가? 7 높은우선순위를지니는프로세스에의해서얼마나자주프로세스가선점 (preempted) 되는가? 8 프로세스가받은실행시간은얼마나되는가? 9 프로세스가완전히처리되는데필요한시간은얼마나더요구되는가? 2) 단계별분류 (1) 상위단계스케줄링 (highlevel scheduling) - 작업 (job) 스케줄링이라고도불림
- 어떤작업에게시스템의자원들을차지할수있도록할것인가를결정 (2) 중간단계스케줄링 (intermediate level scheduling) - 짧은순간에프로세스들에대한일시적인활동의중단및재개를수행 (3) 하위단계스케줄링 (low level scheduling) - 어떤준비완료프로세스 (ready process) 에게중앙처리장치를할당할것인가를결정 3) 방법 환경별분류 (1) 선점 / 비선점 (preemptive/non-preemptive) 스케줄링 1 비선점스케줄링 - 하나의프로세스에중앙처리장치가할당되면그프로세스의수행이끝날때까지중앙처 리장치는그프로세스로부터빠져나올수없다. 2 선점스케줄링 - 하나의프로세스가중앙처리장치를차지하고있을때다른프로세스가현재수행중인프로세스를중지시키고자신이중앙처리장치를차지할수있다. (2) 우선순위 (priority) 스케줄링 - 각프로세스에게우선순위를부여하여우선순위가높은순서대로처리하는방법 1 정적우선순위 (static priority) 기법 - 상대적으로오버헤드는적으나, 주위여건의변화에적응하지않고우선순위를바꾸지 않는다. 2 동적우선순위 (dynamic priority) 기법 - 필요에따라우선순위재구성 (3) 기한부 (deadline) 스케줄링 - 작업들이명시된시간이나기한내에완료되도록계획 - 실시간시스템에는두가지종류 경성실시간시스템 (hard real time system) 정한시간내에완료할수있도록해주는강한형태의실시간시스템 연성실시간시스템 (soft real time system) 시간적제한이다소약한형태의실시간시스템 - 실시간스케줄링의두가지방식 정적 (static) 스케줄링방식
시스템에의해실행되는태스크집합이미리정의되어있는경우 주기적인연성실시간태스크집합에유용 동적 (dynamic) 스케줄링방식 태스크의발생시간이나특성을미리예측할수없는경우에유용 보장된주기의시간내에서비스를보장받기위해서는경성실시간스케줄링을사용 - RM(Rate Monotonic) 알고리즘 대표적인정적스케줄링방식 태스크주기가짧을수록더높은우선순위를부여 - EDF(Earliest-Deadline First) 알고리즘 대표적인동적스케줄링방식 임계시간이가장근접한태스크를가장먼저수행하는방식 (4) 다중프로세서 (Multiple Processor) 스케줄링 1 2 3 4 프로세서들의형태는동질시스템또는이질시스템이질시스템의경우각프로세서는자신의큐가있으며자신의스케줄링알고리즘프로세서들이동질일경우부하공유 (load sharing) 두가지스케줄링방식 i. 각프로세서가스스로스케줄링하며, 공동준비큐를조사하여실행할프로 세스를선택 ii. 한프로세서가다른프로세서를위한스케줄러로서지정되어주종구조 (master slave structure) 를구성 8. 프로세스스케줄링알고리즘 1) FCFS(First Come First Served) 스케줄링 * - 가장간단한스케줄링방식 - 비선점스케줄링방법 - 프로세스들은대기큐에도착한순서에따라중앙처리장치를할당 - 호위효과 (convoy effect) 첫번째프로세스가끝날때까지매우긴시간을기다리게되는것 2) SJF(Shortest Job First) 스케줄링
- 프로세스중에서수행시간이가장짧은것을먼저수행하는비선점스케줄링방식 3) 우선순위 (Priority) 스케줄링 - 각프로세스에게주어지며, 중앙처리장치는가장높은우선순위를가진프로세스로할당 - 무한대기 (indefinite blocking) 또는기아현상 (starvation) 낮은우선순위의프로세스들이중앙처리장치를무한히대기하게하는경우 - 에이징 (Aging) 낮은우선순위의프로세스들의무한대기문제에대한해결책 오랫동안시스템에서대기하는프로세스들의우선순위를점진적으로증가시키는방법
4) 라운드로빈 (Round-Robin) 스케줄링 - 시분할시스템을위하여고안된선점스케줄링방식 - 각프로세스는같은크기의중앙처리장치시간을할당받음 - 할당시간 (time quantum) 의크기는보통 10에서 100ms 사이 할당시간이너무크면 FCFS 방식과같은형식이된다. 할당시간이너무적으면 문맥교환을위한오버헤드가무시못할요소가되어결과적으로대부분의시간이중앙처리장치를분배하는데소모 Processor sharing 5) SRT(Shortest Remaining Time) 스케줄링 - Shortest-Remaining-Time-First(SRTF) - Preemptive SJF - SJF 기법에선점방식을도입한방법 - 시분할시스템에서유용 - 새로도착한프로세스를포함하여처리가완료되는데가장짧은시간이소요된다고판단되는프로세스를먼저수행
6) 다단계큐 (Multilevel Queue) 스케줄링 - 작업들을여러그룹으로나누어여러개의큐를이용하는기법 - 전면작업프로세스들은후면작업프로세스들보다도높은우선순위를갖는다. - 후면작업큐가선입선출알고리즘에의해스케줄되는반면전면작업큐는라운드로빈알고리즘에의해스케줄될수있다. - 큐별로스케줄링 - 전면작업큐에는자신의프로세스들사이에서라운드로빈스케줄링을위해중앙처리장치시간의 80% - 후면작업큐는자신의프로세스들을선입선처리방식으로중앙처리장치시간의 20% 7) 다단계피드백큐 (Multilevel Feedback Queue) 스케줄링 - 대부분의다단계피드백체계에서는프로세스가하위단계의큐로옮겨갈수록주어진할당시간은점차크게설정 8) HRN(High Response ratio Next) 스케줄링
- SJF의약점, 특히긴작업과짧은작업간의지나친불평등을어느정도보완한기법 - 일단한작업이중앙처리장치를차지하면그작업은완성될때까지실행하며, 대기시간이고려되어긴작업과짧은작업간의불평등을어느정도완화 - 시스템응답시간값이클수록우선순위가높아진다. 9. 스레드 (Thread) - 다중쓰레드를사용하는유닉스의경우 스레드는각각독립적으로실행할수있고, 각쓰레드의실행순서는시그널이나동기화방법을통해서제어 - 특성 각스레드는서로독립적 스레드의실행 / 종료순서는예측할수없음 스레드들은수행을위해스케줄되고결과들은프로세스에게전달 프로그램에있는쓰레드의수는다른쓰레드에게알려지지않음 쓰레드는프로그램의외부에서는보이지않음
쓰레드는서로독립적이지만, 한쓰레드가취한행동은프로세스에있는다른쓰레드에영향을미침 쓰레드는프로세스의일부분이기때문에프로세스의자원들을공유하지만그자신의처리시간과스택, 레지스터들이할당 한프로세스가 exit() 시스템콜을통해종료되면, 모든스레들도종료하게된다. - 다중쓰레딩
다수의쓰레드를이용하여하나의프로그램을동시에처리하는것 하나의프로세스자체에다수의실행단위들이존재하여작업의수행에필요한자원들을공유하기때문에자원의생성및관리가중복되는것을최소화 중량프로세스 (HWP: Heavy Weight Process) 는하나의쓰레드를가진프로세스 경량프로세스 (LWP: Light Weight Process) 는프로세스내에두개이상의쓰레드를포함하고있을경우 KLT(Kernel-level threads) 방법 ULT(User-level threads) 방법
요약 1 프로세스스케줄링 - 어떤프로세스에언제어떠한방법으로중앙처리장치를할당할것인가에대한정책을 수립하는것 2 프로세스 - PCB 를가지는실행중의프로그램 - 하나의프로세스가생성되어소멸되기까지여러가지의상태전이를거친다. 3 프로세스의상태 - 중앙처리장치를차지하고있는실행상태 - 모든작업준비를마치고중앙처리장치를기다리고있는준비완료상태 - 어떤사건의발생을기다리는대기상태 4 PCB - 프로세스에관한모든정보를가지고있는데이터베이스 - 프로세스의생성과함께만들어진다. 5 중앙처리장치스케줄링의세단계 i. 상위단계의스케줄링 작업스케줄링은어떤작업이그시스템에들어올것인가를결정 ii. 중간단계의스케줄링 어떤프로세스에게중앙처리장치를부여할것인가 시스템부하의변동에대응하여어떤프로세스를일시중단할것인가를결정 iii. 하위단계의스케줄링 디스패칭 (dispatching) 어떤준비완료 (ready) 프로세스가다음차례에중앙처리장치를차지할것인가를결정 6 스케줄링기법만족조건 i. 모든프로세스에게 CPU 를공정하게할당되도록한다. ii. 단위시간당처리되는양을최대화 iii. 빠른시간내에응답을받을수있는대화식사용자들의수를최대로한다. iv. 예측이가능해야한다. v. 오버헤드를최소로하고자원사용의균형을이루어야한다.
vi. 응답시간과자원의활용간에균형을이루어야한다. vii. 무한지연을방지해야한다. 7 스케줄링기법의고려사항 i. 입출력위주인가? / 연산위주인가? ii. 일괄처리인가? / 대화식인가? iii. 얼마나빠른응답이요구되는가? iv. 높은우선순위를가진프로세스에의해서낮은순위를가진프로세스가얼마나빈번히선점 되는가? v. 각프로세스의대기시간은얼마인가? 8 vi. vii. 각프로세스의현재까지의수행시간및각프로세스를끝내는데필요한예측되는총시간의양은얼마나되는가를고려프로세스의우선순위, 페이지부재 (page fault) 를일으키는비율 선점방식 / 비선점방식스케줄링 i. 선점스케줄링 프로세스들이빠른응답시간을가져야하는다중프로그래밍시스템에서유용 실시간시스템과시분할시스템에서중요 시간간격타이머 (interval timer) 또는인터럽트클럭 (interrupt clock) 중요 9 우선순위스케줄링 - 부여된순위에따라프로세스를처리 i. 정적우선순위 - 프로세스수행중변하지않는우선순위 ii. 동적우선순위 - 시스템조건의변화에따라순위가바뀐다. 10 기한부스케줄링 - 프로세스들이일정한시간내에완료하도록설계 11 FCFS - 대표적인비선점스케줄링방식 - 프로세스들이도착한시간에따라준비완료리스트 (ready list) 에있다가차례대로디스 패치된다.
- 일괄처리 (batch) 시스템에서많이사용하는작업스케줄링방법 - 대화식사용자들에게빠른응답시간을보장해주지못하는단점을갖고있다. 12 SJF - 비선점스케줄링방식 - 대기하고있는작업중에서수행시간이가장짧다고판정되는프로세스를먼저수행 - 프로세스가수행될시간을사전에예측하기가어려움 13 라운드로빈스케줄링 - FCFS 에선점방식을도입한변형된방법 - 타임슬라이스또는할당시간이라고하는제한된시간동안만중앙처리장치가주어진다. - 대화식사용자들에게적당한응답시간을보장한다. 14 SRT - SJF 기법의선점변형 - 수행중인프로세스가처리시간이더짧다고판단되는새로운프로세스에의해선점된다. - SRT는 SJF보다오버헤드가크지만새로도착한짧은작업이기다리는평균대기시간을감소시키며, 긴작업은 SJF에서보다더오래지연될수있다. 15 다단계큐스케줄링알고리즘 - 작업들을여러그룹으로나누어여러개의큐를이용하는기법 - 전면작업 ( 대화식 ) 프로세스들과후면작업 ( 일괄처리 ) 프로세스들로나눈다. 두가지유형의프로세스는서로다른응답시간을요구하기때문에상이한스케줄링이필요하다. 전면작업프로세스들은후면작업프로세스들보다도높은우선순위를갖는다. 16 다단계피드백큐기법 - 가장복잡한스케줄링기법 - 선전프로세스스케줄링방식으로변화가심한작업들이섞인시스템에서특히유리하다. 17 다단계피드백큐잉기법 * - 시스템의동적변환에적응할수있는적응 (adaptive) 기법의좋은예이다. 18 HRN 스케줄링
- SJF의약점인긴작업과짧은작업간의지나친불평등을보완한기법 - 한작업이중앙처리장치를차지하면그작업은완성될때까지실행 - 짧은작업일경우라도대기시간이큰작업은우선순위가높아짐 19 쓰레드 - 서로독립적인일들을불필요하게순차적으로수행하는사실을개선하기위해프로세스보다작고독립적으로스케줄링이가능한개념 20 중량프로세스 (HWP: Heavy Weight Process) - 하나의스레드를가진프로세스 - 프로세스내에스레드가없다면프로세스는수행될수없으며스레드는프로세스내에필히존재하여야한다. - 각각의쓰레드는자신의레지스터와스택을가진다. - 쓰레드간 CPU를교환하게하여쓰레드생성을경제적으로해준다. - 쓰레드를블로킹하고다른쓰레드로교환하는것은서버가많은요청들을효과적으로다루는문제에합리적인해결방법이다. 21 경량프로세스 (LWP: Light Weight Process) - 프로세스내에두개이상의스레드를포함하고있을경우그각각을말한다. - 그것들은같은프로그램코드 ( 텍스트 ), 데이터, 시스템자원들을이용 - 프로그램카운터, 레지스터들과스택을갖는다. - 단일프로세서상의메모리나다중프로세서상의단일공유메모리에서실행된다.