pintos(2)-優先スケジューリング

Pintos Priority Scheduling

Pintosの優先順位スケジューリングメカニズムを確立し、最も優先度の高いスレッドがいつでもCPUで実行されていることを確認します。

  • 優先度が最も高いスレッドを確実に実行するために、スケジューリングを再計算する必要があるのは、新しいスレッドを作成し、スレッドの優先度を設定することです。したがって、ready_listを優先度の高い順序付きキューに変更します。同時に、thread_yield()で、次のスレッドの優先度が現在のスレッドよりも低い場合、スケジューリングは実行されません。
  • セマフォと条件変数の優先度は、ウェイターリストが優先度が最も高いスレッドをウェイクアップするように配置されていることを確認することで実現できます。

基本的な優先順位:

thread_create()関数の最後にスケジューリング判定を追加します。

/* If the new thread have a greater priority, * we should add current thread to ready list and schedule.*/ struct thread * cur_t = thread_current() if(priority > cur_t->priority){ thread_yield() }

thread_unblock()中尉将軍list_push_back() To list_insert_ordered(&ready_list, &t->elem, priority_less, NULL)



priority_less()関数は次のように実装されます。

/* Compare struct thread by priority. * The bigger number means the bigger priority, * so use '>' to make the bigger priority in the front of list.*/ bool priority_less(const struct list_elem *e1,const struct list_elem *e2, void *aux){ return list_entry(e1, struct thread, elem)->priority > list_entry(e2, struct thread, elem)->priority }

thread_yield()では、次のスレッドの優先度が判断されます。現在のスレッドよりも小さい場合、スケジュールされません。

void thread_yield (void) { struct thread *cur = thread_current () enum intr_level old_level ASSERT (!intr_context ()) old_level = intr_disable () if (cur != idle_thread){ /* If the next ready thread priority is lower than current, just do nothing.*/ if(!list_empty(&ready_list)){ int next_thread_priority = list_entry (list_front(&ready_list), struct thread, elem)->priority if(next_thread_priority >= cur->priority){ list_insert_ordered(&ready_list, &cur->elem, priority_less, NULL) cur->status = THREAD_READY schedule () } } } intr_set_level (old_level) }

スレッドの優先度を設定した後、thread_yield()を1回実行します。

/* Sets the current thread's priority to NEW_PRIORITY. */ void thread_set_priority (int new_priority) { enum intr_level old_level = intr_disable () thread_current ()->priority = new_priority thread_yield() intr_set_level (old_level) }

これまでのところ、alarm-priority priority-change priority-fifopriority-preemptテストに合格しています


セマフォの優先順位:

セマフォを待機しているスレッドが優先順位に従って配置された後、sema_up()関数は、最も高い優先度で待機中のスレッドをウェイクアップできます。

will sema_down() middle list_push_back()に変更:
list_insert_ordered(&sema->waiters, &thread_current ()->elem, priority_less, NULL)
priority_less()は上記の関数を再利用します。

優先セマテストに合格


条件変数の優先度:

  • 条件変数は、構造体条件とロックで構成されます。ロックは、条件操作が競合しないようにするために使用されます。条件には、条件を待機しているsemaリストが含まれています。
  • 条件が確立されると、cond_signal()関数が呼び出され、セマリストの最初のセマフォがウェイクアップされます。最高の優先度でスレッドをウェイクアップしたいので、semaを所有するスレッドの優先度に従ってsemaリストを配置する必要があります。

semaphore_elemのセマフォを所有するスレッドにポインター所有者を追加します。

/* One semaphore in a list. */ struct semaphore_elem { struct list_elem elem /* List element. */ struct semaphore semaphore /* This semaphore. */ struct thread *owner /* Owner of this semaphore.*/ }

cond_wait()で、所有者を初期化します。
waiter.owner = thread_current()

同時にlist_push_back()宛先:
list_insert_ordered(&cond->waiters, &waiter.elem, priority_less_cond, NULL)

その中で、priority_less_cond()実装は次のとおりです。

/* * Compare the cond->waiters list element semaphore_elem's owner thread priority. * See as thread/priority_less() * */ bool priority_less_cond(const struct list_elem *e1,const struct list_elem *e2, void *aux){ return list_entry(e1, struct semaphore_elem, elem)->owner->priority > list_entry(e2, struct semaphore_elem, elem)->owner->priority }

priority-condvarテストに合格