Algorithm advice

[electroRF]

Hi,
I got 20 threads, which only 6 of them can be running at the same time.
Thread #1 has the lowest priority, Thread #20 has the highest priority (i.e. Thread #3 can't start if Thread #5 has started and not finished yet).
For example,

   Thread #1 Start -> Thread #6 Start-> Thread #12 Start-> Thread #14 Start -> Thread #17 Start -> Thread #19 Start ->
-> Thread #19 End->   Thread #17 End->  Thread #14 End->   Thread #12 End->    Thread #6 End->     Thread #1 End

Each thread should have a stack of N Bytes.
Instead of dedicating a stack for each thread, i.e. 20 stacks, total of 20*N Bytes,
I'd like to dedicate a single global array for the stacks, of size 6 * N Bytes.

How would you handle the stacks allocation?

I thought of initializing an auxiliary Array with 6 Pointers, meaning:

BYTE GlobalStackArry[6*N];

BYTE* StackPointers[6] =
{
   &GlobalStackArray[0],
   &GlobalStackArray[N],
   &GlobalStackArray[2*N],
   &GlobalStackArray[3*N],
   &GlobalStackArray[4*N],
   &GlobalStackArray[5*N]
}
INT8 StackIndex = 0; //Points on the next available Stack, runs from <0-5> inclusive.

Now, each time a thread starts / ends:

//Thread Starts
SP = StackPointers[StackIndex];
StackIndex++;
if (StackIndex > 5)
   ErrorFunc();


//Thread Ends
StackIndex--;
if (StackIndex < 0)
   ErrorFunc();

I'd love hearing your opinion

Thank you very much.

 

[kubeek]

I don´t think that will work. Lets say all six threads are running, StackIndex is 6. Now lets say thread with index 3 terminates, then stackindex becomes 5, and a new thread will overwrite the stack from thread with index 5.
You need some better memory management than a simple index, for example a list of available stacks would be better.

 

[electroRF]

Hi Kubeek,
Thank you very much

You're correct.

I should have mentioned that, until an high priority thread is finished, a lower priority task can not resume (if it already started).
I think that taking that into account, the mechanism should work?

The idea of a list of available stacks is great!
And their spaces could still be static allocated.

I think that the StackPointers Array I suggested might be more efficient to manage, cycles-wise.
But it is of course not general as the list is, and (I believe) fits to this specific threads system I described.

 

[kubeek]

I should have mentioned that, until an high priority thread is finished, a lower priority task can not resume (if it already started).
I think that taking that into account, the mechanism should work?

Still no dice, lets say that the first six threads are priorites 1 through 6, and number 3 terminates. Thread with priority 20 wants to start executing, what happens? It again overwrites thread 6.

What you need is a mechanism to decide which stack is free to be used (or possibly which thread to suspend and swap to some other part of memory to free that stack), and which also decides which of the waiting threads will go first.

Or do you mean that the six running threads are not actually concurrent and sharing cpu time, but are in fact just a priority queue?

 

[NorthGuy]

If they don't run concurrently (that is high priority suppresses everything of lower priority), they all can use the same stack, so your manipulations are not needed at all.

If they do run concurrently, you must do as kubeek says.

 

[electroRF]

Hi,
Thank you guys!

Or do you mean that the six running threads are not actually concurrent and sharing cpu time, but are in fact just a priority queue?

Exactly,
It's a Priority Queue.

If they don't run concurrently (that is high priority suppresses everything of lower priority), they all can use the same stack, so your manipulations are not needed at all.

If Thread #4 starts, and then Thread #5 interrupts and starts also, they can't use the same Stack, because then when #5 ends and #4 resumes, the #4 will have corrupted data on its stack.

 

[kubeek]

Yes they can have the same stack, when thread #5 starts it starts by pushing the return address and flag register of thread #4 on the stack, and when it finishes it pops everything back and thread #4 continues right where it ended.

 

[electroRF]

Oh I got you Kubeek,
Great Mechanism!

Thank you very much

 

[kubeek]

By the way this is the exact way interrupts work, so you could call it a software interrupt But I really wouldnt call all this a multi-threaded enivronment as you cannot switch between threads.

 

[NorthGuy]

If Thread #4 starts, and then Thread #5 interrupts and starts also, they can't use the same Stack, because then when #5 ends and #4 resumes, the #4 will have corrupted data on its stack.

That is how stack works. Something gets called, it uses top of the stack as needed, then when it leaves the stack is in the same condition as when it started. LIFO - last in first out. As soon as this satement is true, the only bad thing is overflow.

For comparison, circular buffer is FIFO - first in first out.

The third one is random access - heap.