Skip to content

Latest commit

 

History

History
345 lines (251 loc) · 21.6 KB

6장__CPU_스케줄링.md

File metadata and controls

345 lines (251 loc) · 21.6 KB
Raw

6장 CPU 스케줄링


6-1 🍂 CPU 스케줄러　yeosong

CPU 스케줄링: 비선점형 nonpreemtive 방식 / 선점형 preemtive 방식 구분하기

  1. 프로그램 printf를 실행하던 중 코드 내용 중에 출력을 하는 부분이 있어서,
    I/O 인터럽트 루틴을 따르는 동안 프로세스 printf는 blocked(봉쇄) 상태가 되었다. 이 경우의 CPU 스케줄링 방식은?

  2. 아래와 같은 프로그램의 실행을 무사히 마친 프로세스 kido가 종료되고, CPU 제어권을 잃었다. 이 경우의 CPU 스케줄링 방식은?

#include <stdio.h>
int main()
{
  printf("%s\n", "kido calm down.");
}

  1. 프로그램 푸쉬업이 실행되던 중 입출력 인터럽트가 들어와 푸쉬업은 봉쇄 상태가 되었다.
    들어왔던 입출력 인터럽트 종료 후 푸쉬업가 다시 실행될 줄 알았지만..
    최우선순위 프로세스로 설정되어 있었던 프로세스 꼬북칩으로 CPU가 이양되는 바람에
    푸쉬업은 준비 상태로 돌아가버렸다. 이 경우의 CPU 스케줄링 방식은?

  2. 작업량이 방대한 프로세스 42는 타이머 인터럽트에 걸려 준비 상태로 변경되었다. 이 경우의 CPU 스케줄링 방식은?

  3. (보너스 문제) CPU 스케줄러는 특정한 하드웨어일까요? 혹은 소프트웨어? 독립된 소프트웨어일까요?

📄 답지

CPU 스케줄링: 비선점형 nonpreemtive 방식 / 선점형 preemtive 방식 구분하기

  1. 프로그램 printf를 실행하던 중 코드 내용 중에 출력을 하는 부분이 있어서,
    I/O 인터럽트 루틴을 따르는 동안 프로세스 printf는 blocked(봉쇄) 상태가 되었다. 이 경우의 CPU 스케줄링 방식은?

프로세스가 입출력 인터럽트를 위해 CPU를 자발적으로 이양하는 것이므로 비선점형.

  1. 아래와 같은 프로그램의 실행을 무사히 마친 프로세스 kido가 종료되고, CPU 제어권을 잃었다. 이 경우의 CPU 스케줄링 방식은?
#include <stdio.h>
int main()
{
 printf("%s\n", "kido calm down.");
}

프로그램에 명시적으로 적어주지 않아도 main 함수가 리턴되는 위치에 컴파일러가 exit() 시스템 콜을 넣어줘서,
자발적으로 CPU를 반납하고 종료되는 상황이다. 그러므로 비선점형.

  1. 프로그램 푸쉬업이 실행되던 중 입출력 인터럽트가 들어와 푸쉬업은 봉쇄 상태가 되었다.
    들어왔던 입출력 인터럽트 종료 후 푸쉬업가 다시 실행될 줄 알았지만..
    최우선순위 프로세스로 설정되어 있었던 프로세스 꼬북칩으로 CPU가 이양되는 바람에
    푸쉬업은 준비 상태로 돌아가버렸다. 이 경우의 CPU 스케줄링 방식은?

최우선순위로 선점되어 있어서 이를 위해 CPU를 빼앗아 간 것이므로 선점형.

  1. 작업량이 방대한 프로세스 42는 타이머 인터럽트에 걸려 준비 상태로 변경되었다. 이 경우의 CPU 스케줄링 방식은?

시간이 선점되어 있어서 이를 지키기 위해 빼앗아 간 것이므로 선점형.

  1. (보너스 문제) CPU 스케줄러는 특정한 하드웨어일까요? 혹은 소프트웨어? 독립된 소프트웨어일까요?

운영체제 내에 있는 코드 중에 스케줄링을 어떻게 할지에 대한 내용이 들어있는 부분이 있는데 이를 CPU 스케줄러라고 부르는 것입니다.
반효경 교수님 강의중 59분쯤



6-2 🍂 디스패처 　kukim

  1. 디스패처(dispatcher)이란 무엇인가요? (주관식)

  2. 디스패치 지연시간(dispatch latency)이란 무엇인가요? (주관식)

  3. 디스패치 지연시간의 대부분은 어디에 해당될까요? (보기 선택)

보기 : 파파라치 사진찍기, 오버헤드킥, 문맥교환 오버헤드, PCB I/O,  CPU bound process
  1. 다음은 디스패처의 수행 작업 과정이다. 보기에서 괄호를 채우시오.
보기 : PC, SP, PCB, 디스패치, 찰칵찰칵, SD 카드

현재 수행중이던 프로세스의 문맥(context)을 그 프로세스의 ( )에 저장하고

새롭게 선택된 프로세스의 문맥을 ( )로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.

📄 답지

  1. 디스패처(dispatcher)이란 무엇인가요? (주관식)
    정답 : CPU 스케줄러가 어떤 프로세스에게 CPU를 할당해야 할지 결정하고나면 선택된 프로세스에게 실제로 CPU를 이양하는 작업이 필요한데 이때 새롭게 선택된 CPU를 할당, 작업 수행할 수 있도록 환경설정 하는 운영체제의 코드이다.

  2. 디스패치 지연시간(dispatch latency)이란 무엇인가요? (단답형)
    디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간

  3. 디스패치 지연시간의 대부분은 어디에 해당될까요?

보기 : 파파라치 사진찍기, 오버헤드킥, 문맥교환 오버헤드, PCB I/O,  CPU bound process

정답 : 문맥교환 오버헤드

  1. 다음은 디스패처의 수행 작업 과정이다. 괄호를 채우시오.
보기 : PC, SP, PCB, 디스패치, 찰칵찰칵, SD 카드

현재 수행중이던 프로세스의 문맥(context)을 그 프로세스의 (PCB)에 저장하고

새롭게 선택된 프로세스의 문맥을 (PCB)로부터 복원한 후 그 프로세스에게 CPU를 넘기는 과정을 수행한다.



6-3 🍂 스케줄링의 성능 평가 　gaekim

  1. 스케줄링의 성능 평가 지표는 시스템 관점의 지표와 사용자 관점의 지표로 분류할 수 있다. 시스템 관점의 지표로는 ___ ___과 ___이 있고, 사용자 관점의 지표로는 소요시간(총 처리시간), 대기시간, 응답시간 등 기다린 __과 관련된 지표들이 있다.

  2. 여러 프로세스가 CPU를 기다리고 있는 상황에서, 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 / 긴 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.

  3. 응답시간은 CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합을 뜻한다. (O / X)

  4. 일반적으로 CPU 이용률과 처리량은 최소화 / 최대화하고 소요시간, 대기시간, 응답시간은 최소화 / 최대화하는 것이 바람직하다.

📄 답지

  1. 스케줄링의 성능 평가 지표는 시스템 관점의 지표와 사용자 관점의 지표로 분류할 수 있다. 시스템 관점의 지표로는 CPU 이용률과 처리량이 있고, 사용자 관점의 지표로는 소요시간(총 처리시간), 대기시간, 응답시간 등 기다린 시간과 관련된 지표들이 있다.

    ◾ CPU 이용률: 전체 시간 중에서 CPU가 일을 한 시간의 비율
    ◾ 처리량: 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지 (=CPU 버스트를 완료한 프로세스의 개수)
    ◾ 소요시간: 프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간. 즉, 준비 큐에서 기다린 시간과 실제로 CPU를 사용한 시간의 합
    ◾ 대기시간: CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합
    ◾ 응답시간: 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간

  2. 여러 프로세스가 CPU를 기다리고 있는 상황에서, 주어진 시간에 더 많은 프로세스들이 CPU 작업을 완료하기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.

    CPU 버스트가 짧은 프로세스를 우선적으로 처리하는 것이 효율성이 더 높기 때문(더 많은 프로세스를 처리할 수 있음)

  3. 응답시간은 CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합을 뜻한다. (X)

    대기시간에 해당하는 설명이다. 한 번의 CPU 버스트 중에도 준비 큐에서 기다린 시간이 여러 번 발생할 수 있는데, 이 때 이번 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합이 대기시간에 해당한다.

    응답시간은 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간을 뜻한다.

  4. 일반적으로 CPU 이용률과 처리량은 최대화하고 소요시간, 대기시간, 응답시간은 최소화하는 것이 바람직하다.

    가능한 많은 일을 처리하고, 시간은 짧게 걸리는 것이 이익이기 때문



6-4 🍂 스케줄링 알고리즘 　mihykim

[문제0] 다음의 설명을 읽고, 보기에서 가장 적절한 스케줄링 알고리즘을 골라주세요.

<보기>
- 멀티레벨큐
- 멀티레벨 피드백큐
- 다중처리기 스케줄링
- 실시간 스케줄링
- 라운드로빈 스케줄링
- 우선순위 스케줄링
- 선입선출 스케줄링(FCFS)
- 최단작업 우선 스케줄링(SJF)
  • 0-1. 프로세스가 준비큐에 도착한 시간 순서대로 CPU를 할당하는 방식 : 　　　　　　　
  • 0-2. 현재 CPU에서 실행중인 프로세스의 남은 CPU버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗는 방식 : 　　　　　　　
  • 0-3. 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식 : 　　　　　　　
  • 0-4. 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식 : 　　　　　　　
  • 0-5. 성격이 다른 프로세스를 별도로 관리하고, 프로세스 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 여러 개로 분할해 관리하는 방식 : 　　　　　　　
  • 0-6. CPU를 기다리는 프로세스를 여러 큐에 줄세우되, 프로세스가 하나의 큐에서 다른 큐로 이동이 가능한 방식 : 　　　　　　　
  • 0-7. CPU가 여러개인 멀티프로세서 시스템에서의 CPU스케줄링 방식 : 　　　　　　　
  • 0-8. 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야할 경우에 사용하는 스케줄링 기법으로, 주로 데드라인이 얼마남지 않은 요청을 먼저 처리하는 방식 : 　　　　　　　

[문제1] 선입선출(FCFS) 스케줄링의 대표적인 단점이 있는데요

  • 1-1. 이 현상을 무엇이라고 할까요? ㅇㅇㅇ 현상
  • 1-2. 이 현상에 대해서 간단하게 설명해주세요. (1등 +10점)

[문제2] 최단작업 우선(SJF) 스케줄링에도 대표적인 단점이 있는데요

  • 2-1. 이 현상을 무엇이라고 할까요? ㅇㅇ 현상
  • 2-2. 이 현상에 대해서 간단하게 설명해주세요. (1등 +10점)
  • 2-3. '세초공주를 구하라' 게임에 접속해주세요 링크

[문제3] 우선순위 스케줄링에서는 SJF의 문제를 해결할 수 있는 기법을 사용하는데요

  • 3-1. 이 기법을 무엇이라고 할까요? ㅇㅇ 기법
  • 3-2. 이 기법에 대해서 간단하게 설명해주세요. (1등 +10점)

[문제4] 라운드로빈 스케줄링은 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식인데요

  • 4-1. 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 무엇이라고 할까요? ㅇㅇ시간 또는 (time _______)
  • 4-2. 이 시간이 경과하면 무엇을 발생시켜 해당 프로세스로부터 CPU를 회수해 준비 큐의 제일 뒤에가서 줄을 서 다음번 차례를 기다릴까요? ㅇㅇㅇ ㅇㅇㅇㅇ
  • 4-3. 할당시간을 너무 '짧게'할 경우의 문제점은 무엇인지 간단하게 설명해주세요. (1등 +15점)
  • 4-4. 할당시간을 너무 '길게'할 경우의 문제점은 무엇인지 간단하게 설명해주세요. (1등 +15점)

[문제5] 멀티레벨큐는 성격이 다른 프로세스를 별도로 관리할 수 있는 스케줄링 방식인데요

  • 5-1. 대화형 작업을 담기 위한 전위 큐(foreground queue)에는 응답시간을 짧게하기 위해 어떤 스케줄링을 적용할까요? ㅇㅇㅇ ㅇㅇ
  • 5-2. 계산 위주의 작업을 담기 위한 후위 큐(background queue) 문맥교환 오버헤드를 줄이기 어떤 스케줄링을 적용할까요? ㅇㅇㅇㅇ
  • 5-3. 큐의 스케줄링 방식 중, 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스하는 방식은 무엇일까요? ㅇㅇ ㅇㅇㅇㅇ 방식
  • 5-4. 큐의 스케줄링 방식 중, 각 큐에 CPU 시간을 적절한 비율로 할당해 기아현상을 해소할 수 있는 방식은 무엇일까요? ㅇㅇ ㅇㅇㅇㅇ 방식

[문제6] 다중처리기 스케줄링은 CPU가 여러개인 멀티프로세서 시스템에서의 스케줄링 방식인데요

  • 6-1. 각 CPU가 알아서 스케줄링을 결정하는 방식은 무엇일까요? ㅇㅇㅇ 다중처리
  • 6-2. 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식은 무엇일까요? ㅇㅇㅇㅇ 다중처리
📄 답지
[문제0] 다음의 설명을 읽고, 보기에서 가장 적절한 스케줄링 알고리즘을 골라주세요.
  • 0-1. 프로세스가 준비큐에 도착한 시간 순서대로 CPU를 할당하는 방식 : 선입선출 스케줄링(FCFS)
  • 0-2. 현재 CPU에서 실행중인 프로세스의 남은 CPU버스트 시간보다 더 짧은 CPU 버스트 시간을 가지는 프로세스가 도착할 경우 CPU를 빼앗는 방식 : 최단작업 우선 스케줄링(SJF)
  • 0-3. 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식 : 우선순위 스케줄링
  • 0-4. 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식 : 라운드로빈 스케줄링
  • 0-5. 성격이 다른 프로세스를 별도로 관리하고, 프로세스 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 여러 개로 분할해 관리하는 방식 : 멀티레벨큐
  • 0-6. CPU를 기다리는 프로세스를 여러 큐에 줄세우되, 프로세스가 하나의 큐에서 다른 큐로 이동이 가능한 방식 : 멀티레벨 피드백큐
  • 0-7. CPU가 여러개인 멀티프로세서 시스템에서의 CPU스케줄링 방식 : 다중처리기 스케줄링
  • 0-8. 각 작업마다 주어진 데드라인이 있어 정해진 데드라인 안에 반드시 작업을 처리해야할 경우에 사용하는 스케줄링 기법으로, 주로 데드라인이 얼마남지 않은 요청을 먼저 처리하는 방식 : 실시간 스케줄링

[문제1] 선입선출(FCFS) 스케줄링의 대표적인 단점이 있는데요
  • 1-1. 이 현상을 무엇이라고 할까요? 콘보이 현상(Convoy effect)
  • 1-2. 이 현상에 대해서 간단하게 설명해주세요.
    • CPU 버스트가 짧은 프로세스가 CPU 버스트가 긴 프로세스보다 나중에 도착해 오랜시간을 기다려야 하는 현상
[문제2] 최단작업 우선(SJF) 스케줄링에도 대표적인 단점이 있는데요
  • 2-1. 이 현상을 무엇이라고 할까요? 기아 현상(starvation)
  • 2-2. 이 현상에 대해서 간단하게 설명해주세요.
    • 계속 CPU 버스트가 짧은 프로세스에게만 CPU를 할당할 경우 CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 함
  • 2-3. '세초공주를 구하라' 게임에 접속해주세요 링크
[문제3] 우선순위 스케줄링에서는 SJF의 문제를 해결할 수 있는 기법을 사용하는데요
  • 3-1. 이 기법을 무엇이라고 할까요? 노화 기법(aging)
  • 3-2. 이 기법에 대해서 간단하게 설명해주세요.
    • 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법
[문제4] 라운드로빈 스케줄링은 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식인데요
  • 4-1. 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간을 무엇이라고 할까요? 할당시간(time quantum)
  • 4-2. 이 시간이 경과하면 무엇을 발생시켜 해당 프로세스로부터 CPU를 회수해 준비 큐의 제일 뒤에가서 줄을 서 다음번 차례를 기다릴까요? 타이머 인터럽트
  • 4-3. 할당시간을 너무 '짧게'할 경우의 문제점은 무엇인지 간단하게 설명해주세요.
    • 문맥교환의 오버헤드가 증가해 전체 시스템 성능 저하
  • 4-4. 할당시간을 너무 '길게'할 경우의 문제점은 무엇인지 간단하게 설명해주세요.
    • 선입선출과 같은 결과, 콘보이 현상
[문제5] 멀티레벨큐는 성격이 다른 프로세스를 별도로 관리할 수 있는 스케줄링 방식인데요
  • 5-1. 대화형 작업을 담기 위한 전위 큐(foreground queue)에는 응답시간을 짧게하기 위해 어떤 스케줄링을 적용할까요? 라운드 로빈
  • 5-2. 계산 위주의 작업을 담기 위한 후위 큐(background queue) 문맥교환 오버헤드를 줄이기 어떤 스케줄링을 적용할까요? 선입선출
  • 5-3. 큐의 스케줄링 방식 중, 우선순위가 낮은 큐는 우선순위가 높은 큐가 비어있을 때에만 서비스하는 방식은 무엇일까요? 고정 우선순위 방식
  • 5-4. 큐의 스케줄링 방식 중, 각 큐에 CPU 시간을 적절한 비율로 할당해 기아현상을 해소할 수 있는 방식은 무엇일까요? 타임 슬라이스 방식
[문제6] 다중처리기 스케줄링은 CPU가 여러개인 멀티프로세서 시스템에서의 스케줄링 방식인데요
  • 6-1. 각 CPU가 알아서 스케줄링을 결정하는 방식은 무엇일까요? 대칭형 다중처리
  • 6-2. 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임지고 나머지 CPU는 거기에 따라 움직이는 방식은 무엇일까요? 비대칭형 다중처리


6-5 🍂 스케줄링 알고리즘의 평가 　daelee

  • 스케줄링 알고리즘의 성능을 평가하는 방법으로는 ____, ____, ______ 방식이 있다.

    보기 : 시뮬레이션, 뿌잉모델, 트레이스(trace), 구현, 나현, 다현, 대현, 실측, 로드 타임 바인딩, 큐잉모델, 세그먼테이션 기법, 구현 및 실측, 페이징, 고정분할
📄 답지

  • 스케줄링 알고리즘의 성능을 평가하는 방법으로는 ____, ____, ______ 방식이 있다.

    시뮬레이션, 뿌잉모델, 트레이스(trace), 구현, 나현, 다현, 대현, 실측, 로드 타임 바인딩, 큐잉모델, 세그먼테이션 기법, 구현 및 실측, 페이징, 고정분할

    정답 : 큐잉모델, 시뮬레이션, 구현 및 실측

    • 큐잉모델(que-ueing model) : 확률분포를 통해 프로세스의 도착률과 cpu 처리율을 입력값으로 준 뒤 각종 성능지표(cpu의 처리량, 프로세스의 평균 대기시간 등)를 구하는 방식
    • 구현 및 실측(implementation & measurement) : 운영체제 커널의 cpu 스케줄링 코드를 수정해, 동일한 프로그램을 원래 커널과 수정한 커널에서 수행시켜보고 실행시간을 측정/비교하는 방식
    • 시뮬레이션(simulation) : 가상으로 cpu 스케줄링 프로그램을 작성해 결과를 확인하는 방식. 입력값은 실제 시스템에서의 cpu 요청내역을 추출해 사용하기도 하는데, 이 값을 트레이스(trace)라고 부른다.


Bonus Part : Process + CPU 정리 kukim

kukim은 아래의 open_check.c 소스코드를 컴파일하고 실행하였다. 이때 컴퓨터의 내부 작동방식을 자신이 아는 대로 작성해보시오. (C 빌드 과정, 프로세스 메모리 구조에 저장, 스케줄러 알고리즘, 타이머 인터럽트, DMA, 컨택스트 스위칭 활용)

조건

  • 시분할, 선점형 스케줄러, 타이머 인터럽트 존재
  • open_check.out 프로세스 실행되기 전의 CPU에는 프로세스 A가 실행중인 상태
// open_check.c

#include <unistd.h> // close()
#include <stdio.h> // printf()
#include <fcntl.h> // open()

int main()
{
	int fd;
	fd = open("data.txt", O_RDONLY);
	if (fd == -1)
	{
		printf("Error: can not open file\n");
		return 1;
	}
	else
	{
		printf("File opened & not close \n");
		close(fd);
		return 0;
	}
}
📄 답지

kukim의 문제풀이 : https://bit.ly/process_cpu