Trouble Understanding CPU Scheduling Concepts
I have to write a CPU scheduling simulation with kernel level threads. I have to be able to use either first come first served (FCFS) or round robin (RR) algorithms. Data for the processes and their threads is given in the form of a text file. At the moment my program reads in the text file data into linked lists. I'm not really sure how to start the simulation (I've never programmed a simulation before).
Is this how I would proceed in the case of FCFS? When I get to the first thread of the first process, I add the cpu time to the clock time. Then do I simply add the io time to the clock as well while the cpu is idle? or should I put it back in a waiting queue and allow the next thread to start running in the cpu? If so how do I keep track of how much of each thread has already been excecuted?
here is an example test file:
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
The I/O time seems ambiguous based upon the information provided. Do you have a spec/instructions to go along with this?
In general I would think that the I/O time provides you with a window in which the currently executing thread(s) can be swapped out while they wait for I/O requests to complete. Though nothing seems to indicate if the I/O time occurs before, after, or intermixed with the CPU time. That may be a design decision you're expected to make when implementing your simulator.
There's also ambiguity with respect to what impact the 'number_of_CPU' option has. How many CPU cores are you simulating? Or is this just a count of the number of requests that the thread will make of the CPU (which it seems like it is, since you can't have a single thread running on multiple CPU's concurrently)?
In any case, you're correct about the general approach for handling the FCFS algorithm. Essentially you'll want to maintain a queue of requests, and whenever the CPU is idle you simply pull the next thing out of the queue and execute it. Assuming a single-core CPU and ignoring I/O time, the result should look something like this:
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
...
上一篇: 反馈和HRRN调度算法？
下一篇: 无法理解CPU调度概念