I'm now working for a real time os kernel, it's preemptive multitasking.
one thing feazes me a long time is how to implement thread sleeping.
once a thread invokes sleep function with a timeout parameter, the thread won't be scheduled again until
time out.
I try to implement it by the following way:
there is a single direction link list of Thread Control Blocks(TCB), and each TCB has a member sleeptime
which specify how long will the thread sleep. The first node's sleeptime is the longest, and the last one's
sleeptime is the shortest.
and i hook the real time clock interrupt, in the my isr, scan TCB in the list from the first to the end, each
TCB's sleeptime decreases 1, if the TCB's sleeptime is zero, then delete it in the list, and let the thread
specified by the TCB to run.
It seems it can work, but there is a big problem, in each interruption, my isr has to scan the list from the
first to the end, that wastes a lot of cpu time, and the more nodes of the list the more cpu time are wasted.
And then, I improve the algorithm, i set a variable to record the initial shortest sleeptime of TCB, that is, the last node's initial sleeptime. and in my isr, i just decreases the variable's value, this way save a lot of time, but once the variable' value is to zero, i still have to scan the whole list, and subtract the last node's
sleeptime from each node's sleeptime.
This algorithm still have problem and i can not solve it, yep, it's no need to scan the whole list in each interruption, but once the variable is to zero, i still have to.
And I think, if i still use this type of structure(a link list), it can't improve the performance.
but i can't think out another solutions. if you have good solution, please contact me.
I have to say sorry to you about my poor english, it must have taken you a long time to try to understand
what i am stating.
Best regards
Posted on 2003-06-02 00:44:09 by littlebob1
littlebob1, why not just keep the difference between thread waits:

Thread1 100 ; time to wait...
Thread2 150
Thread3 170
Thread4 250
Thread5 500

Thread1 100 ; time until thread execute...
Thread2 50
Thread3 20
Thread4 80
Thread5 250

Instead of the first list use the second above. Now the top entry in the list gives the amount of time to wait, and the list only needs to be scanned when adding a thread. Example, if Thread1 executes every 100 - at time of execution it is put back into the list with a delay of 100 from current time:

Thread1 0 - (execute now)
Thread2 50
Thread3 20
Thread1 30 ; next trigger for Thread1
Thread4 50
Thread5 250
Posted on 2003-06-02 01:11:16 by bitRAKE
A perfect algorithm bitRAKE has made, isn't it?
Now, my isr is no need to scan the list.
I don't konw how to appreciate you, I just say a thousand times of
Thanks very much.........................................
Posted on 2003-06-02 01:59:56 by littlebob1
littlebob1, you are welcome. The algorithm is okay until the number of threads gets bigger - then the data structure needs to be changed (a square array should work for all needs).
Posted on 2003-06-02 19:45:12 by bitRAKE
How about giving me more details about square array structure?
I have no idea on it.
Posted on 2003-06-04 00:14:14 by littlebob1
That's just a two dimensional array I think.
Posted on 2003-06-04 05:31:37 by iblis
I just have no idea on how to use the square array to implement what I wana do.
Posted on 2003-06-04 08:17:44 by littlebob1
bitRAKE, can you give me more details about how to use square array to implement the sleep algorithm?
Thanks bitRAKE.
Posted on 2003-06-18 08:51:00 by littlebob1
I don't have any code, but it is on my list of algorithms to implement and I read a good article in C++ magazine. I'm in the middle of moving this week, but I'll spend some time to explain:
; Square array - no surprises yet ;)

n 2n 3n ... n^2

n-1 2n-1 3n-1 ... n^2-1




2 n+2

1 n+1 2n+1 ... n^2 - n + 1

My idea is to have the top row in an array that grows - reserving space for SQR(max_nodes) is not a big deal.


column_first DWORD ?
this_value DWORD ?

; helpful column sums
column_sum DWORD ?

Each of these nodes point to the column array - making it square. Also each array can be searched in a binary fasion - making the maximum find time 2*(log2 n). For example, if (n) is 2^9 then the sqaure array supports 2^18 items, and takes a maximum of 18 compares to find any item - half that on average. :)

This might not work so well for your uses? As threads retire, whole columns would retire and new ones would have to be added on the end to keep the array square - resizing the array is costly unless a double linked list is used for the items.

I've tried to find a reference on the web for this structure, but it's not commonly used. I'll whip up some code eventually -- either when I have a serious need or free time to explore it more.
Posted on 2003-06-18 14:47:29 by bitRAKE