search

zephyriot / zephyr-issues

0 stars 0 forks source link

O(1) pend queue support #860

Open nashif opened 8 years ago

nashif commented 8 years ago

Reported by Benjamin Walsh:

Searching a wait queue for a kernel object to determine where to insert a waiting thread (based on its priority) is potentially very inefficient. Providing a configuration option that creates a separate queue for each possible thread priority would allow the thread to simply be appended to the queue for its associated priority, without the need for searching. (Of course, this forces the kernel to do additional work to allow it to quickly identify the highest priority non-empty queue when it wants to service the highest priority waiting thread.)

(Imported from Jira ZEP-915)

nashif commented 8 years ago

by Sharron LIU:

this looks measurable by the latency of kernel object? do we have benchmark for this already?

nashif commented 8 years ago

by Deli Niu:

No PnP benchmark covers it now.

nashif commented 8 years ago

by Deli Niu:

Test point is to make sure the configuration works, and if just depend on PnP latency data, it could not be sure that configuration works or not. One KPI’s data does not make sense. It needs series of latency data to compare with that without configuration to judge whether it is O(1) or not. From PnP side, it is not testable.

nashif commented 8 years ago

by Deli Niu:

From PnP point, could consider create 2 KPIs to check enable and disable configration response time and provide 2 different data indirectly. But need to discuss with PnP stakeholders, if it is necessary.

nashif commented 7 years ago

by Andy Ross:

Devil's advocate: how long are wait_q lists, in practice, right now? On all our existing platforms we start to run out of memory well before we hit even dozens of threads. Is an O(1) scheduler even useful? The list of priorities (which you have to search to find an non-empty one) is going to be just about as long as the list of tasks you have to search for all but the biggest apps.

Absent measured evidence, I'd strongly argue we ignore this one.

nashif commented 7 years ago

by Benjamin Walsh:

This is a memory-hungry feature yes, and would only be useful for someone who wants hard realtime. However, the list of priorities does not have to be searched: it's a bit mask whose first set bit is read in one instruction and an array of queues, one per-priority.