PA 8001 2013 Practical 2

Objectives

There are three main objectives for this practical:

• Learn about and implement the basic ingredients for concurrency,

• Implement the mutual exclusion primitives,

• Use them in implementing a simple access control protocol

Instructions

Submit a single .zip file on blackboard with four folders, each containing the solutions to the below-specified parts.

For each function in the code, you need to write a piece of comment, describing its pre- and post-condition and one or more test-cases.

In order to make the on-board processor run at its maximum speed, its CPU clock prescaler functionality must be disabled. This is achieved by writing the byte values 0x80 followed by 0x00 to the special register CLKPR when your program starts up. See the ATmega169 manual, pages 29-31, for further info.

Part 1: Yield

Download the tiny threads library and run the sample program test1 on the butterfly. Notice that only one thread in the sample program gets to execute. This is so because there is no way of switching context: there is no invocation to yield() in the program and furthermore, there is no implementation for yield(). In this exercise you will implement the function

yield() 

in tinythreads.c. The function should

• enqueue the current thread in the ready queue (as you can see in the source file tinythreads.c there are functions already implemented for enqueuing and dequeuing).

• pick the first element in the queue, dequeue it and dispatch it! It is dispatch that makes the context-switch trick! (check the definition of dispatch).

Note that, care is taken that interrupts are disabled when manipulating the queues. See to it that you do so too in the implementation of yield(). You can test your implementation of yield() by inserting an invocation to yield() in the test program after printAt() (print a prime number and yield). If your implementation is correct each thread will get to compute the next prime number and show it on the LCD before switching to the other thread.

Part 2: Time Slicing

The purpose of introducing threads was to let independent mains interleave automatically. One way of doing this is by letting the kernel itself call yield() at regular intervals (a technique called time-slicing). In order to achieve this you will have to configure the hardware so that it generates interrupts at desired intervals and you will have to handle these interrupts by calling yield(). Because both timers and interrupts might be new to you, we suggest that you do this in two steps: first learn to handle interrupts using the joystick for producing the interrupts, and then learn how to configure a timer.

Install a handler for the SIG_PIN_CHANGE1 interrupt (this is defined in

avr/interrupt.h 

and is vector nr. 4). This is done by using the macro ISR with the vector as argument instead of a function header. What is to be done when the interrupt occurs is similar to an arbitrary C function. Do this in

tinythreads.c, 

not in the application program. A SIG_PIN_CHANGE1 interrupt can be generated by pressing the Butterfly joystick in the downward direction, if the logical interrupt source PCINT15 is enabled in mask registers EIMSK and PCMSK1. PCINT15 corresponds to a change on pin 7 of PORTB.

Note 1: to achieve proper operation of the joystick, a pull-up resistor must be activated by setting the corresponding output pin to 1; (recall lab 1 instructions for further info.) Note 2: a SIG_PIN_CHANGE1 interrupt will be generated each time the joystick's downward switch changes state; if you want the current thread to yield only each time the switch is actually depressed (and not when it is released),

you should test the current status of PORTB bit 7 before calling yield() from within your interrupt handler. See pages 51-54 of the ATmega169 manual for more details on external interrupts, and the include file

avr/iom169.h 

for a definition of the available interrupt sources.

Any initalization code required in in this step can preferably be put in the local function

initialize() 

of tinythreads.c.

Try your implementation by uploading the program and producing context-switches using the joystick (remember to remove the calls to yield() from the test program!)

Now that you know how to install interrupt handlers, you will configure a timer to generate interrupts. Configure the 16-bit Timer/Counter1 to generate a SIG_OUTPUT_COMPARE1A interrupt (vector no. 8) with a period of 50 ms. To do so you must set the the timer to Clear on Timer Compare (CTC) mode, and write a suitable value to the timer compare register OCR1A. With a system clock of 8 MHz, a timer prescaling factor of 1024 is recommended. It is also advisable to force the timer to start its first cycle from zero by clearing the TCNT1 register during initialization. Moreover, timer output compare A interrupts must be enabled by setting the corresponding bit in register TIMSK1. Documentation of the registers involved can be found in pages 117-123 of the ATmega169 manual. Try your implementation by uploading the test program to the butterfly!

Part 3: Mutual Exclusion

We will now address the problem of mutual exclusion by implementing the functionality of mutex variables. To obtain clear evidence why mutual exclusion may be needed in a concurrent system, we will consider the test1.c program once more. Start by moving the declaration of variable pp in function printAt() to the global level of file test1.c. This turns the body of printAt() into a critical section, as the same variable pp will now be shared between concurrent calls to the function.

Notice the effect on the display when running your modified test program. Should you have problems noticing any odd effect at all, you can experiment by inserting a loop that simply increments a local variable 1000 times right before where pp is incremented in printAt() - this delay will increase the possibility that a context switch occurs at the worst possible time. Then explain what you see!

To cure the critical section problem you will need the support of mutex variables. The concrete task is to implement the bodies of operations lock() and unlock() in tinythreads.c, and apply them in test1.c to achieve well-behaved printouts of the prime numbers. The type mutex in tinythreads.c already contains the fields necessary to implement a mutex variable. A call to lock() shall set the locked flag of the mutex if it was previously unlocked, otherwise the running thread shall be placed in the waiting queue of the mutex and a new thread be dispatched. Calling unlock() shall activate a thread in the waiting queue of the mutex if it is non-empty, otherwise the locked flag shall be reset. Note: protecting the bodies of exported operations from interrupts is just as important here as it is in other parts of the kernel. Prioritize understanding of what is going on over eager hacking. If the mutex operations end up significantly longer than 8 lines each you should take it as an indication of a design error. When your modified program - including the global declaration of pp and any delay-loop added - generates the same kind of output as in exercise 2 of this assignment you are done! Last question to answer: why can't the sections of the kernel enclosed by DISABLE() and ENABLE() instead be protected by calls to the "proper" mutex operations you have just implemented?

Part 4: Dining Philosophers

The final part of the assignment consists of implementing a sample of dining philosopher with two philosophers and two forks.

We represent a configuration of the protocol is displayed on the display by an integer comprising 4 digits:

• the first and the third digits represent the state of the first and the second forks, respectively; value 0 (for each fork) means free and 1 means taken,

• the second and fourth digits represent the state of philosopher 1 and philosopher 2, respectively; value 0 means thinking, 1 means hungry (waiting to get one fork), 2 means having one fork, 3 means trying to get the other fork, and 4 means eating (possessing 2 forks).

For example, 1 4 1 1 denotes the situation where the first philosopher is eating with two forks and the second philosopher is hungry and trying to get hold of one fork.

The state of forks and philosophers are implemented as global integer variables. In addition the following two functions should be implemented:

void phil1() 
void phil2() 

to represent the behavior of philosophers (first thinking, then becoming hungry and trying to grab one fork, grabbing a fork when available, then trying to grab the other fork, then grabbing the other fork and eating and finally, going back to the thinking state). Note that the access to the forks (global variables) should be surrounded by a mutex. Each philosopher process is responsible for updating the digit of the corresponding philosopher on the display as well as both forks whenever it makes any change to them.

The first philosopher changes its state from thinking to hungry when the joystick is taken to left and released. For example, if the first philosopher is thinking and the joystick is taken to the left and released, then it will try to get hold of one fork and then the other and when both forks are in her/his hands, (s)he will start eating. Eating takes a fixed amount of time: 1 second and then the philosopher goes back to the initial thinking state.

The second philosopher is different; if (s)he is thinking, (s)he will move to the hungry state automatically after 2 seconds, and after starting to eat will release the fork in two seconds.

Is there a deadlock in the protocol? Propose a solution to resolve this. How can the deadlock be resolved; implement your solution and test it.

Write a short text explaining the issues encountered and your solution. Include all the programs and the short report (in pdf) in the zip file under the folder Part 4.