История изменений

Ты не прав. Цикл while означает «выполнять, пока не получится сделать всё атомарно». То есть, если нас не прерывали, то случится break на первой же итерации. Если прервали, то придётся кое-что переделать (структура данных при этом не будет разрушена).

Добавление (пробуждение ото сна) задачи в список выполняется за О(1).

Вот с удалением есть проблема, потому что надо найти предыдущий элемент (вложенный while). Там сложность O(N). Но отправлять задачу в сон обработчики прерывания не будут, только обычные процессы.

Кстати, N здесь количество не спящих задач с таким же приоритетом, а не общее количество задач.

Я многое переделал в коде. Теперь последний элемент списка указывает на NULL.

http://pastebin.com/EqG53n4F

А вот упрощённый вариант алгоритма добавления-удаления, если лень разбираться, http://pastebin.com/2TvDf0Sy.

У меня срабатывает assert при тестировании. Не могу понять, где ошибка.

Ты не прав. Цикл while означает «выполнять, пока не получится сделать всё атомарно». То есть, если нас не прерывали, то случится break на первой же итерации. Если прервали, то придётся кое-что переделать (структура данных при этом не будет разрушена).

Добавление (пробуждение ото сна) задачи в список выполняется за О(1).

Вот с удалением есть проблема, потому что надо найти предыдущий элемент. Там сложность O(N). Но отправлять задачу в сон обработчики прерывания не будут, только обычные процессы.

Кстати, N здесь количество не спящих задач с таким же приоритетом, а не общее количество задач.

Я многое переделал в коде. Теперь последний элемент списка указывает на NULL.

http://pastebin.com/EqG53n4F

А вот упрощённый вариант алгоритма добавления-удаления, если лень разбираться, http://pastebin.com/2TvDf0Sy.

У меня срабатывает assert при тестировании. Не могу понять, где ошибка.

Ты не прав. Цикл while означает «выполнять, пока не получится сделать всё атомарно». То есть, если нас не прерывали, то случится break на первой же итерации. Если прервали, то придётся кое-что переделать (структура данных при этом не будет разрушена).

Добавление (пробуждение ото сна) задачи в список выполняется за О(1).

Вот с удалением есть проблема, потому что надо найти предыдущий элемент. Там сложность O(N). Но отправлять задачу в сон обработчики прерывания не будут, только обычные процессы.

Кстати, N здесь количество не спящих задач с таким же приоритетом, а не общее количество задач.

Ты не прав. Цикл while означает «выполнять, пока не получится сделать всё атомарно». То есть, если нас не прерывали, то случится break на первой же итерации. Если прервали, то придётся кое-что переделать (структура данных при этом не будет разрушена).

Добавление задачи в список выполняется за О(1).

Вот с удалением есть проблема, потому что надо найти предыдущий элемент. Там сложность O(N). Но отправлять задачу в сон обработчики прерывания не будут, только обычные процессы.