Operating Systems -Part III

This post emphasizes on a more efficient way of utilizing threads, commonly known as POSIX threads.

POSIX stands for Portable Operating System Interface, the threads created by this interface are portable on different platforms, as opposed to the threads created by calling system API clone() as explained in the previous post.
This interface has been specified by the IEEE POSIX 1003.1c standard.

POSIX threads library is known as libpthread library. This library provides certain basic routines:

1. pthread_create
2. pthread_join
3. pthread_detach
4. pthread_self
5. pthread_equal
6. pthread_kill
7. pthread_exit
8. pthread_attr_init
When a multi-threaded program starts executing, already one thread exists which runs the main() function. To create a new thread, program uses the pthread_create() API, as explained in the example below:

-------------------------------HELLO.c-------------------------------------------------------

#include        /* standard I/O routines                 */
#include      /* pthread functions and data structures */

/* function to be executed by the new thread */
void* PrintHello(void* data)
{
int my_data = (int)data;      /* data received by thread */

printf("Hello from new thread - got %d\n", my_data);
pthread_exit(NULL);   /* terminate the thread */
}

/* like any C program, program's execution begins in main */
int main(int argc, char* argv[])
{
int        rc;          /* return value                           */
pthread_t  thread_id;      /* thread's ID (just an integer)          */
int        t         = 11;  /* data passed to the new thread          */

/* create a new thread that will execute 'PrintHello' */
rc = pthread_create(&thread_id, NULL, PrintHello, (void*)t);
if(rc)   /* could not create thread */
{
    printf("\n ERROR: return code from pthread_create is %d \n", rc);
    exit(1);
}
printf("\n Created new thread (%d) ... \n", thread_id);

pthread_exit(NULL);  /* terminate the thread */
}

----------------------------------------------------------------------------------------------

1. Inside main, declare a variable of type pthread_t.

2. Call pthread_create() API to bring life to a new thread.

3. pthread_create() takes 4 arguments:

1. Thread id.
2. Attributes for the new thread, If NULL pointer is passed, it sets the default values as attributes.
3. 3rd argument is the function name to be executed by the new thread.
4. 4th argument holds the arguments required by the function passed as argument 3.

4. After pthread_create successfully returns, the program has 2 running threads.

5. The call to pthread_exit causes the current thread to exit and free any thread-specific resources.

In previous posts, we understood the unpredictable timings at which threads are invoked.
pthread_join() API ensures that all the threads are executed before the ma

in thread dies.

But still the uncertainty prevails regarding the execution order of all the threads created by the main thread.

Mutex, condition variables and semaphores come handy for synchronization of threads which can further prevent deadlocks.

MuTex: ( Mutual Exclusion )

Think of mutex as a key for a lock.

Even if there are 2 running threads, we need a mutex, so that the other thread does not get access to a certain section of code, until the first thread has finished its task.

Question - Answer Round:

1. Think of scenarios where mutex will also fail

2. Think os scenarios where mutex is mandatory

3. Does mutex make code more efficient to use?

OS Concepts Part-II

OS concepts gave some idea about threads.
To understand threads more, it is important to understand how threads are different from processes.
Consider different colored threads: red blue, white, purple existing together to give shape to a hand-knit embroidery.

Each thread has a unique existence and at the same time co-exist while using the resources provided in the process of carving out a multi-threaded embroidery.

In the world of Operating Systems, many threads map to one process, while sharing the resources of a single process in multi-threaded environment.
IPC mechanism exist for the communication of 2 processes, whereas 2 threads can easily communicate with each other as they share the same address space, code and data segments. Each thread maintains its own copy of stack and PC and SP registers along with some storage space for local variables.

UNIX supports multiple user process but only supports one thread per process, whereas Solaris supports multiple threads per process. High and cheap degree of parallelism is often achieved via the usage of threads. In an embedded SQL application, each session denotes a thread. The program creates as many sessions as there are threads. This way we can realize that each thread opens up a unique point of execution. An attempt has been made to explain it more in the examples below:

Example 1 : A file server on a LAN

• It needs to handle several file requests over a short period
• Hence more efficient to create (and destroy) a single thread for each request
• Multiple threads can possibly be executing simultaneously on different processors

Example 2: Matrix Multiplication

Matrix Multiplication essentially involves taking the rows of one matrix and multiplying and adding corresponding columns in a second matrix i.e:

Matrix Multiplication (3x3 example)

Note that each element of the resultant matrix can be computed independently, that is to say by a different thread.

Lets try to understand the attributes which further differentiates one thread from the other. These attributes can be set at the time of the creation of the thread or changed when the thread is in running mode:

1. Priority:

As the name suggests, this affects the amount of processing time that the system gives the thread before letting another thread interrupt it.

2. Stack Size:
This parameter decides the number of function calls made by the thread permitted within its stack space.

3. Name:
Each thread is associated with a unique name, something that helps in debugging or tracking the thread in its workspace.

4. Scheduling Policy:
The policy decides how various threads are scheduled within the system.

5. Thread State:
A thread's state indicates what the thread is doing and what it is capable of doing at a particular instance. it is running, waiting for resources or sleeping ??

6. Thread Stack Guard Size:
Most thread implementations add a region of protected memory to a thread's stack, commonly known as a guard region, as a safety measure to prevent stack pointer overflow in one thread from corrupting the contents of another thread's stack.

7. Scope:
This attribute defines the scope or the visibility area of the thread.

8. Detach State:
This attribute defines how a thread leaves the associated active sources during its termination.

Next task is to understand how a thread is created in Linux:

On Linux, kernel threads are created with the clone system call. Clone API specifies which resources should be shared. It shares memory space, file descriptors and signal handlers.


The first step is to decide the optimum stack size to be used by the thread.
The SP (stack counter) passed to clone must refer to the top of the chunk of memory, since on most processors the stack goes down.
To avoid a memory leak, the stack must be freed once the thread has exited. For better understanding, here is a snippet of simple clone program from Linux magazine:

___________________________________________________________________

#include

#include

// 64kB stack
#define FIBER_STACK 1024*64

// The child thread will execute this function
int threadFunction( void* argument )
{
printf( "child thread exiting\n" );
return 0;
}

int main()
{
void* stack;
pid_t pid;

// Allocate the stack
stack = malloc( FIBER_STACK );
if ( stack == 0 )
{
perror( "malloc: could not allocate stack" );
exit( 1 );
}

printf( "Creating child thread\n" );

// Call the clone system call to create the child thread
pid = clone( &threadFunction, (char*) stack + FIBER_STACK,
SIGCHLD | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_VM, 0 );
if ( pid == -1 )
{
perror( "clone" );
exit( 2 );
}

// Wait for the child thread to exit
pid = waitpid( pid, 0, 0 );
if ( pid == -1 )
{
perror( "waitpid" );
exit( 3 );
}

// Free the stack
free( stack );

printf( "Child thread returned and stack freed.\n" );

return 0;
}

_____________________________________________________________________

Simple clone Thread Example

Lets have a look at clone API in more detail.

clone( &threadFunction, (char*) stack + FIBER_STACK,
SIGCHLD | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_VM, 0 );

Remember, the main use of clone is to create multiple threads in a program that run concurrently in a shared memory space.

When a thread is created, it starts executing the function (&threadFunction).
0 represents the arguments passed to the function. These can be variable in number.
When the function returns, the thread terminates.

(char*) stack + FIBER_STACK specifies the location of the stack used by the thread. The calling process must create memory space for the thread stack and pass a pointer to this space to clone().

SIGCHLD | CLONE_FS | CLONE_FILES | CLONE_SIGHAND | CLONE_VM
These represent the flags, the lower byte of the flags contains the number of the termination signal sent to the parent when the thread dies.
Here SIG stands for signal and CHLD stands for child, signifying that the child process has terminated.

Here flags are bit-wise ORed to specify the shared resources:
CLONE_FS: It specifies that the file-system is shared.

CLONE_FILES: It specifies that the file-descriptor table is shared.

CLONE_SIGHAND: It specifies the sharing of same table of signal handlers.

CLONE_VM:It specifies that the created thread runs in the same memory space as the calling process.

Time for Question-Answer session again:

1. 1 process can have 100 threads.
Two child processes are created each having 40 and 60 are formed.
What is the probability that:

a. 2 threads enter the same child process?
b. 2 threads enter the different child process?

2. What are the disadvantages of using threads over processes?

3. Define the 3 possible main stages in which a thread can be?

4. What role does a thread play in contributing to parallel processing inside a multi-processor?

5. How can one ensure that all the threads of a process co-exist at a particular instance?

6. What are the tools required to program with threads?

7. Name some OS which support thread programming?

8. What makes threads such an interesting read ??

OS Concepts Part -1

How helpless we all feel when any of our electronic devices stops working all of a sudden and shows no immediate sign of recovery..

This post helps us understand this master clock better; the one which drives electronic hardware at one end and the user at the other..

In the jargon of computers, we term this master clock as Operating Systems!!




During my primary education, the first OS i was introduced to was MS-DOS.

It is a non-graphical single user operating system by Microsoft primarily meant for desktop computers, developed over Intel 8086 micro processor. The high-level programming language used was BASIC (Beginnner's All-purpose Symbolic Instruction Code )

MS-DOS gave a alphabetic notation to each hard drive: C used to be the boot disk, A was primarily meant for floppies, D used to be the CD Driver.

MS-DOS provides a text based command line interface unlike the later operating systems like Microsoft ME, NT, 2000 or XP which provide a graphical user interface.

As i moved to the college, i was thrown to some more jargons, with quite complex names i would say, whose correct pronunciation i am still not aware of: Linux, Solaris, Unix.....



At the first go, these OS looked quite un-user friendly to me!
Unix to me looked like a hierarchy of file system with certain paths pre-stored in the user profile, something that provides lot many shells to work in; e.g. the bash shell.



UNIX OS was developed by Bell Labs to address the compatibility issues posed by the usage of various PC vendors. They gifted the computer world a special code known as Kernel, written in a middle language C.

Linux provides a great package of C compliers, libraries, man help pages, development and debugging tools. It can be downloaded completely free from the internet.

"De gustibus et coloribus non disputandum est": there's a Linux for everyone.

Solaris on the other hand, is a multi-tasking, multi-processing UNIX-based operating system designed by SUN microsystems.

Remember, all these Unix based OS are case-sensitive, which sounds complex but then makes the system more secure !

When i joined DSP group in my company Aricent 4 years back, i was informed that all GSM products here are developed on 2 RTOS (real time operating system ) BIOS and QNX ???

Wikipedia enlightened me further that RTOS is a multi-tasking operating system intended for real-time applications like mobiles, robots and spacecrafts. The response time in RTOS is quite less, not even within our imagination.
Imagine, 2 people talking on the phone: say one is in New Jersey and the other is in Saudi Arabia. As soon as the guy from the west utters a word, the mind of the guy in the east immediately starts processing the input.



To meet such tight time constraints, RTOS will even need to drop data at times. In terms of GSM, every meaningful bunch of data is transmitted every 477 us. RTOS works on a lot many threads which can be further prioritized.

What is this 'thread' now ??

As defined in whatis.com, a thread is the information needed to serve one individual user or a particular service request. If multiple users are using the program or concurrent requests from other programs occur, a thread is created and maintained for all of them.

Now many thread can be contained inside one process sharing some common resource, say all the pages which need to be printed are a part of the I/O process all sharing the printer software queue buffer.

Computer users take it for granted that their systems can do more than one thing at a time. We play songs, check e-mails, video chat on yahoo messenger, review an adobe document & produce L1 code using TI CCS studio almost at the same time..)

Processing time for a single processor is shared among processes and threads. That signifies why multi processors always remain in such a high demand!

Every thread has a priority. Threads with higher priority are more important to a process and should be allocated processor time before lower priority threads.

When a higher priority thread enters the ready state, the operating system generally pre-empts the currently running thread. This operation is known as 'pre-emptive scheduling'.

Now a higher priority thread could indefinitely postpone the execution of lower priority threads. This indefinite postponement is in one word described as 'starvation'.

Any thread will not always remain in action. It always has some sleep interval. Threads sleep when they momentarily do not have work to perform. e.g. a word processor thread periodically writes a copy of the current document to disk for recovery purposes. This thread sleeps for sure in between those successive backups..)

Now lets try to understand further what would happen when two different threads, acting on the same data interfere! It somewhere reflects that both the threads follow just one algorithm and some of their steps overlap.

Consider a simple class called Counter:

class Counter {
 private int c = 0;

 public void increment() {
     c++;
 }

 public void decrement() {
     c--;
 }

 public int value() {
     return c;
 }

}

As explained in the code segment above, increment API() adds 1 to variable c and decrement API() subtracts 1 from c.

Suppose Thread A invokes increment at about the same time Thread B invokes decrement. If the initial value of c is 0, their interleaved actions might follow this sequence:

1. Thread A: Retrieve c.
2. Thread B: Retrieve c.
3. Thread A: Increment retrieved value; result is 1.
4. Thread B: Decrement retrieved value; result is -1.
5. Thread A: Store result in c; c is now 1.
6. Thread B: Store result in c; c is now -1.

Thread A's result is lost, overwritten by Thread B. This particular interleaving is only one possibility. Under different circumstances it might be Thread B's result that gets lost, or there could be no error at all. Because these are unpredictable, thread interference bugs can be difficult to detect and fix.

What is the key to avoiding such memory inconsistency errors ???

Well, the answer in one word would be "Synchronization", something that i will ponder upon in detail in my next post!

It's time now to do a quality check and see how many questions we can answer -:)

1. Give examples of two situations in which user convenience conflicts with efficient use of a computer system.

2. Comment on validity of the following statement: "A dormant program also consumes resources."

3. An OS cannot meet the response requirement of a real time application if it is executed as a single process.Explain with an example how creation of multiple processes can help to meet the response requirements of the application in the same OS ?

4. If two independent events e1 and e2 have the probability of occurrence of pr1 and pr2, where both pr1 and pr2 <1, the probability that both events occur at the same time is pr1 * pr2. A computer system containing two CPUs is to be designed that the probability that both CPUs fail is 1 in 10000. What should be the probability of failure of a CPU?
.
.
5. An application is to be coded using threads. Describe the conditions under which you would recommend use of
.
(a) kernel-level threads
.
(b) user-level threads