Discussing Real-Time Operating System: ThreadX Questions

[ksatria]

Let's use this thread to discuss about Real-Time Operating System.

In order to be focus, let's discuss start from answering the problem in "Real-Time Embedded Multithreading using ThreadX".

1. What is the usage of thread's stack? (what information pushed to that)
2. What is the primary danger of specifying a thread stack size that is too small? How if too large?
3. Under what circumstances would a thread status be changed from executing to ready? From ready to suspended? From suspended to ready? From completed to ready?

Thanks! Let's start...

 

[rcgldr]

Depends on the RTOS, assuming you mean a generic RTOS (there is an RTOS for the ARM processor family).

1. Thread stack - In addition to the normal registers, whatever it takes to save (and later restore) the current state of the cpu is also saved on each task's stack.

Some processors like the ARM switch to a separate stack for interrupts. If this interrupt is going to cause a task change, then there's code to move the saved registers from the interrupt stack to the current running tasks stack, in order to use common code (the dispatcher) which does the actual switch to the new task.

2. Thread stack size too small can result in stack overflow. Many processors are unable to detect this, and some can only check for this in a debug like mode. Too large wastes space, but if there's plenty of ram for a particular application, it's probably not a big deal.

3. A task is switched to executing to ready when a higher priority task is switched to. The higher priority task would have previousely been in wait for event (sleep) state. The switch from wait to ready could be due to the executing task signaling the waiting higher priority task, such as sending a message, or due an interrupt signaling the waiting higher priority task.

Some multi-tasking OS implementations include the ability to change the priority of a task, or automatically do an increase of priority of a task that has been ready for some period of time (changing it back once that task has run for one time slice), and a change to a higher priority could cause a task switch.

 

[chiro]

Hey ksatria and welcome to the forums.

In addition to 2., usually you will have a pretty good idea of the amount of stack space for a thread by looking at the actual code that is involved for that thread.

Look especially at any recursive procedures that define data on the stack at each call because this is typically where stack-space gets eaten up for breakfast, and very quickly if you are not careful.

The other thing that is a bit more subtle, is to look if you are declaring things that should be on the heap but are for some reason or another, on the stack. Examples include huge matrices as one example or massive fixed strings.

If there are recursive procedures or things that do similar kinds of things with regard to hogging the stack, get an idea of worst case scenarios. This is done by knowing what the algoritm actually does and what kinds of data you deal with both typically and in a worse case scenario.

 

[ksatria]

...
1. Thread stack - In addition to the normal registers, whatever it takes to save (and later restore) the current state of the cpu is also saved on each task's stack.
<removed>...

nice explanation. thanks.
(i just notice that stack pointer is included in the general purpose registers, i.e. r13, will be saved; this is my original confusion on what is pushed to stack and how to tell the system to back to previous stack pointer (thread stack))

<removed>
3. A task is switched to executing to ready when a higher priority task is switched to. The higher priority task would have previousely been in wait for event (sleep) state. The switch from wait to ready could be due to the executing task signaling the waiting higher priority task, such as sending a message, or due an interrupt signaling the waiting higher priority task.
<removed>

what make me still unclear when a thread is executing, how come "suddenly" preempt by higher priority task (consider NOT by interrupt); while CPU is busy executing thread, then who do the job to decide another higher priority thread become ready and need to preempt currently executing thread (consider no time-slicing)? (consider no time-slicing, will higher priority thread have to wait until current thread suspend itself? as CPU busy executing current thread)


chiro, thanks for the nice tips!

 

[rcgldr]

I just notice that stack pointer is included in the general purpose registers, i.e. r13, will be saved; this is my original confusion on what is pushed to stack and how to tell the system to back to previous stack pointer.

You didn't mention which processor you're using. Assuming it's ARM, the current stack pointer is not normally stored on the stack, instead it's stored in a "task control block" (there is one task control block for each task), and only when there's going to be a task switch. There's also a cpsr (current processor state register) that has to be saved. There's a spsr (saved processor state register), used to save and restore the processor state.

what make me still unclear when a thread is executing, how come "suddenly" preempt by higher priority task (consider NOT by interrupt).

Assuming no time slicing, then the only way this occurs is if the current thread changes the state of the higher priority thread from waiting to ready (such as setting a mutex, or bumping the count on a semaphore, or sending a message, ...). This will cause an immediate task switch.

Normally when a task state is changed from waiting to ready, the OS will check to see if that task is higher priority than the currently running task, and if so, it will do a context switch to the higher priority task.

In the case of the ARM processor, there are duplicate registers for interrupt and fiq modes, including stack pointer (R13), and link register (R14). If a call from an interrupt handler changes the state of a higher priority task from waiting to ready, then it has to move any saved registers from the IRQ stack to the currently running task stack, then update the current task control block (where the task stack pointer is saved) so that it can exit via a common dispatcher.

 

[ksatria]

thanks again, rcgldr, for the nice explanation.
some topic you mention (like message queuing), I haven't reach that topic in my self-learning :D , so hope I will understand after I study that topic.


I have another thing I want to ensure.
Here is the sample code from books "Threadx RTOS", https://docs.google.com/file/d/0BzfYd0IyjrofREVSTnVvTWQwLVk/edit# for the thread description.

/* 02_sample_system.c

   Create two threads, one byte pool, and one mutex.
   The threads cooperate with each other via the mutex.  */


/****************************************************/
/*    Declarations, Definitions, and Prototypes     */
/****************************************************/

#include   "tx_api.h"
#include   <stdio.h>

#define     DEMO_STACK_SIZE         1024
#define     DEMO_BYTE_POOL_SIZE     9120


/* Define the ThreadX object control blocks...  */

TX_THREAD               speedy_thread;
TX_THREAD               slow_thread;

TX_MUTEX                my_mutex;

TX_BYTE_POOL            my_byte_pool;


/* Define thread prototypes.  */

void    speedy_thread_entry(ULONG thread_input);
void    slow_thread_entry(ULONG thread_input);


/****************************************************/
/*               Main Entry Point                   */
/****************************************************/

/* Define main entry point.  */

int main()
{

    /* Enter the ThreadX kernel.  */
    tx_kernel_enter();
}



/****************************************************/
/*             Application Definitions              */
/****************************************************/


/* Define what the initial system looks like.  */

void    tx_application_define(void *first_unused_memory)
{

CHAR    *pool_pointer;


    /* Create a byte memory pool from which to allocate
       the thread stacks.  */
    tx_byte_pool_create(&my_byte_pool, "my_byte_pool",
                        first_unused_memory,
                        DEMO_BYTE_POOL_SIZE);

    /* Put system definition stuff in here, e.g., thread
       creates and other assorted create information.  */

    /* Allocate the stack for the speedy thread.  */
    tx_byte_allocate(&my_byte_pool, (VOID **) &pool_pointer,
                     DEMO_STACK_SIZE, TX_NO_WAIT);

    /* Create the speedy_thread.  */
    tx_thread_create(&speedy_thread, "speedy_thread",
                     speedy_thread_entry, 0,  
                     pool_pointer, DEMO_STACK_SIZE, 5, 5,
                     TX_NO_TIME_SLICE, TX_AUTO_START);

    /* Allocate the stack for the slow thread.  */
    tx_byte_allocate(&my_byte_pool, (VOID **) &pool_pointer,
                     DEMO_STACK_SIZE, TX_NO_WAIT);

    /* Create the slow thread */
    tx_thread_create(&slow_thread, "slow_thread",
                     slow_thread_entry, 1, pool_pointer, 
                     DEMO_STACK_SIZE, 15, 15,
                     TX_NO_TIME_SLICE, TX_AUTO_START);

    /* Create the mutex used by both threads  */
    tx_mutex_create(&my_mutex, "my_mutex", TX_NO_INHERIT);

 
}


/****************************************************/
/*              Function Definitions                */
/****************************************************/


/* Entry function definition of the "speedy thread"
   it has a higher priority than the "slow thread" */

void  speedy_thread_entry(ULONG thread_input)
{

ULONG current_time;

   while (1)
   {
      /* Activity 1:  2 timer-ticks */
      tx_thread_sleep(2);

      /* Get the mutex with suspension */
      tx_mutex_get(&my_mutex, TX_WAIT_FOREVER);

      /* Activity 2:  5 timer-ticks  *** critical section *** */
      tx_thread_sleep(5);

      /* Release the mutex */
      tx_mutex_put(&my_mutex);

      /* Activity 3:  4 timer-ticks */
      tx_thread_sleep(4);

      /* Get the mutex with suspension */
      tx_mutex_get(&my_mutex, TX_WAIT_FOREVER);

      /* Activity 4:  3 timer-ticks  *** critical section *** */
      tx_thread_sleep(3);

      /* Release the mutex */
      tx_mutex_put(&my_mutex);

      current_time = tx_time_get();
      printf("Current Time: %5lu  Speedy Thread finished a cycle...\n",
              current_time);

   }
}

/****************************************************/

/* Entry function definition of the "slow thread"
   it has a lower priority than the "speedy thread" */

void  slow_thread_entry(ULONG thread_input)
{


ULONG current_time;

   while(1)
   {
      /* Activity 5 - 12 timer-ticks  *** critical section ***  */

      /* Get the mutex with suspension */
      tx_mutex_get(&my_mutex, TX_WAIT_FOREVER);

      tx_thread_sleep(12);

      /* Release the mutex  */
      tx_mutex_put(&my_mutex);

      /* Activity 6 - 8 timer-ticks  */
      tx_thread_sleep(8);

      /* Activity 7 - 11 timer-ticks  *** critical section ***  */
 
      /* Get the mutex with suspension  */
      tx_mutex_get(&my_mutex, TX_WAIT_FOREVER);

      tx_thread_sleep(11);

      /* Release the mutex  */
      tx_mutex_put(&my_mutex);

      /* Activity 8 - 9 timer-ticks  */
      tx_thread_sleep(9);

      current_time = tx_time_get();
      printf("Current Time: %5lu  Slow Thread finished a cycle...\n",
              current_time);

    }
}

the expected output is:
Current Time: 34 Speedy_Thread finished cycle...
Current Time: 40 Slow_Thread finished cycle...
Current Time: 56 Speedy_Thread finished cycle...
Current Time: 77 Speedy_Thread finished cycle...
Current Time: 83 Slow_Thread finished cycle...
Current Time: 99 Speedy_Thread finished cycle...
Current Time: 120 Speedy_Thread finished cycle...
Current Time: 126 Slow_Thread finished cycle...
Current Time: 142 Speedy_Thread finished cycle...
Current Time: 163 Speedy_Thread finished cycle...


Now I want to understand the number (of time-ticks) above, so I made a calculation of time spend by each threads, please click here; what I want to confirm is I can achieve the exact same number of time-ticks when the thread finish the cycle only if I assume both thread run at the same time (except in critical section), but in the code, the threads are created without time-slice; how that can be...?

Thanks!

 

[rcgldr]

Although not a problem in your case, you might want to put the printf's inside critical code sections so that one printf doesn't interrupt the other. Assuming that the 4th parameter in the create thread call is a priority, then the speedy thread will always run when it's ready, and the slow thread will only run when the speedy thread is in a sleep or waiting for a mutex.Time slicing is only used to share cpu time with threads of equal priority.

For something similar with Windows that includes a messaging interface for threads, I created a multi-threaded windows console application that copies a file. FIFO linked list messages are used to communicate between threads, with mutexes used for ownership of a message list, and semaphores for count of messages on a list. Windows has a WaitForMultipleObjects() function that I used to allow a thread to wait for ownership (mutex) and non-zero count (semaphore), (plus decrement the count once it's non-zero) in a single atomic (not interruptable) system call, which eliminates thread priority issues. There's some overhead in the setup but the actual thread code and the messaging functions are simple.

The code can be compiled using Visual C/C++ Express (free from Microsoft).

http://rcgldr.net/misc/mtcopy.zip

 

[ksatria]

Although not a problem in your case, you might want to put the printf's inside critical code sections so that one printf doesn't interrupt the other. Assuming that the 4th parameter in the create thread call is a priority, then the speedy thread will always run when it's ready, and the slow thread will only run when the speedy thread is in a sleep or waiting for a mutex.Time slicing is only used to share cpu time with threads of equal priority.

<removed>

thanks again, that bold statement really explain why the spreadsheet is match and correct. yes, immediately after speedy_thread has been executed, it's goes to sleep and then slow_thread (lower priority) get chance to be executed.


to all,
as I'm self-learning in RTOS, I may post the question from chapter of 'RTOS with ThreadX' book just for evaluation of my answer, as using this forum is one way to verify that my answer to problem :D , otherwise I can't measure my understanding.

 

[ksatria]

I have these problem sets, including my answer.

[chapter 3]

Q#1. When a thread is removed from the Suspended Thread List, either it is placed on the Ready Thread List or it is terminated. Explain why there is not an option for that thread to become the currently executing thread immediately after leaving the Suspended Thread List.

A#1. After leaving Suspended Thread List (if not terminated) the thread goes into Ready Thread List and not immediately become currently executing thread, because of the priority of other threads. Remember the selection of to-be-executed thread is base on FIFO and priority.​

Q#2 Suppose every thread is assigned the same priority. What impact would this have on the scheduling of threads? What impact would there be if every thread had the same priority and was assigned the same duration time-slice?

A#2. (a). We have to introduce Round-Robin scheduling so that the other threads will not wait until the currently executing thread finish. Simply if not it will become sequential execution base on FIFO or any wait-time-algorithm, i.e. A execute until finish then B execute until finish, and so on.
(b). So the scheduler will rotate the execution equally (in time) for each thread, seen as no waiting for each other’s (concurrently).​

Q#3 Explain how it might be possible for a preempted thread to preempt its preemptor? Hint: Think about priority inheritance.

A#3. By temporary change the priority, so preempted thread has higher priority than preemptor thread.​

Q#4 Discuss the impact of assigning every thread a preemption-threshold value of 0 (the highest priority).

A#4. No preemption will occurs then.​

Anyone challenged by the questions, please have your opinion :D

 

[rcgldr]

Q#1. When a thread is removed from the Suspended Thread List, either it is placed on the Ready Thread List or it is terminated. Explain why there is not an option for that thread to become the currently executing thread immediately after leaving the Suspended Thread List.

There should be an option. Take the case where the suspended thread is higher priority than the currently executing thread, and that the curently executing thread or an interrupt routine sets an event that the higher priority suspended thread is waiting for. In this situation, the RTOS code to handle set event should suspend the currently executing thread and immediately switch to the higher priority thread (making it the currently executing thread).

 

[rcgldr]

... In this situation, the RTOS code to handle set event should suspend the currently executing thread and immediately switch to the higher priority thread (making it the currently executing thread).

Too late to edit. This would be a pre-emptive context switch to the higher priority thread. What was the currently executing lower pirority thread would still be in the "ready" state.

 

[ksatria]

Too late to edit. This would be a pre-emptive context switch to the higher priority thread. What was the currently executing lower pirority thread would still be in the "ready" state.

From my understanding, the kernel will only choose the thread to be executed only from Ready List, as in this picture:
http://dl.dropbox.com/u/41059921/threadstatetransition.jpg
Will it RTOS dependent?
CMIIW

 

[ksatria]

And I'm also challenged by these questions, in mutex topic:

#C8Q6:
Suppose a mutex has the priority-inheritance option enabled and a thread that
attempted to acquire that mutex had its priority raised as a result. Exactly when will
that thread have its priority restored to its original value?

--> #C8A6: after the mutex is released, then the thread's priority will be restored.

#C8Q7:
Is it possible for the thread in the previous problem to have its priority changed while
it is in the Suspend Thread List? If so, what are the possible problems that might
arise? Are there any circumstances that might justify performing this action?

--> #C8A7:
the questions are not really clear to me, let's make an assumption: thread-A (priority=3*) own mutex-1, thread-B (priority=2) try to own mutex-1; then due to priority inheritances, priority of thread-A become 2 (inherit from thread-B).
*note: lower the number, higher the priority, e.g. priority=2 is higher than priority=3

so thread-B goes into Suspended List.
I don't see any problem by rising the priority of thread-B, it will make thread-B (faster) to be placed in Ready List, but once thread-B try to own mutex-1 (which is still owned by thread-A), again the thread-A's priority is raised to new thread-B's priority.
Am I correct?

Thanks for help!

 

[rcgldr]

... a pre-emptive context switch to the higher priority thread.

From my understanding, the kernel will only choose the thread to be executed only from Ready List.

Whenever the RTOS changes the state of a thread to ready, it should check to see if that thread is higher priority than the currently executing thread and if so, perform a pre-emptive context switch to the higher priority thread.

RTOS dependent?

In the case of a simple RTOS where each thread must have a unique and fixed (non-changeable) priority, then there is no need for thread lists. Instead an array of thread control blocks (or array of pointers) and a single word in memory with one bit per thread to indicate which threads are ready is sufficient (the bit number would correspond to priority). The advantage of this is that such an RTOS has less overhead.

By adding the rule that only one thread can wait for an event (mutex, semaphore, ...) at at time, the event structure can then include a pointer to the thread control block for the waiting thread (or zero if no thread is currently waiting on the event). This eliminates having to search through a list to see what thread is waiting for a particular event when the event is signaled. If multiple threads need to be signaled, then multiple events can be used to work with this restriction.

#C8Q7:Is it possible for the thread in the previous problem to have its priority changed while
it is in the Suspend Thread List?

This shouldn't be a problem. I assume that if a thread is in the suspended list, it's currently waiting (pending) on some event (mutex, semaphore, ...). If the thread is in the ready list, then the RTOS should check if that thread is now higher priority than the currently executing thread, and if so, do a context switch.