CPU Scheduling

preemptive resource: 한 프로세스가 점유한 상태에서 다른 프로세스에게 양보할 수 있는 자원이다. cpu나 main memory(swap) 등등이 있다.
non-preemptive resource: 한번 점유하게 되면 다른 프로세스가 뺏을 수 없다. 프린터가 하나의 예이다.
process scheduling: 어느 프로세스에게 얼마나 cpu를 줄 것인가를 정한다.
batch monitor의 job: 한번 수행되면 끝날 때까지 수행돼야한다.
CPU burst size가 크면 cpu intensive한 연산이고 작으면 I/O interactive(터치 스크린과 같이)하다.

ready -> running: dispatch한다고 말한다. scheduling이라고 하지 않는다.
running -> ready: HW interrupt로 os scheduler가 개입하여 강제로 cpu를 뺏는다. preemptive.
running -> waiting: 스스로 cpu yield 함수를 호출한다. non-preemptive.
running -> terminate: non-preemptive.
waiting -> ready: preemptive.
ready로 가면 preemptive인가보다.

aging: task가 cpu를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 방법이다.
throughput: 단위 시간 내에 끝내는 process 수이다.
turnaround time: process가 수행되는 데 걸리는 시간이다.
waiting time: ready큐에서 대기하는 시간이다.
response time: 처음 request가 왔을 때부터 첫 response까지의(output이 아니라) 시간이다.

FIFO: cpu burst 단위이다. monopoly가 발생할 수 있기 때문에 maximum limit을 걸 수 있다.
SJF(Shrotest Job First): 가장 optimal하지만 task의 남은 cpu burst size를 예측할 수 없기에 이상적인 스케쥴링이다.
preemptive SJF: process 수행 중이라도 더 작은 프로세스가 들어오면 preempt한다. Shortest Running Time First(SRTF).
Round Robin: 기본적으로 FIFO이지만 time-out(time slice, time quantum)이 있어서 일정 시간이 지나면 강제로 종료당하고 FIFO의 가장 뒤로 간다. Time slice가 무한대이면 FIFO와 같아진다.

Adaptive Scheduling: work load에 따라 time slice를 바꾼다.
CPU bound process: 대부분의 시간을 cpu에 할당한다. throughput이 중요하고 긴 cpu burst를 갖는다.
I/O bound process: 대부분의 시간을 I/O에 할당한다. response time이 중요하고 짧은 cpu burst를 갖는다. 1ms run하고 I/O를 10ms 기다리는 식이다.

multi-level feedback queue(MLFQ)(exponential queue): 큐가 우선순위에 따라 여러 레벨로 있다. 높은 우선순위는 작은 TS를 갖는다. I/O bound process가 높은 우선순위이다.

Priority-based scheduling: starvation이 발생할 수 있다.
Fair Share Scheduling(Bandwidth Scheduling, Proportional Share Scheduling): 대기 중인 프로세스들에게 정해진 비율에 따라 cpu의 bandwidth를 분배한다.



댓글

댓글 쓰기

이 블로그의 인기 게시물

논문 정리 - MapReduce: Simplified Data Processing on Large Clusters

Abstract 맵리듀스는 큰 데이터 셋을 다루는 프로그래밍 모델이다 . 사용자는 map 함수를 통해서 키 / 밸류 쌍을 이용하여 intermediate key/value pair 를 만들고 reduce 함수를 통해서 그 intermediate pair 들을 같은 key 별로 합쳐준다 . 많은 일들이 이런 모델을 통해 표현될 수 있다 . 이 모델은 분산 시스템이나 병렬 시스템에 대한 경험이 부족하더라도 분산 시스템의 자원을 쉽게 사용할 수 있게 해준다 . 1. introduction 데이터가 많아지면서 reasonable time 안에 작업을 끝내기 위해 수백 혹은 수천대의 기계에 분산되어야 했다 . 이 때 어떻게 연산을 병렬화하고 , 데이터를 분산하고 , 실패 작업을 어떻게 처리할지가 이슈가 되었다 . 이런 복잡한 문제들을 해결하기 위해 병렬화의 세세한 부분들은 숨기고 fault tolerance 하며 데이터를 분산시켜주고 로드 밸런싱을 해주는 라이브러리를 통해서 연산을 맵과 리듀스로 간단히 표현하도록 했다 . 2. Programming Model 사용자가 직접 만드는 맵 함수는 입력으로 key/value pairs 를 받아서 intermediate key/value pairs 를 만든다 . 그러면 intermediate key/value pairs 에 대해서 맵리듀스 라이브러리가 같은 key 별로 value 들을 묶어서 리듀스 함수로 보내준다 . 마찬가지로 사용자가 직접 만드는 리듀스 함수는 이 데이터를 받아서 key 별로 묶인 value 들을 합쳐서 표현한다 . 리듀스 함수에 전달되는 intermediate 데이터는 iterator 의 형태로 전달되기 때문에 메모리에 다 안 들어갈 정도로 큰 데이터도 처리할 수 있다 . 예를 들어서 , 어떤 문서에 있는 각 단어들이 몇 번 나왔는지 세는 프로그램을 생각해보자 . 그렇다면 맵 함수는 입력으로 < 문서 이름 , 문서 내용 > 의...
자세한 내용 보기

논문 정리 - The Google File System

The Google File System 1. Introduction 새로운 관점 component failure 은 예외가 아니라 일반적인 상황이다 . 그래서 constant monitoring, error detection, fault tolerance, automatic recovery 가 필요하다 . 파일의 크기가 커졌다 . I/O 작업이나 block 크기 등이 고려되어야 한다 . 원래 있는 데이터에 덮어쓰는 작업보다는 새로운 데이터를 추가한다 . 따라서 appending 이 성능 최적화에 중요해졌다 . 2. Design Overview 2.1 assumptions 시스템은 잘 고장나는 저렴한 장비들로 구성되어 있다 . 시스템은 큰 파일이 있다 . 작은 파일들도 있지만 optimizing 할 때는 고려하지 않는다 . 로드는 주로 큰 스트리밍 읽기와 작은 랜덤 읽기로 구성되어 있다 . 로드는 또한 파일에 데이터를 추가하는 많은 sequential write 가 있다 . 같은 파일에 여러 사용자가 동시에 데이터를 추가하는 경우도 잘 고려해야 한다 . 빠른 반응 속도 보다는 high sustained bandwidth 가 더 중요하다 . 대부분의 타겟 애플리케이션은 데이터 뭉텅이를 빠른 시간 내에 처리하는 것을 중요하게 여긴다 . 2.2 Interface 파일은 hierarchically , 디렉토리에 정렬돼있고 path name 으로 구분된다 . 또한 GFS 는 snapshot 과 record append 기능이 있다 . snapshot 은 파일이나 디렉토리 트리를 복사한다 . record append 는 다수 클라이언트가 데이터를 하나의 파일에 동시에 추가할 수 있도록 해준다 . 각 append 의 atomicity 를 보장하면서 . 2.3 Architecture 하나의 마스터와 여러개의 chunkserver 로 구성되어 있다 . 그리고 다수의...
자세한 내용 보기

kazoo: Using zookeeper api with python

``` pip3 install kazoo ``` https://kazoo.readthedocs.io/en/latest/basic_usage.html https://kazoo.readthedocs.io/en/latest/api/client.html ### 접속 ``` from kazoo.client import KazooClient zk = KazooClient(hosts='127.0.0.1:2181') zk.start() ``` 호스트에 접속할 때 default port는 2181이다. ### 상태 Listener zookeeper의 상태가 변하는 것을 알 수 있다. ``` from kazoo.client import KazooState def my_listener(state):     if state == KazooState.LOST:         # Register somewhere that the session was lost     elif state == KazooState.SUSPENDED:         # Handle being disconnected from Zookeeper     else:         # Handle being connected/reconnected to Zookeeper zk.add_listener(my_listener) ``` LOST CONNECTED SUSPENDED 의 state를 가질 수 있다. 가능한 상태 변화 - LOST -> CONNECTED - CONNECTED -> SUSPENDED - CONNECTED -> LOST - SUSPENDED -> LOST - SUSPENDED -> CONNECTED ### CRUD - `zk.create("/my/favorite/node", b"a value")` `create(path...
자세한 내용 보기