문제 CPU 스케줄링 개념 이해

Question

커널 레벨 스레드로 CPU 스케줄링 시뮬레이션을 작성해야합니다. FCFS (first come first served) 또는 RR (round robin) 알고리즘을 사용할 수 있어야합니다. 프로세스 및 스레드에 대한 데이터는 텍스트 파일 형식으로 제공됩니다. 현재 내 프로그램은 텍스트 파일 데이터를 링크 된 목록으로 읽습니다. 시뮬레이션을 시작하는 방법을 잘 모르겠습니다. (전에는 시뮬레이션을 프로그래밍 한 적이 없었습니다.)

FCFS의 경우 어떻게 진행합니까? 첫 번째 프로세스의 첫 번째 스레드에 도달하면 CPU 시간을 시계 시간에 추가합니다. 그런 다음 CPU가 유휴 상태 일 때 I/O 시간을 시계에 간단하게 추가합니까? 또는 대기열에 다시 넣고 다음 스레드가 CPU에서 실행을 시작할 수 있도록해야합니까? 그렇다면 어떻게 각 스레드가 이미 실행되었는지 추적 할 수 있습니까?

2 4 6 // number_of_processes thread_switch process_switch 
1 5 // process_number(1) number_of_threads(1) 
1 0 4 // thread_number(1) arrival_time(1) number_of_CPU(1) 
1 15 100 // 1 cpu_time io_time 
2 18 120 // 2 cpu_time io_time 
3 12 100 // 3 cpu_time io_time 
4 16 // 4 cpu_time 
2 4 4 // thread_number(2) arrival_time(2) number_of_CPU(2) 
1 18 110 
2 15 80 
3 20 75 
4 15 
3 6 5 //thread(3) 
1 40 100 
2 20 70 
3 15 80 
4 18 90 
5 50 
4 8 4 //thread(4) 
1 25 60 
2 15 50 
3 20 80 
4 18 
5 18 4 //thread(5) 
1 8 60 
2 15 120 
3 12 80 
4 10 

Answer 1

의 I/O 시간이 제공 한 정보를 기반으로 모호한 것 같다 여기

는 예를 들어 테스트 파일입니다. 이것과 함께 할 spec/instructions가 있습니까?

일반적으로 I/O 시간은 I/O 요청이 완료 될 때까지 기다리는 동안 현재 실행중인 스레드를 스왑 아웃 할 수있는 창을 제공한다고 생각합니다. I/O 시간이 CPU 시간 전후인지, 또는 CPU 시간과 혼합되었는지는 알 수 없습니다. 이는 시뮬레이터를 구현할 때 예상되는 설계 결정일 수 있습니다.

'number_of_CPU'옵션의 영향에 대한 모호성이 있습니다. 얼마나 많은 CPU 코어를 시뮬레이트하고 있습니까? 또는 이것은 스레드가 CPU를 만드는 요청의 수를 계산 한 것입니다 (여러 개의 CPU가 동시에 실행되는 단일 스레드를 가질 수 없기 때문에 그렇게 보입니다).

어쨌든 FCFS 알고리즘을 다루는 일반적인 방법은 맞습니다. 본질적으로 요청 대기열을 유지하려는 경우 CPU가 유휴 상태 일 때마다 다음 작업을 대기열에서 꺼내 실행합니다. 단일 코어 CPU를 가정하고 I/O 시간을 무시하면 결과는 다음과 같아야합니다.

time=0 
    Thread 1 arrives, and wants to do 15 time-units of work 
     Thread 1 starts executing 15 time-units of work 

time=4 
    Thread 2 arrives, and wants to do 18 time-units of work 
     Thread 2 is blocked because Thread 1 is executing 

time=6 
    Thread 3 arrives, and wants to do 40 time-units of work 
     Thread 3 is blocked because Thread 1 is Executing 

time=8 
    Thread 4 arrives and wants to do 25 time-units of work 
     Thread 4 is blocked because Thread 1 is Executing 

time=15 
    Thread 1 completes its initial set of work 
    Thread 2 is next in the queue, and begins executing 
    Thread 1 wants to do 18 time-units of work 
     Thread 1 is blocked because Thread 2 is executing 

time=18 
    Thread 5 arrives and wants to do 8 time-units of work 
     Thread 5 is blocked because Thread 2 is executing 

time=33 
    Thread 2 completes its initial set of work 
    Thread 3 is next in the queue, and begins executing 
    Thread 2 wants to do 15 time-units of work 
     Thread 2 is blocked because Thread 3 is executing 

...