Operating System FAQS

What is Re-entrant Function?

The term "re-entrant" means that it is safe to "re-enter" the function while it is already executed, typically in a concurrent environment.

In other words, when two tasks can execute the function at the same time without interfering with each other, then the function is re-entrant.

A function is not re-entrant when the execution by one task has an impact on the influence of another task. This typically is the case when a global state or data is used.

A function that uses only local variables and arguments is typically re-entrant.

Basic guidelines:

• Do not access mutable global or function-static variables.
• Do not self-modify code.
• Do not invoke another function that is itself non-reentrant.

For example, the following function is not reentrant, because the observed value of the summation depends on when and where the function is interrupted (or, in the case of multithreading, how two or more threads race into the function):

1 2 3 4 5 6

static int sum = 0; int increment(int i) {   sum += i;   return sum; }

We can make this function reentrant by making the sum not a global variable and instead requiring the caller to maintain it:

1 2 3

int increment(int sum, int i) {     return sum + i; }

Returning data

Many non-reentrant functions return a pointer to static data. This can be avoided in the following ways:

• Returning dynamically allocated data. In this case, it will be the caller's responsibility to free the storage. The benefit is that the interface does not need to be modified. However, backward compatibility is not ensured; existing single-threaded programs using the modified functions without changes would not free the storage, leading to memory leaks.
• Using caller-provided storage. This method is recommended, although the interface must be modified.

For example, a strtoupper function, converting a string to uppercase, could be implemented as in the following code fragment:

/* non-reentrant function */
char *strtoupper(char *string)
{
        static char buffer[MAX_STRING_SIZE];
        int index;

        for (index = 0; string[index]; index++)
                buffer[index] = toupper(string[index]);
        buffer[index] = 0

        return buffer;
}

A better solution consists of modifying the interface. The caller must provide the storage for both input and output strings, as in the following code fragment:

/* reentrant function (a better solution) */
char *strtoupper_r(char *in_str, char *out_str)
{
        int index;

        for (index = 0; in_str[index]; index++)
        out_str[index] = toupper(in_str[index]);
        out_str[index] = 0

        return out_str;
}

The non-reentrant standard C library subroutines were made reentrant using caller-provided storage.

 

Making a function threadsafe

In multithreaded programs, all functions called by multiple threads must be threadsafe. However, a workaround exists for using thread-unsafe subroutines in multithreaded programs. Non-reentrant functions usually are thread-unsafe, but making them reentrant often makes them threadsafe, too.

Locking shared resources

Functions that use static data or any other shared resources, such as files or terminals, must serialize the access to these resources by locks in order to be threadsafe. For example, the following function is thread-unsafe: 

/* thread-unsafe function */
int increment_counter()
{
        static int counter = 0;

        counter++;
        return counter;
}

To be threadsafe, the static variable counter must be protected by a static lock, as in the following example:

/* pseudo-code threadsafe function */
int increment_counter();
{
        static int counter = 0;
        static lock_type counter_lock = LOCK_INITIALIZER;

        pthread_mutex_lock(counter_lock);
        counter++;
        pthread_mutex_unlock(counter_lock);
        return counter;
}

 

Writing reentrant and threadsafe code

In single-threaded processes, only one flow of control exists. The code executed by these processes thus need not be reentrant or threadsafe. In multithreaded programs, the same functions and the same resources may be accessed concurrently by several flows of control.

To protect resource integrity, code written for multithreaded programs must be reentrant and threadsafe.

Reentrance and thread safety are both related to the way that functions handle resources. Reentrance and thread safety are separate concepts: a function can be either reentrant, threadsafe, both, or neither.

Example 1: not thread-safe, not reentrant

/* As this function uses a non-const global variable without
   any precaution, it is neither reentrant nor thread-safe. */

int t;

void swap(int *x, int *y)
{
    t = *x;
    *x = *y;
    *y = t;
}

Example 2: thread-safe, not reentrant

/* We use a thread local variable: the function is now
   thread-safe but still not reentrant (within the
   same thread). */

__thread int t;

void swap(int *x, int *y)
{
    t = *x;
    *x = *y;
    *y = t;
}

Example 3: not thread-safe, reentrant

/* We save the global state in a local variable and we restore
   it at the end of the function.  The function is now reentrant
   but it is not thread safe. */

int t;

void swap(int *x, int *y)
{
    int s;
    s = t;
    t = *x;
    *x = *y;
    *y = t;
    t = s;
}

Example 4: thread-safe, reentrant

/* We use a local variable: the function is now
   thread-safe and reentrant, we have ascended to
   higher plane of existence.  */

void swap(int *x, int *y)
{
    int t;
    t = *x;
    *x = *y;
    *y = t;
}


What is Priority Inversion problem?

Before discussing about priority inversion problem, I would like to emphasize when this problem occur in  Real time operating system.

A real time system running with priority based scheduler,  if two tasks share the same resources( such as memory buffer) ,obviously one of the task have a HIGH priority.  The higher-priority task expects to be run as soon as it is ready.

However, if the lower-priority task is using their shared resource when the higher-priority task becomes ready to run,the higher-priority task must wait for the lower-priority task to finish with it. We say that the higher-priority task is pending on the resource.

The real trouble arises at run-time, when a medium-priority task preempts a lower-priority task using a shared resource on which the higher-priority task is pending.

If the higher-priority task is otherwise ready to run, but a medium-priority task is currently running instead, a priority inversion is said to occur.

Low-priority Task L and high-priority Task H share a resource.

Shortly after Task L takes the resource, Task H becomes ready to run.

However, Task H must wait for Task L to finish with the resource, so it pends. Before Task L finishes with the resource,Task M becomes ready to run, preempting Task L. 

While Task M (and perhaps additional intermediate-priority tasks) runs,

Task H, the highest-priority task in the system, remains in a pending state.

How to solve this problem?

The solution is Priority inheritance

The first is called priority inheritance. This technique mandates that a lower-priority task inherit the priority of any higher-priority task pending on a resource they share.

This priority change should take place as soon as the high-priority task begins to pend; it should end when the resource is released. This requires help from the operating system.