What to do for this Project $($Implementation of Fair Scheduler$)$ :

$$ Change ready queue from unsorted list to list sorted by vruntime and tid

$$ Each tick calculate the ideal runtime and compare time running

$$ If time running is longer yield and add to ready queue $($unless ready to terminate$)$

$$ Thread block

$$ Remove from ready queue

$$ Thread Unblock

$$ Add to ready queue

$$ Cause current thread to yield if CPU was idle or if get sleeping boost

What to do $-$ variables

Variables to think about :

$$ Vruntime $-$ for each thread

$$ Weight table $-$ for scheduler to use

$$ Min$\_$vruntime $-$ for each ready queue

$$ vruntime$\_0-$ for each thread

$$ CPU time consumed $-$ for each thread

$$ Thread$$s time slice $($ideal runtime$)$ for each thread

$$ Number of threads running or ready for each ready queue

$$ Weight of thread $-$ for each thread

$$ Sum of weights $-$ for each ready queue

What to do $-$ Initialization

$$ Some variables need to be initialized when each CPU first thread is initialized and ready queue is set$-$up

$$ Some variables need to be initialized when threads are created

Each Tick

$$ Thread$\_$tick calls sched$\_$tick

$$ Determine if thread needs to yield

$$ Calculate and compare ideal runtime to the amount of time that thread has been running

$$ Then thread$\_$yield calls sched$\_$yield

$$ Update how long thread has been running

$$ Add to ready$\_$queue in order by runtime and tid

$$ Update number of threads in ready queue

$$ Update sum of weights

$$ Then thread$\_$tick calls schedule$()$

$$ Calls next thread to run which calls sched$\_$pick$\_$next

$$ Remove from ready queue just like before but also

$$ Update any variables about when it was last run or runtime was calculated etc if you are using them

$$ Update number of threads in ready queue

$$ Update sum of weights

$$ Calls switch thread

$$ Calls thread$\_$schedule$\_$tail

Thread Block$/$Unblock

$$ Block

$$ Remove from ready queue

$$ Update variables

$$ Unblock

$$ Add to ready queue

$$ Update variables

$$ Trigger schedule if CPU was NULL or if thread got a sleeping boost

Theory :

CFS $-$ Niceness :

Niceness $($in thread struct$)$

indication of priority

Higher niceness $=$ lower priority

Function: int thread$\_$get$\_$nice $($void$)$

Returns the current thread's nice value.

Function: void thread$\_$set$\_$nice $($int new$\_$nice$)$

Sets the current thread's nice value to new$\_$nice.

CFS Weights :

static const uint$32\_$t prio$\_$to$\_$weight$[40]=$

$\{$

$/*-20*/88761,71755,56483,46273,36291,$

$/*-15*/29154,23254,18705,14949,11916,$

$/*-10*/9548,7620,6100,4904,3906,$

$/*-5*/3121,2501,1991,1586,1277,$

$/*0*/1024,820,655,526,423,$

$/*5*/335,272,215,172,137,$

$/*10*/110,87,70,56,45,$

$/*15*/36,29,23,18,15,$

$\}$

Algorithm Summary :

$1.$Preempt the current thread at each timer tick if it exceeds its ideal runtime.

$2.$Select the next thread with the lowest virtual runtime $($vruntime$),$ using thread ID $($tid$)$ to break ties.

$3.$ Update a thread's vruntime by adding d $*($w$0/$w$)$ where d is the CPU time since the last update, w$0$ is the base weight and w is the thread$$s weight.

$4.$ Keep track of the minimum vruntime $($min$\_$vruntime$)$ across all threads, ensuring it remains nonnegative.

$5.$ Calculate ideal$\_$runtime as $4000000*$ n $*($w$/$s$)$ where n being the count of active or ready threads, w is the current threads weight and s the total weight of all active or ready threads

$6.$ For a thread unblocked for the first time, set its vruntime to min$\_$vruntime.

$7.$ For threads unblocked subsequently, adjust their vruntime to the maximum of its current vruntime or min$\_$vruntime minus $20000000.$

$8.$ Prompt the CPU to yield if an unblocked thread has a lower vruntime than the current thread or if the CPU is idle, ensuring efficient and fair scheduling.

$$Provide code as per Pseudocode and necessary changes in Pintos Multi Processor OS to implement a complete Fair Scheduler.