#5 CPU SCHEDULING

 


 

* cpu and I/O Bursts in Program Execution




# cpu bursts : cpu만 실행 되는곳

  I/o bursts : I/O만 실행 되는곳


# 프로그램의 종류에 따라 cpu burts와 I/O bursts의 빈도가 달라진다.

cf> 주로 사람이 만지는 프로그램은 I/O bursts가 높아지고,

    과학 계산용 프로그램은 cpu bursts가 높다.


* cpu-bursts time의 분포

 

 


# 그래프 분석 : job의 종류가 섞여있다.

# cpu bursts가 짧은 경우(빨간색 네모) : 중간에 i/o가 많이 끼어드는 경우가 많았다. => I/O bound job

  cpu bursts가 긴 경우(파란색 네모)   : 중간에 i/o가 많이 끼어들지 않았다. => cpu bound job


!!!) 이렇듯 여러 종류의 job(=process)이 섞여 있기 때문에 cpu 스케줄링이 필요하다.

 

  - cpu 스케줄링의 중요한 역할 중에 하나는!!!

  : I/O bound job 처럼 사람하고 interaction 하는 job 에게 cpu를 우선적으로 주는것. (효율성을 위해!!)

    즉, interactive 한 job들을 오래 기다리게 하지 않는것


* 프로세스의 특성 분류

 

 


* CPU Scheduler & Dispatcher

 

 


# CPU 스케줄러 : 누구한테 CPU를 줄지를 정함.

 ???) CPU 스케줄러는 HW or SW?

     : CPU 스케줄러는 os kernel에 있는 스케줄링 해주는 code이다.


# Dispatcher : cpu를 누구한테 줄지 결정했으면, 그 친구에게 cpu를 넘겨주는 역할을 함.

  cf> 마찬가지로 kernel에 있는 code.


!!!과정))

 - 방금전에 cpu에서 돌아가던 process의 context를 save하고, 

 - 새로 cpu를 넘겨주는 process의 context를 펼쳐놓는다.

 - cpu 안에다가 register 값 세팅 해놓고,

 - 그런다음에 cpu를 넘겨준다.


# cpu 스케줄링이 필요한 경우 

 1. I/O 작업처럼 오래 걸리는 작업을 하는 경우

 2. cpu를 계속 쓰고 싶은데 timer interrupt가 발생해서 빼앗는 경우

 3. 오래 걸리는 작업이 끈낫을때 (device controller가 interrupt를 걸어서 ready상태로 만들어 줌.)

 4. 

'cs > os' 카테고리의 다른 글

#5-3. CPU SCHEDULING  (0) 2018.01.09
#5-2. CPU SCHEDULING  (1) 2018.01.08
#4. Process Management  (0) 2018.01.02
#3-3. Thread  (0) 2017.12.29
#3-2. Process  (0) 2017.12.27

#4. Process Management

 

 

* 프로세스의 생성
: 부모 프로세스가 자식 프로세스를 생성.
 cf> 생성하는 방법 : 복제 생성(메모리(code, data, stack), cpu문맥(pc)을 copy.)

 

 v. 계층구조 : 트리구조

 v. 프로세스는 자원을 필요함(실행이 되려면)
  - os로부터 받는다.
  - 부모와 자원을 공유한다.
   (공유하지 않는 모델도 있고, 일부만 공유하는 모델도 있다.)

 
  #보통 일반적인 경우는 자원을 공유하지 않고, 자식 프로세스가 생성되자마자 서로 cpu를 더 차지 하기 위한 경쟁관계가 된다.

 

 v. 수행(Excution)
  - 부모와 자식은 공존하며 수행되는 모델
  - 자식이 종료(terminate)될 때까지 부모가 기다리는(wait)모델

 

  # 부모와 자식이 공존하며 수행되는 모델이 있고, 자식을 생성하고 종료 될때까지 기다리는 모델이 두가지가 있다. 이 것들을 자세히 알아보자.

  # 메모리를 아끼기 위해 공유할수 있는거는 copy하지 않고 공유하는 효율적인것들도 있다.

 

 vv. 주소공간(address space)
  - 자식은 부모의 공간을 복사함(복제 생성)-------1단계(fork)
  - 자식은 그 공간에 새로운 프로그램을 올림------2단계(exec)

 

 vv. 유닉스의 예
  - fork() 시스템 콜이 새로운 프로세스 생성
   .부모를 그대로 복사 (os data except PID + binary)
   .주소 공간 할당

 

  - fork 다음에 이어지는 exec() 시스템 콜을 통해 새로운 프로그램을 메모리에 올림.

 

# 일단 fork()로 생성한다음에 복제해서 exec()를 사용해서 필요한거만 덮어 씌운다.

 

* 프로세스 종료

 v. 프로세스가 마지막 명령을 수행한 후 os에게 이를 알려줌(exit)
  - 자식이 부모에게 output data를 보냄(via wait).
    # 자식이 항상 부모보다 먼저 죽는다!!


  - 프로세스의 각종 자원들이 os에게 반납됨

# 자발적으로 프로세스가 종료되는것 : exit
    비 자발적으로 종료 되는것        : abort

 

 v. 부모 프로세스가 자식의 수행을 종료시킴(abort)
  - 자식이 할당 자원의 한계치를 넘어섬
  - 자식에게 할당된 task가 더 이상 필요하지 않음
  - 부모가 종료(wait)하는 경우
   . os는 부모 프로세스가 종요하는 경우 자식이 더 이상 수행되도록 두지 않는다.
   . 단계적인 종료

 

# 자식이 사치(자원한계치 이상)부리거나,

(일시키려고 자식을 생성했기 때문)할 일이 없거나,

 부모가 먼저 죽게 되는

경우에 자식을 죽인다.

 

 

* fork() 시스템 콜

 

 


# fork를 사용해서 프로세스를 만드는 코드
# fork() 빨간 부분은 시스템콜 부분이다.

 

# 문제점 : fork를 통해 복제를 할 경우 문제점
1) 복제를 해놨더니 지가 원본이라고 주장한다. 부모 프로세스를 자식 취급을 하면, 굉장히 혼란스러운 상황이 발생.
2) 부모와 똑같은 제어흐름을 따라가야 될거 같다....

해결책)) 
 1.부모와 자식을 구분을 해준다.
   어떻게?)) return value를 다르게 한다.
             자식은 0, 부모는 양수가 된다. (pid 설명.)

 2. 부모와 자식 프로세스가 다른일을 하게 해주는 system call
   : exec()

 

* exec() 시스템 콜
 : 어떤 프로그램을 완전히 새로운 프로세스로 태어나게 해주는 역할을 한다.


 

 

 

# execlp는 일종의 함수인데, 이것이 exec 시스템콜을 하게 된다.
# exec을 하게되면 fork와 달리 main 처음부터 실행을 하게 된다.

 

 

* wait()
 : 자식이 종료될때까지 기다리는 시스템 콜

 

 


ex> 리눅스 커널도 wait() 시스템콜이 사용된다. (콘솔 기다리는 거 상상하자.)


* exit()
 : 프로그램을 종료할때 실행하는 시스템 콜.

 

 

 

# 보통 자발적으로 종료될때 실행이 된다, 코드가 없어도(code에 exit()가 없어도) 마지막 코드 읽어주고 exit()가 실행됨.


* 프로세스와 관련한 시스템 콜(정리)

 

 - fork() : 부모 프로세스 복제 생성하는 것.
 - exec() : 완전히 새로운 프로그램으로 덮어 씌우는 것
 - wait() : 자식이 종료될때 까지 기다리는 것
 - exit() : 모든 자원을 반납하고 부모 프로세스한테 죽는다고 알리는 것.

 

 


* 프로세스 간 협력

 

 

 

# 프로세스는 원칙적으로 독립적이다.(부모가 자식을 죽이는것 말고는 프로세스들이 서롤 영향을 미치지 못한다.)

# process 협력: 프로세스간의 정보 교환
  정보를 교환하는 방법 => IPC

 

 

* Message Passing
 : 커널을 통해서 메시지를 passing 할수 있다.

 

# 메세지 패싱에는 또 2가지 방법이 있다.
: 상대 메시지를 받아볼 프로세스 이름을 명시 하느냐 안하느냐에 따라 2가지로 나뉨. (직접 통신 / 간접 통신)


# 2가지 방법으로 나누지만, 어쨋껀 메세지를 전달하려면 os의 kernel을 통해 전달해야 하는건 똑같다.

why?)) 프로세스 끼리는 메세지를 전달하는게 불가능 하기 때문에! 


# 간접 메시지는 아무나 꺼내갈수 있게 할수 있다! (상황에 따라 맞게 설계하도록 하자.)

 

 

* 일부 주소 공간을 공유하는 IPC
 : 아래 그림은 물리적인 공간

 

 

# 원칙적으로 process들은 독자적인 주소공간을 각자 가지고 있지만 일부 process들은 주소 공간을 공유한다.

# 공유된 주소공간은 접근을 바로 할 수 있다.

# shared 공간을 쓰려면 kernel한테 mapping(인제 shared 공간을 사용하겠다)을 해놓고, 그때부터는 사용자 프로세스끼리는 한쪽에서 쓰면 다른쪽에서 볼수있다.
 즉, shared memory 처음 하는것은 kernel의 도움을 받지만, 일단 kernel이 한번 해주면 그 이후는 가능하다. 
 
** 단, shared memory를 쓰려면 두 프로세스는 굉장히 신뢰할만한 프로세스여야 한다.

cf> 쓰레드들간의 협력은 주소공간을 같이 쓰기 때문에 유용하다.

 

 

 

'cs > os' 카테고리의 다른 글

#5-2. CPU SCHEDULING  (1) 2018.01.08
#5. CPU SCHEDULING  (0) 2018.01.04
#3-3. Thread  (0) 2017.12.29
#3-2. Process  (0) 2017.12.27
#3-1. Process  (0) 2017.12.27

https://www.acmicpc.net/problem/1759


1. 문제 이해


 모음 1개와 자음 2개 이상이 꼭 포함 된다는 것을 기억해야 합니다.


2. 접근 방법


로또 (http://sbell92.tistory.com/15?category=640303) 문제와 비슷한 방법으로 접근했습니다.


dfs를 이용해 완전 탐색을 하되, 모음과 자음일 경우를 고려해 주었습니다.



3. 문제 해결


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <algorithm>
#include <iostream>
#include <vector>
#define MAX_SIZE 20
 
using namespace std;
 
int l, c, ja, mo;
vector<char> res;
 
void dfs(vector<char>& v, int d, int cnt) {
    if (l == cnt && mo >= 1 && ja >= 2) {
        for (int i = 0; i < res.size(); i++) {
            cout << res[i];
        }
        cout << '\n';
        return;
    }
    if (l == cnt) return;        // 모음, 자음 만족 안하고 길이가 l이 될때
    if (c == d) return;            // 완전히 탐색했을때
 
    if (v[d] == 'a' || v[d] == 'e' || v[d] == 'i' || v[d] == 'o' || v[d] == 'u') {
        mo++;
    }
    else {
        ja++;
    }
 
    res.push_back(v[d]);
    dfs(v, d + 1, cnt + 1);
 
    char out = res.back();
    if (out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u') {
        mo--;
    }
    else {
        ja--;
    }
    res.pop_back();
    dfs(v, d + 1, cnt);
}
 
int main() {
    cin >> l >> c;
 
    char input;
    vector<char> v;
    for (int i = 0; i < c; i++) {
        cin >> input;
        v.push_back(input);
    }
    sort(v.begin(), v.end());
 
    dfs(v, 00);
 
    return 0;
}
cs


※ 오늘의 코드 리뷰 : 벡터가 점점 익숙해져 갑니다. ㅎㅎ

'Algorithm > solution' 카테고리의 다른 글

#14502. 연구소  (4) 2018.01.16
#1953. [모의 SW 역량테스트] 탈주범 검거  (0) 2018.01.07
#2140. 지뢰찾기  (0) 2017.12.29
#6305. 로또  (0) 2017.12.26
#1463. 1로 만들기  (0) 2017.12.24

+ Recent posts