Ich bin auf der Suche nach einer Möglichkeit, Threads nach Prioritäten und First-Come-First-Serve (FCFS) zu planen, wenn zwei Threads die gleiche Priorität haben. Ich dachte daran, einen Haufen Warteschlangen oder so etwas zu benutzen. Das Problem ist, dass selbst wenn ich meine eigene Prioritätswarteschlange implementiere, die Fähigkeit, Prioritäten zu ändern, die Reihenfolge der Einfügung in diese Warteschlange ruiniert.Priority Queue mit Change Priority-Funktion, die Elemente geordnet hält
Um dieses Problem zu lösen, kann ich die Einfügezeit jedes Threads speichern und die Prioritätswarteschlange auch nach der Einfügezeit sortieren (als sekundärer Parameter zum primären Prioritätsparameter), aber ich glaube, dass es eine Kombination von Daten gibt Strukturen, die das Problem ohne Verwendung der Insertionszeit lösen können.
Die Komplexität sollte O(logN) sein (es gibt einige naive Lösungen mit O(N) Komplexität, wie zum Beispiel eine reguläre Warteschlange, und Iterieren der Warteschlange, wann immer wir einen Thread öffnen müssen).
Wenn dies ein Betriebssystem-Kernel ist, würde ich nicht in der Nähe versuchen, die Einfügezeit jedes Threads zu speichern - es ist zu viel Mühe für nicht genug Gewinn. In dem seltenen Fall, dass jemand eine Thread-Priorität ändert entferne den Thread aus einer Warteschlange und schiebe ihn auf eine andere. Wenn die Priorität erhöht wurde, lege sie an den Kopf, wenn sie verringert wird, lege sie an den Schwanz. Führe dann einen Dispatch-Lauf aus, um [Anzahl der Prozessoren] -Threads von der höchsten zu erhalten. Priority Queue und arbeite nach unten und entscheide, wie man Threads den Prozessoren auf deine übliche Weise zuweist –
Ich bekomme jetzt wirklich verwirrt :(Ein Thread in einer Warteschlange hinzugefügt hat garantiert 0 Zeit - es ist gerade jetzt eingefügt, so sollte es auf der Rückseite der Warteschlange gehen. Sie könnten die Einfügezeit aus der vorherigen Warteschlange verwenden, in der sie sich befand, aber der Thread könnte kürzlich aus einer vorherigen Warteschlange verschoben worden sein ... Ich bekomme diese Anforderung nicht und kann mir nicht vorstellen, was sie lösen soll - ich werde es tun muss noch darüber nachdenken ... –
Durch das Speichern der Einfügezeit wollte ich nicht wirklich die Zeit speichern, sondern einen Zähler haben und jedem Thread einen "Zeitstempel" geben, wenn er fertig ist und eingefügt werden soll in die Warteschlange, sodass die Threads nach ihren Zeitstempeln geordnet werden können. Kostet es zu viel? – Lior