I.
Data Structures and Functions:
1. thread.h :
Combine the attributes from both sections:
struct thread {
// ... existing attributes ...
int priority; // Current dynamic priority (calculated by
MLFQ)
int base_priority; // Initial priority (could be considered as
nice level mapped to a priority)
fixed_t recent_cpu; // Recent CPU usage (for MLFQ calculations)
int nice; // Nice value (user-adjustable, influences
priority)
int real_priority; // Used for priority donation, stores the
original calculated MLFQ priority
struct list locks_held; // List of locks held by the thread
struct lock *current_lock; // Pointer to the lock the thread is
currently waiting for (if any)
};
Explanation:
priority : This will hold the dynamically calculated priority
based on MLFQ rules.
base_priority : initial priority of the thread (can set by users)
recent_cpu : Tracks recent CPU usage for MLFQ.
nice : Allows users to influence thread priority (similar to UNIX
nice values).
real_priority : Stores the actual calculated priority before any
donation. This is essential for restoring the original priority
after releasing locks.
locks_held : Keeps track of locks held, crucial for priority
donation.
current_lock : Used during recursive priority donation.
2. synch.h :
struct lock {
// ... existing attributes ...
struct list_elem elem; // List element for priority donation tracking
int max_priority; // Highest priority among waiting threads (for
donation)
};
struct semaphore {
// ... existing attributes ...
struct list waiters; /* List of waiting threads. */
};
struct semaphore_elem
{
struct list_elem elem; /* List element. */
struct semaphore *semaphore; /* Current semaphore. */
int priority;
};
Explanation:
[Link] : Used to put locks into the locks_held list of a
thread.
lock.max_priority : Tracks the highest priority of threads waiting
for this lock. This optimization avoids traversing the waiters
list repeatedly during donation.
semaphore_elem.priority : the priority of the thread who is
waiting for this semaphore
3. thread.c :
static fixed_t load_avg; // Global load average
Explanation:
load_avg : System-wide load average, used in MLFQ calculations.
II. Algorithms and Implementation:
1. Initialization:
In thread_init() :
Initialize load_avg to 0.
Initialize each thread's recent_cpu to 0.
Initialize each thread's nice to 0 (or a user-specified value).
Initialize base_priority to PRI_DEFAULT (or other default
priority).
Calculate initial priority using MLFQ formula (see Priority
Calculation below).
Initialize real_priority to priority
Initialize locks_held as an empty list for each thread.
2. Priority Calculation (MLFQ):
Formula:
priority = PRI_MAX - (recent_cpu / 4) - (nice * 2)
Make sure the priority is within the bounds [PRI_MIN, PRI_MAX]
Recalculation Points:
Every thread: Recalculate every 4 timer ticks.
All threads: Recalculate recent_cpu and then priority once per
second using the following formulas:
recent_cpu = (2 * load_avg) / (2 * load_avg + 1) * recent_cpu +
nice
Load Average Update:
Update load_avg once per second:
load_avg = (59/60) * load_avg + (1/60) * ready_threads
(where ready_threads is the number of threads in the ready
list, not including the idle thread).
3. Choosing the Next Thread to Run ( schedule() ):
Modify next_thread_to_run() :
Select the thread with the highest priority from the ready_list .
4. Timer Interrupt ( timer_interrupt() ):
Increment recent_cpu of the running thread.
If 4 ticks have passed, recalculate the running thread's priority .
