-
Notifications
You must be signed in to change notification settings - Fork 0
proj_scheduler
CPU scheduler for xv6.
Two types of scheduling algorithms are supported: Stride(default), MLFQ.
MLFQ algorithm run with fixed portion of CPU (20%).
int cpu_share(unsigned int portion);A system call that requests the portion of CPU and guarantees the calling process to be allocated that CPU time. Processes that doesn't call any other system calls(i.e. cpu_share) run with equal CPU portion. The function can reject to allocate the requested portion of CPU.
-
portion
The portion(1-20%) of CPU that the calling process want to use.
A 0 return value indicates success. A -1 return value indicates rejection.
void run_MLFQ();A system call that requests the calling process to run with MLFQ scheduling algorithm.
struct _Proc {
bool is_portion_requested;
unsigned double portion;
unsigned double stride;
unsigned long double step;
...
};
static struct _Proc * _procs;
static unsigned double _total_portion;
static unsigned int _num_procs;
static unsigned int _num_no_portion_requested;
static bool _is_MLFQ_running;struct _Proc represents a single process.
_procs is min-heap, ordered by step, represented by array.
The function rejects when CPU portion is not sufficient. It means the value of _total_portion is not less than 80 + _is_MLFQ_running * 20(%).
Note that this value is different from actual CPU portion, which can be greater than portion. So even though MLFQ is not running, 20% of the portion is not wasted.
If new process enters, the portion of every processes whose value of is_portion_requested is false is updated. Each CPU portion of such processes is determined as (100 - _total_portion) / (_num_no_portion_requested).
The number of processes which did not called scheduler system call is stored in _num_no_portion_requested.
stride = _total_portion / portion;
_procs maintains binary min-heap ordered by step.
This is for fast(O(logN)) selecting a process which has the smallest step.
When cpu_share() selected such process in _procs, it increments the process' step by stride, and push it into _procs again.
If new process enters, its value of step is set by the smallest step over all processes.