[SOLVED] COMPSCI 340 / SOFTENG 370 Assignment 1 Making Threads

COMPSCI 340 / SOFTENG 370

Operating Systems Assignment 1 Making Threads

Worth 7%
final date 11:59pm 21st of August, 2017

Introduction

User level threads are surprisingly easy to make, as long as the operating system provides a few basic requirements. In this assignment you are going to finish writing a thread library using some of the standard Unix system calls.

Threads without preemption

The file OSA1.c is a program which creates a thread, executes that thread and then on completion of the thread returns to the main function (which is executing in a sort of thread too).

This program runs fine on the Mac and Linux (including the Windows Subsystem for Linux). However I recommend using Linux in the lab or in a virtual machine because later parts of the assignment (in particular Part3) become OS dependent. The markers will test the programs on the lab Linux image.

Compile and run the program either from the command line:

gcc OSA1.c -o OSA1./OSA1

or from within an IDE such as Eclipse. I recommend the command line.

In this case there was no need for a thread as the main function merely waits for the thread to finish before it finishes, just like a very fancy subroutine call. However by the end of the assignment you will have a proper pre-emptive threading system.

The first thing you need to do is to read and understand the code in OSA1.c. I will also cover this in lectures. What is a thread?

The littleThread.h header file defines a thread structure as:

typedef struct thread {int tid;

void (*start)();jmp_buf environment;enum state_t state;void *stackAddr;struct thread *prev;struct thread *next;

} *Thread;

// thread identifier// the start function// saved registers// the state

// the stack address// pointer to the previous thread// pointer to the next thread

So a thread has a unique identifier tid (the first thread is 0, add 1 for each subsequent thread), a start function, this is the function which gets called when the thread begins executing. It has an environment (which is used by setjmp and longjmp), a state, the address of the bottom of the threads stack stackAddr and pointers to previous and next threads (not used in OSA1.c at the moment but you will have to use them). The thread states are simply: SETUP, RUNNING, READY, and FINISHED. SETUP means that the thread is in the process of being created or setup. READY means the thread is all set to run but it is not running. RUNNING and FINISHED are obvious.

The environment of a thread includes the values of the processors registers so that the thread can resume after not running for a while. See the section on setjmp and longjmp later in this handout.

Page1 of 8

The code for the thread is in threads0.c. This way the markers can supply different threads to test your code.

What about the stack?

Each thread requires its own stack. This could be allocated by reserving some space in memory and then setting the stack pointer register to the top of this space. However there is a way of doing this without having to use any assembly language.

When signals are sent to Unix processes they normally execute the signal handler on the normal user stack, but it is possible to request that when a signal handler is called it uses an alternate stack. This is partially set up in the setUpStackTransfer function.

The createThread function allocates space for the stack (and the thread structure). Before it sends a signal to the current process with the kill system call it also makes the new stack for the thread act as the signal stack, using the sigaltstack function.

Then when the SIGUSR1 signal is received it will cause the process to jump to the handler function associateStack using the new stack for this function.

Each Part

There are 3 parts to this assignment. Do each part in its own directory: Part1, Part2, Part3. Each directory must have your source code for the part: OSA1.1.c, OSA1.2.c, OSA1.3.c, the unmodified header littleThread.h and the example thread file for the part: threads1.c, threads2.c, threads3.c.

When the markers are testing your code they will first run each part using the code you provide then they will replace the threads?.c files with other thread files to make sure your code works with different threads and different numbers of threads.

Part 1

Take OSA1.c change its name to OSA1.1.c and put your name and login/UPI in the opening comment. You have to change the code so that if multiple threads are created they will be switched between as each thread finishes. There is no pre-emption. After all threads have finished, execution returns to the main function and the process stops. You can change the existing code in any way you like as long as it still works in the same way. You will certainly have to change the switcher function.

You should keep all created threads in a circular linked list (that is what the prev and next pointers are for in the thread struct). You will need to keep track of the current thread (the thread currently running), this will initially be the first thread created. Always insert new threads at the end of the list. Each thread must have a unique thread identifier.

The main thread (the one executing the main function) is different, it doesnt have an identifier and should not be inserted in the circular list of threads. It should only be returned to when there are no other threads still able to run.

When the currently running thread finishes you need to remove it from the list and switch to the next thread in the list. You must free the stack space of all finished threads. Keep the message saying you are disposing of the stack space for the finished thread. Do not free the thread structure memory as you need this to print the state of the thread.

Add a scheduler function called scheduler to choose the next thread to run. You need to ensure that all thread states are correct. e.g. Threads which have completed have their state changed to FINISHED, threads which are waiting to run are READY and only the currently executing thread is RUNNING.

Add a new function printThreadStates which prints out the thread ids and the state of each thread in the order they were created. The const NUMTHREADS is the number of threads created. Output should look like this:

Thread States=============

Page2 of 8

threadID: 0 state:runningthreadID: 1 state:ready

In this case thread 0 is the current thread, and hence running, and thread 1 is ready to run. Even when threads have finished their state should still be shown by the printThreadStates function.

Call the printThreadStates function whenever there is a switch to a new thread. Also call it after creating the threads but before any of them are started, and one last time just as the process finishes.

The output when using the threads1.c file must be like this (extra empty lines and spaces can be ignored): robert@ubuntu:Part1$ ./OSA1.1

Thread States=============threadID: 0 state:readythreadID: 1 state:ready

switching to first thread

Thread States=============threadID: 0 state:runningthreadID: 1 state:ready

hi hi hi hi hi

disposing 0

Thread States=============threadID: 0 state:finishedthreadID: 1 state:running

byebyebyebyebye

disposing 1

back to the main thread

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finished

Part 2

Copy OSA1.1.c from Part 1 and save it as OSA1.2.c. Use the thread2.c file for the threads. Add a threadYield function to OSA1.2.c which will call the scheduler. This should immediately stop the current thread from running and start up the next READY thread in the circular linked list. If the current thread is the only existing READY thread then it continues.

Page3 of 8

The output should look like this:

robert@ubuntu:Part2$ ./OSA1.2

Thread States=============threadID: 0 state:readythreadID: 1 state:readythreadID: 2 state:ready

switching to first thread

Thread States=============threadID: 0 state:runningthreadID: 1 state:readythreadID: 2 state:ready

hi

Thread States=============threadID: 0 state:readythreadID: 1 state:runningthreadID: 2 state:ready

bye

Thread States=============threadID: 0 state:readythreadID: 1 state:readythreadID: 2 state:running

bye

Thread States=============threadID: 0 state:runningthreadID: 1 state:readythreadID: 2 state:ready

hi

Thread States=============threadID: 0 state:readythreadID: 1 state:runningthreadID: 2 state:ready

bye

Thread States=============threadID: 0 state:readythreadID: 1 state:readythreadID: 2 state:running

bye

Thread States=============threadID: 0 state:runningthreadID: 1 state:readythreadID: 2 state:ready

Page4 of 8

disposing 0

Thread States=============threadID: 0 state:finishedthreadID: 1 state:runningthreadID: 2 state:ready

disposing 1

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finishedthreadID: 2 state:running

disposing 2

back to the main thread

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finishedthreadID: 2 state:finished

Part 3

All we need to add now is a way of pre-empting a running thread to enable other threads to get a turn. We can do this with another signal. Look up how to use setitimer to send a signal to your process every 20 milliseconds (how many microseconds?). This is where the assignment becomes OS dependent. You must use ITIMER_VIRTUAL and its corresponding signal SIGVTALRM.

Save the program either from Part 1 or Part 2 as OSA1.3.c . Add setUpTimer and a call to it, just before starting the threads in threads3.c. The output should show all three threads taking turns running, similar to this:

robert@ubuntu:Part3$ ./OSA1.3

Thread States=============threadID: 0 state:readythreadID: 1 state:readythreadID: 2 state:ready

switching to first thread

Thread States=============threadID: 0 state:runningthreadID: 1 state:readythreadID: 2 state:ready

... (lots of missing output)

Thread States=============threadID: 0 state:runningthreadID: 1 state:readythreadID: 2 state:ready

hi1296337872hi

Page5 of 8

Thread States=============threadID: 0 state:readythreadID: 1 state:runningthreadID: 2 state:ready

bye

... (lots of missing output)

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finishedthreadID: 2 state:running

910746567

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finishedthreadID: 2 state:running

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finishedthreadID: 2 state:running

bye767147961disposing 2

back to the main thread

Thread States=============threadID: 0 state:finishedthreadID: 1 state:finishedthreadID: 2 state:finished

The output will be different every time the program is run.

Questions (put the answers to these in a file called A1answers.txt) Question 1

There is a comment saying Wow! in the switcher function in OSA1.c. This is to indicate something very bad is happening here. Explain what it is.

Question 2

Why are the time consuming calculations in threads3.c required in order to demonstrate the effectiveness of the pre-emptive scheduler?

Question 3

In threads3.c there is some code around the call to rand() to block signals and then allow them again. Explain what can happen if this is not done. Also give an explanation as to why this can happen.

Page6 of 8

Extra info

There are definitely differences in the behaviour of programs like this on different Unix/Linux operating systems. For this reason you eventually have to get your solution working on the lab image of Linux.

As one example, I found that the Windows subsystem for Linux wouldnt allow me to use ITIMER_VIRTUAL when calling setitimer, I had to use ITIMER_REAL instead. Whereas ITIMER_VIRTUAL worked fine on an Ubuntu virtual machine on my Mac.

Remember that the Unix man command gives very useful information about system and C function calls, in particular for this assignment: malloc, sigaction, sigaltstack, setitimer, kill

setjmp and longjmp

The C functions setjmp and longjmp are used to store the current environment (actually the registers) and restore them at a later time. This means we can effectively store the computation of a thread at this point and then come back to this point when we want to. Just what we need to freeze and unfreeze a thread. But because C uses a stack to keep track of function calls (the corresponding arguments, local variables and return addresses) we must make sure that longjmp is called before the stack has lost or overwritten the position where setjmp was called.

setjmp(thread->environment)

will save the current registers in the environment field of the thread structure. When setjmp is called it returns 0. When we come back to exactly the same position in the code because of the matching longjmp we can return another value (traditionally 1) so that we can do different things when we return.

longjmp(thread->environment, 1);

In this way a thread can be setup to run by skipping the code to call its start function when the return value from setjmp is zero. When we do a longjmp with one as the return value back to the same point the threads start function is executed. See the associateStack and switcher functions in OSA1.c .

Part 4 Extra for Experts (just because you can)

Save your OSA1.3.c file as OSA1.4.c in a Part4 directory and modify it in the following way. Rather than use the clever but hacky system to set up a new stack for each thread using an alternate signal stack, you have to descend into the murky depths of assembly language to modify the stack pointer directly.

You will have to look up inline assembly on the Web in order to change the stack pointer for each thread. Remove all the unnecessary pieces of code which are to do with alternate signal stacks and the associated

kill call.
You could also use setcontext and getcontext for switching between contexts rather than using

setjmp and longjmp. Submit

Zip up all of your solutions into one file (Part1, Part2, Part3 (and possibly Part4) directories and the A1answers.txt file).

Submit the zipped file to Canvas. If you resubmit Canvas adds a suffix to the filename. Do not worry about this.

Remember: Your code is going to be tested on the Linux lab image. If your code does not run correctly in this environment you will not get the marks :(.

Include your name and UPI in all files.

Page7 of 8

Marking guide (28 marks = 7%)

Students name and UPI in every file.

Part 1 OSA1.1.c

There is only the one call to the switcher function in the main function.
There is a simple scheduler function which selects the next thread to run. The threads are

maintained in a circular linked list.
The stack space for a thread is freed when the thread completes.

1 mark

1 mark

1 mark

1 mark

There is a printThreadStates function which prints out the state of all threads in the order of creation of the threads. Even finished threads are shown.

Works correctly using given threads1.c. Works correctly using different threads1.c.

Part 2 OSA1.2.c

2 marks 2 marks 2 marks

There is a threadYield function which schedules the next thread to run.
Works correctly using given threads2.c. The program terminates cleanly by returning to the main

function when the threads have all finished. Works correctly using different threads2.c.

Part 3 OSA1.3.c

1 mark

1 mark 2 marks

Using given threads3.c the program output shows that the threads are being pre-empted.
The program terminates cleanly by returning to the main function when the other threads have all

finished.
Works correctly using different threads3.c.

Part 4 OSA1.4.c (no marks but lots of fun)

Question 1 Question 2 Question 3

2 marks

1 mark 2 marks

3 marks 2 marks 4 marks

Page8 of 8