Kernel: Refactor scheduler to use dynamic thread priorities

Threads now have numeric priorities with a base priority in the 1-99
range.

Whenever a runnable thread is *not* scheduled, its effective priority
is incremented by 1. This is tracked in Thread::m_extra_priority.
The effective priority of a thread is m_priority + m_extra_priority.

When a runnable thread *is* scheduled, its m_extra_priority is reset to
zero and the effective priority returns to base.

This means that lower-priority threads will always eventually get
scheduled to run, once its effective priority becomes high enough to
exceed the base priority of threads "above" it.

The previous values for ThreadPriority (Low, Normal and High) are now
replaced as follows:

    Low -> 10
    Normal -> 30
    High -> 50

In other words, it will take 20 ticks for a "Low" priority thread to
get to "Normal" effective priority, and another 20 to reach "High".

This is not perfect, and I've used some quite naive data structures,
but I think the mechanism will allow us to build various new and
interesting optimizations, and we can figure out better data structures
later on. :^)

2 files changed, 14 insertions, 20 deletions

diff --git a/Applications/SystemMonitor/ProcessModel.cpp b/Applications/SystemMonitor/ProcessModel.cpp
index 88fa965907..f9190d442a 100644
--- a/Applications/SystemMonitor/ProcessModel.cpp
+++ b/Applications/SystemMonitor/ProcessModel.cpp
@@ -55,6 +55,8 @@ String ProcessModel::column_name(int column) const
         return "User";
     case Column::Priority:
         return "Pr";
+    case Column::EffectivePriority:
+        return "EPr";
     case Column::Virtual:
         return "Virtual";
     case Column::Physical:
@@ -108,7 +110,9 @@ GModel::ColumnMetadata ProcessModel::column_metadata(int column) const
     case Column::State:
         return { 75, TextAlignment::CenterLeft };
     case Column::Priority:
-        return { 16, TextAlignment::CenterLeft };
+        return { 16, TextAlignment::CenterRight };
+    case Column::EffectivePriority:
+        return { 16, TextAlignment::CenterRight };
     case Column::User:
         return { 50, TextAlignment::CenterLeft };
     case Column::Virtual:
@@ -177,16 +181,9 @@ GVariant ProcessModel::data(const GModelIndex& index, Role role) const
         case Column::User:
             return thread.current_state.user;
         case Column::Priority:
-            if (thread.current_state.priority == "Idle")
-                return 0;
-            if (thread.current_state.priority == "Low")
-                return 1;
-            if (thread.current_state.priority == "Normal")
-                return 2;
-            if (thread.current_state.priority == "High")
-                return 3;
-            ASSERT_NOT_REACHED();
-            return 3;
+            return thread.current_state.priority;
+        case Column::EffectivePriority:
+            return thread.current_state.effective_priority;
         case Column::Virtual:
             return (int)thread.current_state.amount_virtual;
         case Column::Physical:
@@ -249,15 +246,9 @@ GVariant ProcessModel::data(const GModelIndex& index, Role role) const
         case Column::User:
             return thread.current_state.user;
         case Column::Priority:
-            if (thread.current_state.priority == "Idle")
-                return String::empty();
-            if (thread.current_state.priority == "High")
-                return *m_high_priority_icon;
-            if (thread.current_state.priority == "Low")
-                return *m_low_priority_icon;
-            if (thread.current_state.priority == "Normal")
-                return *m_normal_priority_icon;
             return thread.current_state.priority;
+        case Column::EffectivePriority:
+            return thread.current_state.effective_priority;
         case Column::Virtual:
             return pretty_byte_size(thread.current_state.amount_virtual);
         case Column::Physical:
@@ -338,6 +329,7 @@ void ProcessModel::update()
             state.tid = thread.tid;
             state.times_scheduled = thread.times_scheduled;
             state.priority = thread.priority;
+            state.effective_priority = thread.effective_priority;
             state.state = thread.state;
             sum_times_scheduled += thread.times_scheduled;
             {
diff --git a/Applications/SystemMonitor/ProcessModel.h b/Applications/SystemMonitor/ProcessModel.h
index cccedbcb3a..2572444ccc 100644
--- a/Applications/SystemMonitor/ProcessModel.h
+++ b/Applications/SystemMonitor/ProcessModel.h
@@ -25,6 +25,7 @@ public:
         CPU,
         State,
         Priority,
+        EffectivePriority,
         User,
         PID,
         TID,
@@ -71,7 +72,8 @@ private:
         String name;
         String state;
         String user;
-        String priority;
+        u32 priority;
+        u32 effective_priority;
         size_t amount_virtual;
         size_t amount_resident;
         size_t amount_dirty_private;