Devvoo

앞으로 포스팅은 velog에…
https://velog.io/@root-devvoo/posts

CPU Scheduling (1), (2)

🔊 이화여자대학교 반효경 교수님의 KOCW 2014년 1학기 운영체제 강의를 들으며 정리한 노트입니다.
      캡쳐한 이미지 중 따로 출처 명시를 하지 않은 이미지 또한 반효경 교수님 강의 자료에 있음을 밝힙니다.

CPU and I/O Bursts in Program Execution

image

프로그램이 실행이 되면 어떤 프로그램이든 간에 위와 같은 path를 실행하면서 쭉 진행이 된다.

load store, add store 이런 것들이 CPU에서 instruction을 실행하는 기계어들이다.
이것을 실행한다는 것은 Running 한다는 것이다.
CPU를 잡고 Running을 하다가 또 중간에 파일에서 어떤 내용을 읽어온다거나 하는 오래 걸리는 작업 이런 부분이 보통 프로그램 안에 포함된다. (이미 나왔던 내용)

어쨋든 프로그램의 path는 CPU만 연속적으로 쓰는 단계와 I/O를 하는 단계가 이렇게 번갈아가면서 실행이 되는 것

이런식으로 CPU만 연속적으로 쓰면서 instruction을 실행하는 일련의 단계를 CPU burst라고 부르고,
I/O를 실행하고 있는 단계를 I/O burst라고 부른다.

즉, 어떤 프로그램이든 프로그램이 실행된다는 거는 CPU burst와 I/O burst를 반복하며 실행이 된다. 이렇게 말할 수 있다.

단, 프로그램의 종류에 따라서 CPU burst와 I/O burst가 굉장히 빈번하게 있는 프로그램이 있고, 또 CPU burst만 아주 진득하게 나오다가 I/O burst가 한번 나오고 이런 프로그램도 있을 수가 있다.
(주로 사람이 Interaction을 하는 프로그램이 위 이미지 같이 중간중간에 CPU, I/O가 많이 끼어드는 프로그램이다. 왜냐하면, CPU에서 뭔가 작업을 하고 화면에 뭔가를 출력해주고, 그 다음에 사람이 키보드 입력을 하고 그러면 다시 또 CPU가 뭔가를 실행하고, 그다음 Execution이 됐으면 그 결과를 화면에 보여주고, 사람이 반응을 하고… 이런 Interactive한 job들이 이렇게 CPU burst와 I/O burst가 자주 나오게 되므로)

즉, I/O가 중간에 자주 끼어든다 이렇게 보면 된다.

CPU-burst Time의 분포

image
컴퓨터 안에서 돌아가는 프로그램들의 CPU burst time을 그래프로 찍어본 것이다.
(CPU burst가 아주 짧은 경우부터 CPU burst가 아주 긴 경우까지를 찍어본 것)
그 빈도가 어떤지를 봤더니 CPU burst가 아주 짧은(중간에 I/O가 많이 끼어드는 그런) 경우가 굉장히 많았다는 것이고, CPU burst가 아주 긴 I/O작업 없이 CPU만 진득하게 쓰는 경우는 굉장히 빈도가 낮았다는 것이다.
이런식으로 CPU를 짧게 쓰고 중간에 I/O가 끼어드는 이런 종류의 작업을 I/O bound job이라고 부르고, CPU만 아주 굉장히 오랫동안 쓰는 작업을 CPU bound job이라고 부른다.

※ 여러 종류의 job(=process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다

  • Interactive job에게 적절한 response 제공 요망
  • CPU와 I/O 장치 등 시스템 자원을 골고루 효율적으로 사용

컴퓨터 안에는 똑같은 종류의 프로그램들만 있는게 아니라 CPU bound job도 있고, I/O bound job도 있는 등 이런 것들이 섞여있기 때문에 CPU 스케줄링이라는 것이 필요하다는 얘기.

위 그래프를 통해서 CPU bound job이 CPU를 많이 쓰고, I/O bound job은 CPU를 많이 쓴다기 보다는 CPU를 짧게 쓰는데 빈도가 잦은 것이라고 해석할 수 있다.

job의 종류에는 이런 것들이 있고, CPU를 공평하게 주는 것도 좋지만 가능하면 사람하고 Interaction을 하는 이러한 I/O bound job한테 CPU를 더 우선적으로 주는게 필요하다는게 CPU 스케줄링의 중요한 역할 중 하나

즉, 공평한 것보다도 효율성이 중요할 것이고, 또 I/O bound job같은 Interactive한 job이 너무 오래 기다리지 않게 하는 것, 그게 CPU 스케줄링의 중요한 필요성이다.

프로세스의 특성 분류

  • 프로세스는 그 특성에 따라 다음 두 가지로 나눔
    • I/O-bound process
      • CPU를 잡고 계산하는 시간보다 I/O에 많은 시간이 필요한 job
      • (many short CPU bursts)
    • CPU-bound process
      • 계산 위주의 job
      • (few very long CPU bursts)

CPU Scheduler & Dispatcher

  • CPU Scheduler

    누구한테 CPU를 줄지 결정하는 친구
    운영체제 안에서 CPU 스케줄링을 하는 코드 부분을 CPU Scheduler라고 말함.

    • Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다

  • Dispatcher

    (CPU를 누구한테 줄지를 결정했으면) 그 친구한테 CPU를 넘겨주는 역할을 하는 운영체제 커널 코드를 Dispatcher라고 말함.

    • CPU의 제어권을 CPU scheduler에 의해 선택된 프로세스에게 넘긴다
    • 이 과정을 context switch(문맥 교환)라고 한다

  • CPU 스케줄링이 필요한 경우는 프로세스에게 다음과 같은 상태 변화가 있는 경우이다

    이런 경우가 있겠구나 정도로 생각하면 된다

    1. Running → Blocked (예: I/O 요청하는 시스템 콜)

    2. Running → Ready (예: 할당시간만료로 timer interrupt)

    3. Blocked → Ready (예: I/O 완료 후 인터럽트)

    4. Terminate

      4번은 프로세스가 종료되서 더이상 할일이 없으니까 새로운 프로세스한테 CPU를 넘겨야 되는 경우

※ 1, 4에서의 스케줄링은 nonpreemptive(비선점형) (=강제로 빼앗지 않고 자진 반납)

1번과 4번은 CPU를 가지고 있어도 더이상 Instruction 실행이 안되서, 자진 반납하는 경우

※ All other scheduling is preemptive(선점형) (=강제로 빼앗음)
(그 외 다른 모든 스케줄링(2, 3번)은 선점형 스케줄링의 경우)

2번, 3번은 나는 CPU를 계속 쓰고 싶은데 번갈아써야되기 때문에 강제로 CPU를 빼앗기는 것이고,
또 I/O 끝난 프로세스한테 CPU를 넘겨주고 싶지 않은데 내가 우선 순위가 떨어져서 이 친구(I/O 끝난 프로세스)한테 강제로 CPU를 넘겨주고…

3번에 대해서…

I/O를 요청했던 프로세스(오래걸리는 작업을 요청한 프로세스)의 I/O 작업이 끝난 경우 그 Device Controller가 인터럽트를 걸어서 프로세스의 상태를 Ready로 바꿔줄 것이다.(CPU를 얻을 수 있는 권한을 다시 주는 것, 당장 CPU만 얻으면 그 다음 Instruction을 실행할 수 있는 그런 상황이 되는 것이다.)

근데, 이 작업에서 I/O가 끝난 친구는 원래 Ready상태로만 보내지 I/O가 끝났다고 해서 그 친구한테 바로 CPU는 주지 않는다고 보통 지금까지 설명했었다.
I/O가 끝난 작업 전에 CPU를 쓰던 다른 프로세스가 있을 것이다. 그 친구는 CPU를 본인의 할당 시간을 가지고 쓰고 있는데, 또 다른 친구의 I/O가 끝나는 바람에 인터럽트가 걸려서 운영체제가 이 친구의 상태를 Ready로 바꿔준거고 그러면, CPU는 다시 방금 전에 인터럽트 당했던 프로세스한테 넘어가는 것이 일반적이다.

그런데, 이 상황에서 I/O가 끝난 친구한테 곧바로 CPU를 넘겨야될 때도 있다.
그게 어떤 경우냐면, 여러가지 스케줄링 종류 중 우선 순위(Priority)에 기반한 스케줄링…
I/O를 하러 갔던 친구가 우선 순위가 제일 높은 프로세스다(시스템 안에서 최고로 중요한 프로세스다) 라고 하면, 앞에 인터럽트 당했던 프로세스의 시간이 남아있다 하더라도 (그건 할당 시간에 기반한 스케줄링이 아니라 절대적으로 우선 순위에 기반한 스케줄링으로써) I/O 끝난 친구한테 바로 CPU를 넘겨줘야되는 그런 스케줄링도 경우에 따라서 있기 때문에…

이제 3번 예(I/O 완료 후 인터럽트)의 상황을 이때 스케줄링이 필요할 수도 있다 이렇게 설명을 한 것임

Scheduling Criteria(스케줄링 기준)

Performance Index (= Performance Measure, 성능 척도)

  • CPU utilization (CPU 이용률)
    • Keep the CPU as busy as possible
      (CPU는 가능한 바쁘게 일을 시켜라)
    • 전체 시간 중에서 CPU가 놀지 않고, 일한 시간의 비율을 나타낸다.
  • Throughput (처리량, 산출량)
    • ’#’ of processes that complete their execution per time unit
    • 주어진 시간 동안에 몇개의 작업을 처리, 완료했는가?
  • Turnaround time (소요시간, 반환시간)
    • amount of time to execute a particular process
    • CPU를 쓰러 들어와서 다 쓰고 나갈 때까지 걸린 시간을 의미함.
      (프로세스가 시작되서 종료될 때까지의 시간이 아니고, 지금 이 프로세스가 CPU를 쓰러 들어와서 CPU를 쓰고 I/O 하러 나갈 때까지 걸린 그 총 시간을 의미한다.) → 유념해서 생각하기!
  • Waiting time (대기 시간)
    • amount of time a process has been waiting in the ready queue
    • CPU를 쓰기 위해 순수하게 ready queue에 줄서서 기다린 시간
  • Response time (응답 시간)
    • amount of time it takes from when a request was submitted until the first response is produced, not output
      (for time-sharing environment)
    • CPU 쓰겠다고 ready queue에 들어와서 처음으로 CPU를 얻기까지 걸린 시간

맨 위 2가지는 시스템 입장에서의 성능 척도

그 외 나머지는 프로그램(프로세스) 입장에서의 성능 척도
프로그램(프로세스) 입장에서의 성능 척도란? 내가 CPU를 빨리 얻어서 빨리 끝나면 좋은 것 ☞ 시간과 관련된 성능 척도

Preemptive(선점형) 스케줄링의 경우에는 CPU를 한번 얻었다고 해서 끝까지 쓰는게 아님, 얻었다가 뺏겼다가 다시 얻었다가 다시 뺏겼다가 이럴 수가 있다.
그런 경우 조금 쓰다가 CPU를 뺏겨서 맨 뒤에 줄서서 또 기다렸다가 CPU 사용하고 이런 과정들이 반복될 수 있을 것이다. 그러면, 줄서서 기다린 시간이 여러 차례 발생 할 것이다. 그 기다린 시간을 다 합친 개념이 waiting time이다.

Response time은 ready queue에 들어와서 최초의 CPU를 얻기까지 기다린 시간을 말한다.

Turnaround time은 기다린 시간, CPU 쓴 시간, 기다린 시간, 쓴 시간 다 합쳐서 들어와서 나갈 때까지 걸리는 총 시간을 말함

여기서 착각하면 안되는 것… 여기서 우리는 CPU 관점만 따지고 있는 것이기 때문에 어떤 프로그램 하나가 시작이 되서 종료될 때까지 시간들 이런 의미가 아니다!
매 CPU Burst 건건을 따져야 한다. 그러니까 CPU를 쓰러 ready queue에 들어온 것에 한해서 스케줄링 대상이 되는 것이기 때문에 그것에 대해서 기다린 시간이 얼마고, 지금 ready queue에 줄서있는 프로세스 중에서 단위 시간당 몇개를 처리했고, 그런게 관심사항이라는 것이다.

CPU 스케줄링 알고리즘들 (종류)

FCFS (First-Come First-Served)

먼저 온 고객을 먼저 서비스해주는 스케줄링 방법
(먼저 온 순서대로 처리하는 것)

  • Example:
Process Burst Time(msec)
P1 24
P2 3
P3 3
  • 프로세스의 도착 순서 P1, P2, P3
    스케줄 순서를 Gantt Chart로 나타내면 다음과 같다
image
출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ehdrjsdlzzz&logNo=220969631489
  • Waiting time for P1 = 0; P2 = 24; P3 = 27
  • Average waiting time: (0+24+27)/3 = 17

예제는 프로세스가 위와 같이 세 개가 있는데 세 개가 도착한 시점이 간발의 차로 전부 0초에 도착했는데, 아주 간발의 차이로 P1, P2, P3 순서대로 도착을 했다.

간트 차트를 보자.
x축 = 시간, CPU에 스케줄링된 프로세스를 시간 순서에 따라서 보여주고 있는 것이다.
FCFS 스케줄링에서 3개의 프로세스 중 P1이 제일 먼저 도착했기 때문에 0초에 도착하자마자 CPU를 장악해서 굉장히 긴 사용 시간인 24초 동안 CPU를 잡고 실행을 했다.
그 다음에 두번째 도착한 P2는 24초 만큼 기다렸다가 CPU를 얻게 되서 본인이 쓰고자 하는 3초만큼 CPU를 독점적으로 쓰게 되고, P2가 CPU를 놓게 되면,
세번째 프로세스(P3)는 아쉽게도 제일 늦게 도착하는 바람에 27초라는 시간을 기다리고 나서야 CPU를 얻게되는 것이다.

만약, 간발의 차이로 먼저 도착한 이 프로세스(P1)가 CPU를 쓰고자 하는 시간이 아주 긴 100만 초 정도의 시간이라고 하면 P2, P3도 빨리 도착했는데 굉장히 오래 기다려야되는 것이다.

그러면, time sharing시스템에서 interactive job의 응답 시간이 대단히 길어지기 때문에, 그래서 FCFS는 그렇게 좋은 스케줄링 방법이 아니다.

맨 마지막은 대기 시간과 평균 대기 시간을 구한 것이다.
평균 대기 시간을 보면 제일 먼저 도착한 프로세스는 기다린 시간이 없지만 뒤에 도착한 프로세스들은 P1이 오래 CPU를 쓰는 바람에 기다린 시간이 상당히 커져서 평균도 커지게 된다는 것을 알 수 있다.

반면에…

프로세스의 도착 순서가 다음과 같다고 하자.
P2, P3, P1

  • The Gantt chart for the schedule is:

    image
    출처 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=ehdrjsdlzzz&logNo=220969631489
  • Waiting time for P1 = 6; P2 = 0; P3 = 3
  • Average waiting time: (6+0+3/)/3 = 3
  • Much better than previous case.
  • Convoy effect: short process behind long process

기다린 시간의 평균을 내보면 앞에 경우보다 3초로 굉장히 짧아진다.

그래서, FCFS는 앞에 어떤 프로세스가 버티고 있냐에 따라서 기다리는 시간에 상당한 영향을 미친다는 것이다.

이런식으로 긴 프로세스가 하나 도착해서 짧은 프로세스들이 지나치게 오래 기다려야 되는 현상을 Convoy effect라고 부른다.

SJF (Shortest-Job-First)

  • 각 프로세스의 다음번 CPU burst time을 가지고 스케줄링에 활용
  • CPU burst time이 가장 짧은 프로세스를 제일 먼저 스케줄
  • Two schemes:
    • Nonpreemptive
      • 일단 CPU를 잡으면 이번 CPU burst가 완료될 때까지 CPU를 선점(preemption) 당하지 않음
    • Preemptive
      • 현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 새로운 프로세스가 도착하면 CPU를 빼앗김
      • 이 방법을 Shortest-Remaining-Time-First (SRTF)이라고도 부른다
  • SJF is optimal
    • 주어진 프로세스들에 대해 minimum average waiting time을 보장

짧게 쓰는 친구들이 먼저 CPU를 쓰게 해주는 방법

SJF에도 2가지 방법으로 나눌 수 있다.
Nonpreemptive한 방법: 기다리는 프로세스 중에서 CPU를 제일 짧게 쓰는 프로세스한테 줬으면 더 짧은 프로세스가 도착하더라도 CPU를 내어놓을 때까지는 CPU 사용권을 보장해주는 방식
Preemptive한 방법: CPU를 줬다 하더라도 더 짧은 프로세스가 도착하면 CPU를 뺏어가지고, 그 친구한테 넘겨주는 방법

평균 대기 시간을 최소화하는 것은 Preemptive 버전이다.
즉, CPU를 줬더라도 더 짧은 프로세스가 도착하면 뺏어서 더 짧은 친구한테 CPU를 주게되면 전체적으로 기다리는 시간이 평균적으로 짧아진다는 뜻

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

  • SJF (non-preemptive)

    image
    출처 : https://m.blog.naver.com/klp0712/220846433292

  • Average waiting time = (0+6+3+7)/4 = 4

4개의 프로세스… 도착한 시간이 다 다르다.
그리고, CPU를 연속적으로 쓰고자 하는 시간(Burst time)이 주어져있다.

0초 시점에 도착한 프로세스가 P1 밖에 없으므로 P1이 CPU를 얻게 된다.
non-preemptive방식이기 때문에 P1은 본인이 원하는 만큼 CPU를 쓰고 반납을 하게 된다.
그 다음 7초 시점에 어떤 프로세스들이 큐에 도착해서 기다리고 있나 봤더니 P2부터 P4까지 모두 이미 도착해있다.
이중에서 CPU를 짧게 쓰는 프로세스가 어느건지를 살펴보면 P3가 1로 제일 짧기 때문에, P3가 CPU를 얻게 됨.

그 다음에는 이미 도착한 친구들 중에서 짧은 순서로 CPU를 얻게되서 평균 대기시간이 4초로 구해지게 됐다.

반면에 Preemptive버전의 SJF의 예를 한번 보자.
(프로세스 예제는 똑같다.)

Process Arrival Time Burst Time
P1 0.0 7
P2 2.0 4
P3 4.0 1
P4 5.0 4

  • SJF (preemptive)

    image
    출처 : https://m.blog.naver.com/klp0712/220846433292

  • Average waiting time = (9+1+0+2)/4 = 3

0초 시점에는 P1 혼자 도착했기 때문에 P1에게 CPU를 준다.
Preemptive버전이기 때문에 P1이 CPU를 얻었지만, 더 짧은 프로세스가 도착하면 빼앗길 수가 있다.

2초 시점이 되면 P2가 도착을 한다. P2가 CPU를 쓰고자 하는 시간은 4초,
P1은 7초를 쓰고자 했는데 2초를 이미 썼고, 아직 5초를 더 써야한다.
5초를 쓰고자 하는 P1과 4초를 쓰고자 하는 P2 중에서 P2가 더 CPU 사용시간이 짧기 때문에 P2에게 CPU를 넘겨주게 되는 것이다.

그 다음에 다시 4초 시점이 되면 P3가 도착한다.
그런데, P3는 CPU 사용 하려는 시간이 1초로 가장 짧기 때문에, 4초 시점에 P3가 CPU를 얻고 1초를 쓰고…

그리고 나서, 5초 시점이 되면 4개의 프로세스가 모두 다 도착한 상황.
P3는 이미 다 쓰고 나갔기 때문에, P1, P2, P4 중에서 현재 추가로 써야될 CPU 시간이 짧은 프로세스한테 CPU가 넘어가게 되는 것이다.

이런식으로해서 CPU 사용 스케줄링 결과를 쭉 나열하고, 이 4개의 프로세스에 CPU 대기시간의 평균을 내보면 3초가 나온다.
앞에서 나왔던 non-preemptive버전의 4초보다 더 짧은 대기 시간이 얻어지는 걸 알 수 있다.

CPU 스케줄링이 언제 이루어지는가를 살펴봤더니,
non-preemptive버전인 경우에는 CPU를 다 쓰고 나가는 시점에 스케줄링을 할지 안할지 결정을 하게 되는데…
거기에 비해서 Preemptive버전은 새로운 프로세스가 도착하면 언제든지 스케줄링이 이루어질 수가 있는 그런 차이가 있다.

그러면 CPU 스케줄링에서 SJF를 쓰면 더 좋겠구나 생각할 수 있는데, 사실은 이 알고리즘은 2가지 문제점이 있다.

SJF의 2가지 문제점

  1. Starvation(기아 현상)
    SJF는 극단적으로 CPU 사용이 짧은 job을 선호한다. 그래서 CPU 사용이 긴 프로세스는 영원히 서비스를 못받을 수도 있다.

  2. CPU 사용시간을 미리 알 수 없다.
    프로그램이 실행이 되다보면 input을 받아서 실행되기도 하고, 조건문(if문)을 만족하냐, 안하냐 그때그때 상황에 따라서 branch가 일어나고, 또 user input 이런 것들이 있기 때문에… 매번 CPU를 쓰러 들어와서 얼마나 쓰고 나갈지를 CPU burst 시점에 미리 알 수가 없다는게 문제라는 말.

    (그러면 정말 사용할 수가 없는거냐? 꼭 그렇진 않다.
    우리가 CPU 사용시간을 미리 알 수는 없지만, 추정은 할 수가 있다.
    프로그램의 종류에 따라서 사람하고 인터랙션을 하는 프로그램들은 CPU burst들이 대개 짧게 나타나고, 과학 계산 응용 프로그램 같은건 CPU 사용시간이 굉장히 긴.. 이러한 특징들이 있기 때문에, 과거 CPU 사용 흔적을 통해서 과거에 CPU를 얼마나 썼는가? 예측해서 이번에 이 친구가 CPU를 얼마나 쓸지 예측하면 된다는 얘기다. (물론 정확하진 않겠지만 대개 프로그램들이 비슷한 패턴을 나타내기 때문에 그러한 예측이 가능 하다는 것))

    다음 CPU Burst Time의 예측
    image

    위에서 말했듯이 과거의 CPU burst time을 이용해서 이번에 CPU burst time이 얼마가 될지를 추정할 수 있는 방법이 있는데 주로 exponential averaging 방법이라는 것을 많이 사용하게 된다.

    (위 이미지)

    1번 t는 실제 CPU 사용 시간, (tn이 붙으면)n번째 실제 CPU 사용 시간
    2번 𝛕(타우)는 CPU 사용을 예측한 시간, (𝛕n+1하면)n+1번째 CPU 사용 시간의 예측치를 나타내는 것
    지금 n+1번째 CPU를 사용하고자 한다면 t1부터 tn까지는 이미 주어져 있을 거고(과거에 CPU 사용 시간이 얼만지.. n개는 주어져 있는 상황에서), n+1번째 CPU 사용 시간을 예측해야되는 상황이다.

    그래서 예측하는 시간은 4번과 같이 주어진다.
    n+1번째 CPU 사용 예측 시간 = n번째 실제 CPU 사용 시간(tn)하고, n번째 예측했던 CPU 사용 시간(𝛕n)을 일정 비율(α, (1-α))씩 곱해서 더해주게 되는 것이다.

    3번을 보면,
    α(알파)라는 상수가 0과 1사이의 값이다.

    그래서, 4번을 다시보자
    α하고, (1-α) 이 두개를 더하면 1이 된다.(예를 들어, α: 0.7이면 (1-α): 0.3, α: 0.9면, (1-α): 0.1 이렇기 때문에 이 두 가지를 일정 비율씩 반영한다는 의미가 되겠다.)
    그래서 이 식을 이용해서

    Exponential Averaging
    image (1)

    위 이미지 3번째 첫째줄과 같은 점화식으로 쭉 풀게되면 𝛕(타우)로 주어진 예측값들은 사라지고, t로 주어지는 실제 CPU 사용시간만 쭉 남아서 tn, tn-1, tn-2 해가지고, 결국엔 예측한 값은 최초에 예측한 𝛕0(타우제로)만 남게된다.

    그러면 이 식에서 맨 앞에 tn에 대한 계수는 α(알파)가 있고, 그 다음에 tn-1에 대한 계수는 α(알파)에다가 (1-α)를 곱한게 앞에 붙게 되고…
    뒤로 가면, (1-α)가 접접 더 곱해지게 된다.
    근데, α(알파)하고 (1-α)는 둘다 1보다 작은 값이기 때문에, 1보다 작은 값을 곱하면 점점 더 값이 작아질 것이다.

    이 얘기는 뭐냐하면,
    다음번 CPU 사용 시간(𝛕n+1)을 예측하는데 있어서 직전의 CPU 사용 시간(𝛕n)을 α만큼 반영하고, 그거보다 하나 이전의 CPU 사용 시간은 그거보다 좀 적게 반영하고, 그거보다 더 이전의 실제 CPU 사용 시간은 더 적게 반영하고…
    이런식으로, 현재를 기준으로 최근의 과거는 좀 더 가중치를 높게 반영하고, 오래 전의 것은 좀 더 가중치를 낮게 반영한 그런 결과가 얻어지게 된다는 것이다.

    (위 이미지 α = 0, α = 1인 경우는 양쪽 극단적인 경우니까 참고로 알아두면 되겠다.)

    어쨋든 그래서, 이번에 CPU를 얼마나 사용할지 정확하게 알 수는 없지만 과거의 값을 통해서 예측을 하게 되고, 그 예측한 값을 토대로 예측치가 제일 적은 프로세스한테 CPU를 주는 그런 SJF로 구현을 할 수가 있을 것이다.

Priority Scheduling(우선 순위 스케줄링)

우선 순위가 제일 높은 프로세스에게 CPU를 주겠다.

  • A priority number (integer) is associated with each process
    (우선 순위를 나타내는 숫자가 각 프로세스에게 주어진다)
  • highest priority를 가진 프로세스에게 CPU 할당
    (작은 정수의 숫자 = 우선 순위가 높은 프로세스) → (Linux나 일반적인 시스템)
    • Preemptive
    • Nonpreemptive
  • SJF는 일종의 priority scheduling이다
    • priority = predicted next CPU burst time
      SJF 스케줄링에서의 우선 순위 = CPU 사용 시간 숫자가 제일 적은 프로세스
  • Problem(문제점)
    • Starvation(기아 현상): low priority processes may never execute.
      우선 순위 스케줄링의 문제점: 우선 순위가 낮은 프로세스가 지나치게 오래 기다려서 경우에 따라서는 영원히 CPU를 얻지 못하는 상황도 발생할 수 있다.
  • Solution(해결방법)
    • Aging(노화): as time progresses increase the priority of the process.
      에이징 기법 도입: 아무리 우선 순위가 낮은 프로세스라 하더라도 오래 기다게되면, 우선 순위를 조금씩 높여주는 것.
      이 방법으로 Starvation을 막을 수 있다.

Round Robin (RR)

현대적인 컴퓨터 시스템에서 사용하는 CPU 스케줄링은 Round Robin에 기반하고 있다.

  • 각 프로세스는 동일한 크기의 할당 시간(time quantum)을 가짐
    (일반적으로 10-100 milliseconds).

  • 할당 시간이 지나면 프로세스는 선점(preempted)당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다

  • n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit 단위로 CPU 시간의 1/n을 얻는다.
    → 어떤 프로세스도 (n-1)q time unit 이상 기다리지 않는다.

    (n개 중에서 자기 자신을 뺀 n-1개가 q만큼 시간을 쓰고 나면 적어도 내 차례가 한번은 돌아온다.)
    (그리고, q라는 할당 시간(time quantum)을 짧게 잡아주면 CPU를 내가 쓸 수 있는 차례가 아주 빨리 돌아오게 된다.
    그래서, CPU를 아주 짧게 쓰는 프로세스는 한번의 할당 시간 만에 쓰고 그냥 나가버릴 것임… 대기를 하더라도 기다리는 시간이 짧음… 그래서 응답 시간이 빨라진다는 장점이 있다.
    CPU를 오래 쓰는 프로세스는 CPU를 q만큼 쓴 다음에 뺏기는 과정을 여러번 반복하기 때문에 기다리는 시간이 길어진다.
    즉, 기다리는 시간이 본인이 CPU를 사용하려는 시간과 비례하게 된다. ☞ 아주 재밌는 특징이다.)

  • Performance

    • q large → FCFS (First-Come First-Served)

    • q small → context switch 오버헤드가 커진다

      Round Robin에서도 양쪽 극단적인 상황을 생각해볼 수 있다.
      할당 시간(time quantum)을 아주 크게 잡으면 FCFS랑 같은 스케줄링 알고리즘이 될 것이고,
      할당 시간(time quantum)을 지나치게 잘게 잘라놓으면 계속 CPU를 얻었다 뺏겼다하는 상황이 반복되는데, 이렇게 하면 Round Robin이라는 철학 측면에서는 이상적이지만 context switch가 매우 빈번히 발생…
      이 context switch라는 것도 오버헤드이기 때문에, 할당 시간을 너무 짧게 주면 context switch 오버헤드때문에 시스템 전체의 성능이 나빠지는 문제가 생길 수 있다.

      그래서, 적당한 규모의 할당 시간(time quantum)을 주는 것이 바람직하고, 보통은 그 적당한 규모의 시간이 위에 나와있는 것처럼 10~100 milliseconds라고 알려져 있다.

초반부터 늘 설명했던 방법…
CPU를 줄 때는 그냥 주는게 아니고 할당 시간을 셋팅해서 넘겨주고, 할당 시간이 끝나면 timer interrupt가 걸려서 CPU를 빼앗기고…
이런게 전부다 Round Robin 스케줄링에 기반한 설명을 했던거고, 또 그러한 스케줄링은 당연히 Preemptive(선점형) 스케줄링이 되겠다. ((할당 시간이 끝나면)CPU를 빼앗길 수 있는거니까…)

이 Round Robin 스케줄링의 가장 좋은 점은 응답시간이 빨라진다는 것이다.
(CPU를 최초로 얻기까지 걸리는 시간이 빠르다는 것)
그리고, 누가 CPU를 오래쓸지 모르는 상황에서 굳이 예측할 필요없이 CPU를 짧게 쓰는 프로세스가 빨리 CPU를 쓰고 나갈 수 있게 해주는게 바로 Round Robin 스케줄링 방법의 중요한 장점

Example: RR with Time Quantum = 20

이 예제는 Round Robin 스케줄링에서 할당 시간이 20인 경우에 어떻게 스케줄링이 되는지 보여주는 것이다.

Process Burst Time
P1 53
P2 17
P3 68
P4 24

  • The Gantt chart is:

    image
    출처 : https://m.blog.naver.com/klp0712/220846433292

  • 일반적으로 SJF보다 average turnaround time이 길지만 response time은 더 짧다.
    (Turnaround time이나 Waiting time은 길어질 수가 있지만 최초로 CPU를 얻는데 걸리는 response time은 더 짧아진다는 것)

P2의 경우 할당 시간보다 본인의 CPU 사용 시간이 짧기 때문에 한번에 쓰고 빠져나감.
나머지 CPU를 계속 쓰고자하는 프로세스들은 계속해서 쓰고, 그러다가 본인이 쓸 만큼이 다 끝났으면 빠져나가고 이런식으로 스케줄링이 이루어지는 것

Round Robin의 특이한 경우…
예를 들어서, CPU 사용 시간이 100초인 프로그램이 여러개가 있는데, 그것을 FCFS로 처리하면 첫번째 친구가 100초 쓰고 나가고, 두번째 친구가 100초 쓰고 나가고 이런식으로 스케줄링이 될 것이다. 그러면, 기다리는 시간이 0초, 100초, 200초, 300초 이런식으로 될 것이다.
근데, Round Robin은 예를 들어서, 1초 단위로 난도질을 해가지고 돌리게 되면 CPU 사용 시간이 100초인 프로그램들이 1초씩 번갈아가면서 쓰다가 다같이 1000초가 되는 지점에 다 쓰고 동시에 빠져나가는 스케줄링이 될 수도 있을 것이다.

다시 말하자면…

Round Robin 스케줄링은 기본적으로 heterogeneous한(여러 다른 종류들로 이뤄진)…
CPU 사용 시간이 짧은 친구랑 긴 친구가 얼마나 쓸지를 알 수 없는 상황에서 마구잡이로 섞여있을 때 쓰기에 좋은 스케줄링인데, 반대로 CPU 사용 시간이 모두 동일한 프로그램들을 난도질을 해가지고 짧게 돌리게 되면 다 같은 지점에서 CPU를 다 쓰고 한꺼번에 동시에 빠져나가게 되는 상황… 오히려 그렇게 Round Robin을 하게되면…
거의 모든 프로세스들이 마지막까지 CPU를 조금씩 서비스를 받으면서 waiting time이 굉장히 길어지고, 그런 다음에 빠져나가기 때문에 그런 측면에서는 안좋을 수도 있다는 얘기.

일반적으로는 짧은 프로세스하고 긴 프로세스가 섞여있기 때문에 Round Robin이 더 효과를 발휘하게 되는 것이다.

Turnaround Time Varies With Time Quantum
다운로드
출처 : https://m.blog.naver.com/klp0712/220846433292

프로세스 4개에 CPU 사용시간이 위와 같이 주어져 있을 때
Round Robin의 Time quantum을 1초부터 7초까지 쭉 늘려나갔을 때 저 4개의 프로세스의 Average Turnaround Time이 어떻게 되는가를 구해봤더니, 들쭉날쭉하다.
그것은 위 프로그램들이 heterogeneous하기(여러 다른 종류들로 이뤄져있기) 때문에, 그런 성질이 있고…

만약에, 이 프로세스들에게 굉장히 긴… 시간이 동일한 같은 크기로 주어져있다고 하면 사실은 time quantum을 크게 하는게 각각이 빨리 빠져나갈 수 있기 때문에 Average Turnaround Time이 짧아지게 되고, time quantum을 아주 짧게 잡으면 4개가 전부다 오랫동안 조금 조금씩 서비스를 받다가 마지막에 한꺼번에 빠져나가기 때문에 Average Turnaround Time이 길어지고 이런 상황이 생길 수 있다는 것이다.

어쨋든, Round Robin 스케줄링의 좋은 점은 Turnaround Time이 아니라 Response Time이 빨라진다는 것이 중요한 장점이라는 것이다.

그 전까지는 한줄서기를 했는데, Multilevel Queue나 Multilevel Feedback Queue는 여러 줄로 CPU를 기다리는 줄서기를 하게 되는 것이다.

Multilevel Queue

image

맨 위에 줄이 가장 우선 순위가 높은 줄이 되겠고, 밑으로 갈수록 우선 순위가 낮은 줄이다.

  1. system processes(시스템 프로세스) : 시스템과 관련된 프로세스들이 기다리고 있다.
  2. interactive processes : 사람하고 인터랙션을 하는 프로세스들
  3. interactive editing processes : 2번 보다는 약간 인터랙션이 약간 떨어지는 프로세스들
  4. batch processes : CPU만 오랫동안 사용하는 job들
  5. student processes

이런식으로 줄이 정해져있고, 프로세스가 본인이 태어난 출신에 따라서 줄을 서야함… 운명에 따라서 영원히 우선 순위를 극복하지 못하는 식의 스케줄링

  • Ready queue를 여러 개로 분할

    • foreground (interactive)

    • background (batch - no human interaction)

      여기서는 두 줄로 줄서기를 하고 있다. foreground 큐에는 interactive한 job을 집어넣고, background 큐에는 batch형 job(중간에 사람과 인터랙션이 없이 CPU만 오랫동안 쓰는 프로세스)

  • 각 큐는 독립적인 스케줄링 알고리즘을 가짐

    • foreground - RR

      foreground job은 사람과 인터랙션을 하는 프로세스이기 때문에 여기선 Round Robin을 쓰는게 응답시간을 짧게 하는 방법이 됨

    • background - FCFS

      background job은 CPU만 오랫동안 사용하는 프로세스들이고, 응답시간이 빠르다고 좋을게 없으므로 중간에 CPU를 얻었다가 뺏었다가 하는 context switch 오버헤드를 줄이기 위해서, 먼저 온 순서대로 처리하는 FCFS로 하는게 효율적

    이런식으로, 줄의 특성에 맞는 Queue별 스케줄링 방법을 채택해야한다.

  • 큐에 대한 스케줄링이 필요

    • Fixed priority scheduling

      • serve all from foreground then from background
      • Possibility of starvation

      우선 순위를 강하게 적용하는 방식에서는 우선 순위 높은 줄이 비어있을 때만 낮은 줄에 있는 프로세스한테 CPU가 가는 방식을 쓸 수 있을 것이다.

      그렇게 되면, 우선 순위 높은 줄이 비어있지 않으면, 우선 순위가 낮은 줄의 프로세스는 영원히 CPU를 얻지 못하는 starvation이 발생할 수 있을 것임

    • Time slice

      • 각 큐에 CPU time을 적절한 비율로 할당
      • Eg., 80% to foreground in RR, 20% to background in FCFS

      그런 starvation을 막기 위해서 각 줄 별로 어느정도는 CPU 시간을 나누어서 주는 Time slice 방법을 생각해볼 수 있다.

      예를 들어, 전체 CPU 시간의 80%는 우선 순위가 높은 줄에다가 주고, 20%는 우선 순위가 낮은 줄에다가 주고… 이렇게 하면 아무리 우선 순위가 낮더라도 CPU를 얻을 수는 있는 스케줄링이 가능할 것이다.

신분을 영원히 극복하지 못하는 이러한 방식은 문제가 있다해서 나온게 Multilevel Feedback Queue이다.

Multilevel Feedback Queue

image

이것도 여러 줄이 있지만 Multilevel Queue와는 다르게 현대 사회처럼 약간 출신이 낮아도 중간에 다시 승격이 되기도 하고, 출신이 좋았지만 방탕하게 살면 강등이 되기도 하는… 이런 식의 줄을 왔다갔다 할 수 있는 스케줄링 방법

  • 프로세스가 다른 큐로 이동 가능

  • 에이징(aging)을 이와 같은 방식으로 구현할 수 있다

  • Multilevel-feedback-queue scheduler를 정의하는 파라미터들

    • Queue의 수
    • 각 큐의 scheduling algorithm
    • Process를 상위 큐로 보내는 기준
    • Process를 하위 큐로 내쫓는 기준
    • 프로세스가 CPU 서비스를 받으려 할 때 들어갈 큐를 결정하는 기준

    Multilevel Feedback Queue에서는…
    이런 큐를 몇개 둘거냐 하는 문제, 각 큐에서는 어떤 스케줄링을 사용할 것인가?, 우선 순위가 높은 큐에서 낮은 큐로 떨어지는 기준, 우선 순위가 낮은 큐에서 높은 큐로 승격되는 기준을 어떻게 할 것이냐?, 처음 프로세스가 들어갈 때 어느 큐로 들어갈 것이냐?
    이런 식의 여러가지 기준이 정해져야됨.

    보통은 어떤 식으로 Multilevel Feedback Queue를 운영하느냐 하면,(위 이미지 참고)
    처음 들어오는 프로세스는 우선 순위가 가장 높은 큐에다가 집어넣고, 우선 순위가 가장 높은 큐는 Round Robin의 할당 시간을 굉장히 짧게 준다.
    그리고, 밑에 큐로 갈수록 Round Robin의 할당 시간을 점점 길게 주고,
    제일 아래 큐는 FCFS 방식을 쓴다.

    이를 바탕으로, 할당 시간이 맨 위에 큐에서 끝나게 되면, 그 아래 큐로 강등이 되고, 또 그 아래 큐에서도 할당 시간 내에 다 처리가 안됐으면 더 아래 큐로 강등이 되고… 이런식으로 운영을 한다.

    그래서, CPU burst가 아주 짧은 프로세스는 도착하자마자 CPU를 얻어서 짧은 시간쓰고 바로 빠져나갈 수가 있고,
    CPU 사용 시간이 긴 프로세스는 맨 위에 큐에서 다 처리가 다 안끝나고 아래 큐로 점점 이동을 해서 할당 시간은 더 받게 되지만, 큐 간의 우선 순위에서 보통은 위에 큐가 비었을 때만 밑에 큐를 처리하는 이러한 방식을 쓰고 있다.

    제일 먼저 도착한 프로세스는 일단 얼마 기다리지 않고 CPU를 쓰게 되고, 할당 시간이 끝났지만 더 쓰고 싶어서 그 다음 CPU를 쓰려면 낮은 큐로 이동해서 위에 큐가 빌 때까지 기다려야되는 이런 식의 스케줄링이 된다는 것이다.

    그러므로, 이 방식은 CPU 사용 시간이 굉장히 짧은 프로세스한테 우선 순위를 더 많이 주고, 긴 프로세스는 점점 밑으로 쫓겨나게 해서 우선 순위를 낮춰주는 스케줄링 방식이다.

    그리고, 이 방식은 처음에 들어올 때는 누구든지 짧은 시간을 주기 때문에 CPU 사용 시간이 긴지 짧은지 예측이 필요없다.
    즉, 미리 예측도 필요 없으면서 짧은 프로세스가 더 우대를 받는 방식이 되겠다.

Example of Multilevel Feedback Queue
  • Three queues:
    • Q0 - time quantum 8 milliseconds
    • Q1 - time quantum 16 milliseconds
    • Q2 - FCFS
  • Scheduling
    • new job이 queue Q0로 들어감
    • CPU를 잡아서 할당 시간 8 milliseconds 동안 수행됨
    • 8 milliseconds 동안 다 끝내지 못했으면 queue Q1으로 내려감
    • Q1에 줄서서 기다렸다가 CPU를 잡아서 16 ms 동안 수행됨
    • 16 ms에 끝내지 못한 경우 queue Q2로 쫓겨남

지금까지 설명한 CPU 스케줄링은 CPU가 하나밖에 없는 시스템이었다.
지금부터 설명할 내용은 CPU가 여러개 있거나, 시간에 대한 Deadline 제약조건이 있거나, 쓰레드가 여러개 있거나…
이런식으로 특이한 케이스에서의 CPU 스케줄링을 말할 것이다.

Multiple-Processor Scheduling

CPU가 여러개 있는 시스템에서의 스케줄링

  • CPU가 여러 개인 경우 스케줄링은 더욱 복잡해짐
  • Homogeneous processor인 경우
    • Queue에 한줄로 세워서 각 프로세서가 알아서 꺼내가게 할 수 있다
    • 반드시 특정 프로세서에서 수행되어야 하는 프로세스가 있는 경우에는 문제가 더 복잡해짐
  • Load sharing
    • 일부 프로세서에 job이 몰리지 않도록 부하를 적절히 공유하는 메커니즘 필요
    • 별개의 큐를 두는 방법 vs 공동 큐를 사용하는 방법
      (한 줄 서기를 할 수도 있고, 각각의 CPU마다 별도의 줄을 서게 하는 방법도 있을 수 있음)
  • Symmetric Multiprocessing (SMP)
    • 각 프로세서가 각자 알아서 스케줄링 결정
      (Symmetric이라 함은 모든 CPU들이 대등한 것. 대등하기 때문에 CPU가 알아서 스케줄링을 하는 경우를 얘기함)
  • Asymmetric Multiprocessing
    • 하나의 프로세서가 시스템 데이터의 접근과 공유를 책임지고 나머지 프로세서는 거기에 따름
      (여러개의 CPU 중에 하나의 CPU가 전체적인 컨트롤을 담당하고, 나머지 CPU들은 거기에 따르는 방식)

Real-Time Scheduling

먼저 CPU를 주는게 중요한게 아니고, CPU에서 Deadline안에 처리가 끝나는 것을 보장해야 됨

  • Hard real-time systems
    • Hard real-time task는 정해진 시간 안에 반드시 끝내도록 스케줄링해야 함
      (반드시 deadline안에 보장이 되어야 하는 것)
  • Soft real-time computing
    • Soft real-time task는 일반 프로세스에 비해 높은 priority를 갖도록 해야 함
      (일반적인 time sharing 시스템에서 다른 프로세스들과 섞여서 실행되는 것, 그래서 다른 프로세스에 비해서 우선 순위만 높여줘서 CPU를 먼저 얻을 수 있게하지 deadline을 꼭 보장하지는 못함.)

보통 Real time job들이 주어져있고, 그거를 미리 스케줄링을 해서 deadline이 보장되도록 적재적소에 배치를 하는 방법을 쓰고 있다.

Thread Scheduling

프로세스 하나 안에 CPU 수행 단위가 여러개 있는 것을 쓰레드라고 설명했었음.

  • Local Scheduling

    • User level thread의 경우 사용자 수준의 thread library에 의해 어떤 thread를 스케줄 할지 결정

      OS가 하는 것이 아니고, 사용자 프로세스가 직접 어느 쓰레드한테 이번에 CPU를 줄지 결정하는 것이다.

  • Global Scheduling

    • Kernel level thread의 경우 일반 프로세스와 마찬가지로 커널의 단기 스케줄러가 어떤 thread를 스케줄할지 결정

      프로세스 스케줄링 하듯이 OS가 어떤 알고리즘에 근거해서 이번에 어떤 쓰레드에게 CPU를 줄지를 결정하는 것이다.

쓰레드를 구현하는 방식이 크게 두 종류가 있었다.
1. User level thread : 사용자 프로세스가 직접 쓰레드를 관리하고, 운영체제는 쓰레드의 존재를 모름
2. Kernel level thread : 운영체제가 쓰레드의 존재를 이미 알고 있음

이렇게 상황이 다르기 때문에 쓰레드를 스케줄링 하는 방법도 위와 같이 다르다.
User level thread의 경우는 운영체제는 쓰레드를 모르기 때문에 운영체제 입장에서는 그냥 그 프로세스한테 CPU를 줄지 안줄지를 결정하고, 그 프로세스한테 CPU가 갔을 때 프로세스 내부에서 어떤 쓰레드에게 CPU를 줄지 결정
반면에, Kernel level thread의 경우에는 어차피 운영체제가 쓰레드의 존재를 알고 있기 때문에 프로세스 스케줄링 하듯이 운영체제가 어떤 알고리즘에 근거해서 이번에 어떤 쓰레드에게 CPU를 줄지를 결정함.

아래는 어떤 알고리즘이 좋은지를 평가하는 방법에 대해서 설명

Algorithm Evaluation

  • Queueing models

    • 확률 분포로 주어지는 arrival rate와 service rate 등을 통해 각종 performance index 값을 계산

    • 굉장히 이론적인 방법 (이론가들이 주로 하는 방법)

    • image

    • 위 그림을 보자.
      보통 Queueing model에선 server라고 부르지만, 우리는 지금 CPU 스케줄링을 하고 있기 때문에 이 server = CPU

    • 프로세스들이 도착하는 도착율(arrival rate)하고, CPU의 처리 능력인 처리율(service rate)(단위 시간당 몇개 처리할 수 있는지) 이런 정보가 확률 분포로 주어질 때 복잡한 수식 계산을 한다.
      그 계산을 하고 나면 결과로 여러가지 성능 척도 결과가 나온다.

      예전에는 이런 방식을 굉장히 많이 썼었는데, 최근에는 워낙 실제 시스템에서 직접 돌려보는 방식을 더 의미있게 보기 때문에 그렇게까지 많이 사용하지는 않지만, 여전히 이론적으로는 많이 사용하는 하나의 방법이다.

  • Implementation (구현) & Measurement (성능 측정)

    • 실제 시스템에 알고리즘을 구현하여 실제 작업(workload)에 대해서 성능을 측정 비교

      실제 시스템에다가 구현을 해서 돌려보고 성능을 측정하는 것 (실측하는 방법)

      예를 들어, 리눅스라고 하면 리눅스의 원래 시스템에 내가 새로 만든 CPU 스케줄링 알고리즘을 리눅스 커널의 소스코드를 수정해서 새로운 알고리즘을 구현 한 다음에 리눅스 커널을 컴파일하면 리눅스의 실행 Binary code가 나올 것이다.
      그러면, 원래 리눅스를 설치한 컴퓨터와 내 CPU 스케줄러를 넣어서 만든 리눅스 커널을 설치한 컴퓨터가 각각 한 대씩 있을 것이다.
      거기다가 실제 프로그램 workload들을 돌려서 어느쪽이 얼마나 빨리 끝나는가를 보면 어떤 스케줄러가 좋은가를 알 수 있음.

    • 그러나, 운영체제 내부에 있는걸 고치는 것은 오래걸리고 쉬운 일이 아님

이 방법을 쓰기 어려울 때 아래 방법을 쓴다.

  • Simulation (모의 실험)

    • 알고리즘을 모의 프로그램으로 작성 후 trace를 입력으로 하여 결과 비교

      실제 프로그램에 CPU burst 패턴에 근거한 input 데이터를 갖고 시뮬레이션을 한다면 신빙성이 있을 것이다.

      실제 프로그램을 통해서 추출한 input 데이터를 trace라고 부른다.
      이런 trace는 시뮬레이션 프로그램에 input으로 들어갈 데이터
      (trace를 임의로 만들 수도 있고, 실제 프로그램을 돌리면서 뽑을 수도 있다.)

      trace만 있다면 누구나 충분히 해볼 수 있다.

맨 위로 이동하기

Leave a comment

You may also enjoy