Embedded systems

1°/ Theory

 1.1°/ The problem 

• Historically, an application that needs concurrent processing must necessarily create several processes, called "heavy" processes
• A special process of the operating system, called the scheduler, is in charge to compute the order of execution of all processes, and giving them an amount of processor time. The goal is that every process can execute regularly a part of its instructions, and it gives to humans the feeling that all processes run concurrently.
• context switching is the mechanism to pass from the execution of a process to another. It is a kind of memory and processor state snapshot that must be kept apart, until the switched process can execute once again.
• The problem is that such a snapshot takes a long time at the machine scale : few hundreds of micro-seconds.
• This is why threads emerged. The allow to do concurrent processing without using classical processes.

1.2°/ principles

• Thread is qualified to be a light process because context switching between threads is fast : few micro-seconds.
• It is possible because the processor time given to a process can be once again divided in small chunks that are scattered over the threads.
  
• In fact, a thread is merely an execution unit that lives within a heavy process.
• It implies to create a scheduling mechanism to determine which thread must execute now and for how long time.
• All that is possible using existing libraries, like libpthread, and calling their function to create and start the execution of threads.

• Vocabulary : as for heavy processes, when a thread loose the access to the processor, we say that it "passes/looses the hand", and when it can execute once again, it "takes the hand".

1.3°/ Implications

• As threads are executing within the same process, they naturally share its ressources, notably its memory space.
• It implies that 2 threads have a natural access to the same memory locations, without the help of additional software mechanisms.
• For example, in Java, 2 threads may share the same object, assuming they have a variable that references this object.
• But sharing yields potential conflict: since we never know at which time a thread is executing and for how long time, there can be issues while modifying a memory location.

• Analogy : 2 persons (= threads) have an access to a board (= memory zone) to write news, but a single pen is available (= processor).
• The first one wants to write : "exam friday", the 2th: "away tomorrow"
• If we assume that a third person is in charge to give and take the pen (=scheduler), then the result on the board is variable:
  • "examaway friday tomorrow"
  • "eaxwaamy  ftroimdoaryrow"
  • ...
• But the common sense would be that a person has an exclusive access to he board until she stops writing.
• Moreover, since she's the only one to know the length of her message, she must be able to set and release this exclusive access.
• And if we add reader of this board, we must be able to set an order: writers first, then readers.

• While coding, this principles exist and they are called mutual exclusion and event wait.

2°/ In Java

2.1°/ Creating threads

• Java API proposes a Thread class, from which we inherit to create our own threads (NB: we can also implement Runnable interface)
• The single constraint is to implement a run() method, which is similar to main() for the thread.
• Basic example:

class MyThread extends Thread {
    int value;
    public MyThread(int value) { this.value = value; }
    public void run() {
       for(int i=0;i<1000000;i++) {
            System.out.println(value++);
        }
    }
}

• CAUTION : the header of run() is fixed: no parameters, no return value.
• Thread parameters are in fact its attributes, that can be assigned through the constructor, 

2.2°/ Instanciation and execution.

• When a Java program is launched, the JVM executes several threads, notably one for the main program.
• The main thread can create itself new threads by instantiating a thread class, with new, like other objecs
• Then, the thread execution is started by calling start() method (NB : inherited from Thread)
• Example :

class TestThread {
    public static void main(String[] args) {
        MyThread t1 = new MyThread(10);
        MyThread t2 = new MyThread(20);
        t1.start();
        t2.start();
    }
}

• CAUTION : if we call run() (instead of start() ), we do not create a new execution unit, running concurrently with the main thread.
• As for the news board, the result of this example is variable if we execute if several times.
• From a human point of view, it is not even deterministic ! Obviously, it is not the case because the thread scheduler follows well-known and fixed rules (no random). But a human cannot follow them in real-time.

2.3°/ Sharing memory

• For several threads to share the same object, the simplest way is to provide that object to the constructor of the thread and/or through a setter.
• In both cases, the object is referenced by a thread attribute.
• Generally, we start by creating shared objects then the threads, but we can do it in the reverse way if we have setters.
• Example, with an incrementing box:

class Box {
    int value;
    public Box() { value = 0; }
    public void inc(int v) { value += v; }
    public int get() { return value; }
}

class MyIncThread extends Thread {
    Box b;
    int incr;
    public MyIncThread(Box b, int incr) { this.b = b; this.incr = incr; }
    public void run() {
        for(int i=0;i<100;i++) {
            b.inc(incr);
            System.out.println(b.get());
        }
    }
}

class IncTest {
    public static void main(String[] args) {
        Box b = new Box();
        MyIncThread t1 = new MyIncThread(b,2);
        MyIncThread t2 = new MyIncThread(b,5);
        t1.start();
        t2.start();
    }
}

  

• If we execute this example several times, there won't be so much differences between the display ... but there will be.
• Nevertheless, as soon as we use thread, we must absolutely consider that the display order could be anyone !
• For example, we could obtain a very surprising result: 2 4 9 14 16 18 20 27 22 29 ...
• To understand such a case, we have to pick the point of view of the processor and not from the language.
• For example, Java instruction System.out.println(...) is compiled in many assembly instructions.
• When a thread calls this method, it is not mandatory that it reaches the end of these instructions before it looses the hand.
• From the language (and developer) point of view, a thread can loose the hand in the "middle" of a Java instruction.
• However, a single assembly instruction cannot be interrupted.
• In conclusion : unless you perfectly know the behavior of the Java compiler, you cannot know how many assembly instructions represent a single Java instruction.
• It means that we must always consider that thread executions can intricate quite weirdly.
• Example : we assume that box value is 20.
  • t1 starts the loop and calls inc(). Box value is 22. 
  • t1 calls get() then immediately looses the hand, before starting println().
  • t2 starts the loop and calls inc(). Box value is now 27.
  • t2 calls get() then println() and thus displays 27. Then it looses the hand.
  • t1 calls println() with the value it got before being interrupted. This, it prints 22.
  • t1 starts a new loop and calls inc(). Box value is 29
  • etc.

 

• In this example, even if there are access conflicts, we used the principle of "dumb thread"
• Indeed, all the functional logic to manage the box is in the Box class.
• Threads just ask for "services" to the box, by calling its methods.
• Otherwise said, the thread does nearly nothing by itself, and mostly through the shared object.
• This design pattern allows to easier fix the conflicts between threads.

 

2.4°/ Fix the conflicts: mutex and event wait

• In the box example, the order of threads execution has no impact.
• But the common sense would tell that the 3 instructions in the loop should not be interrupted.
• It is called a critical section.
• In fact, it is not possible to avoid a thread to be interrupted because it must loose the hand.
• However, it is possible to lock a critical section so that a single thread can execute its instructions, even if the thread gains and looses the hand several times before reaching the end of the section.

 

• This lock is done thanks to a mechanism called a mutex (from mutual exclusion), explained in the next section.
• For application where the thread execution order is important, we must use the mechanism of even wait, that is addressed in section 2.4.2

 

2.4.1°/ Mutex.

• The general principle of a mutex is the following:
  • we create a variable of type mutex.
  • just before the first instruction of the critical section, we call a method that locks the mutex.
  • just after the last instruction of the critical section, we call a method that unlocks the mutex.

 

• Explanation :
  • When a thread A calls the lock method, the OS keeps in memory which thread did it.
  • If A looses the hand in the middle of the section, it keeps the lock.
  • After that, if a thread B tries to lock he mutex, the OS refuses and put B in a wait state: B losses the hand and another thread C(or maybe A) executes.
  • Each time B takes the hand, it tries to lock the mutex, fails, the losses the hand.
  • And so on, until A ends the critical section and unlocks the mutex.
  • When B takes again the hand, it can finally locks the mutex and execute the section.

 

• BEWARE : a mutex does not guaranty an executio order.
• For example, if B and C are waiting that A unlocks the mutex, then the first one that takes the hand will be able to lock the mutex. Even if B was the first to wait, there is not guaranty that it will be the first to take the hand after the unlock by A. It could be C !

 

• Using mutex in Java is a bit special because there is no Mutex class in Java.
• In fact, every object contains a kind of hidden variable of type mutex. But it is not accessible (no getter).
• This variable can be manipulated thanks to the keyword synchronized, with 2 cases.
• To illustrate its use, we assume an A a class with 3 methods meth1(), meth2() et meth3().
• meth2() is a critical section by itself, whereas only few instructions in meth3() constitute a critical section.
• Assuming now that threads t1, t2, ... have all an access to object objA instance of A.

 

principle 1 : current object locking with synchronized method.

class A {
    ...
    public void meth1() { ... }
    public synchronized void meth2() { ... }
    public synchronized void meth3() { ... }
}

• In this case, assuming that t1 does objA.meth2() or objA.meth3(), the JVM checks the mutex of objA.
• If it's free, then t1 can execute the code of the method and it owns the mutex.
• If not free, t1 must wait.
• BEWARE: there is a single mutex for both methods so if t1 locks the mutex while calling meth2(), t2 will be blocked even if it calls meth3().
• However, if a thread calls meth1(), it is never blocked.

 

principle 2 : locking the mutex of an auxiliary object, using  synchronized block.

class A {
    Object myMut;
    public A() { myMut = new Object(); ... }
    ...
    public void meth1() { ... }
    public synchronized void meth2() { ... }
    public void meth3() { 
        ...
        synchronized(myMut) {
            ....
        }
        ...
    }
}

• This time, we use 2 mutex : the one of objA, that of myMut.
• Problem: no syntax to tell a method which object to use as a mutex.
• But there is a syntax to protect an instruciton block by a given mutex. It is used in meth3()
• Advantages of synchronized block are double:
  • we can use several mutex, thus not blocking threads if it is not justified.
  • we can select a set of critical instructions and not the whole method.
• The drawback is that during development phase, we regularly change the code of methods. Thus, it is quite easy to forget to put some new instructions in the critical section.

 

2.4.2°/ Event wait

• The general principle is that a thread must test a set of variables to determine if an event occurred or not.
• If it is not the case, the thread must wait passively.
• If the event occurred, the thread wakes up other threads that are waiting passively.
• In Java, it is done thanks to instructions wait() and notify()/notifyAll().
• It is closely tight to the mutex because we need a mutex to protect the instructions that determine if an event occurred or not. 
• wait() allows to put  a thread in a passive wait state, while notify() allows to wake up the threads.
• So, we do not directly use the wait yielded by a mutex but another type of wait.

 

• To setup this principle in practice:
• • as long as a set of variables that represent the even have not the right values, a thread must wait calling wait(). (NB : wait() must be put within a try/catch of InterruptedException.)
  • the first thread that states that the values are right calls notifyAll(), to wake up all waiting threads, or notify() to wake up just one
• It translates in:

while ( ... ) {
    try {
        wait();
    }
    catch(InterruptedException e) {}
}

if ( ...) {
    notifyAll();
   ...
}

• The (...) are replaced with the tests on variables.

 

• These codes are located in one or several synchronized methods accessible to threads that want to wait for the same event. This is why these methods are put in a shared object.
• It is mandatory that this methods are protected by a mutex : the tests and modifications of the variables representing the event must be done without conflitcs.
• Otherwise, we can imagine a situation where 2 threads modify these variables at the same time, avoiding that the event can occur.
• Since wait() is within a synchronized method, we can wonder why it dos not block other thread that want to wait the same event.
• Indeed, the first thread that calls the synchronized method locks the mutex. Then, other thread cannot enter in this method.
• Fortunately, calling wait() unlocks the mutex but as soon as wait() ends up, the mutex is once again locked.
• Thus, other thread are not blocked and can themselves enter in the synchronized method.

  

Example 1 : synchronization barrier for N threads

• The goals is to block N-1 threads, until the Nth unblocks them.
• It is particularly useful for a multi-threaded server where a given amount of client must be connected before starting something (e.g. a game).

class Barrier {
    int nb; // nb to reach
    int in; // nb currently waiting
    public Barrier(int nb) { 
        this.nb = nb;
        in = 0;
    }
    public synchronized void enter() {
        in += 1;
        if (in == nb) {
            notifyAll();
        }
        else {
            while(in != nb) {
                try { wait(); }
                catch{InterruptedException e) {}
            }
        }
    }
}

Remarques :

• This barrier can be used only once: we cannot reset the counter.
• For example,if we put in = 0; just after notifyAll(), other threads will wake up but the while test will fail and they will wait again.
• Unexpert users could be tempted to use an if(...) instead of a while(...).
• Big mistake : notifyAll() is not bounded to a particular event. Thus, whenever a thread calls notifyAll(), it wakes up all threads that are in a wait state, whatever the event they wait.
• Thus, a thread can be waked up for a false reason. This is why we must test once again (thanks to the while) if the vent really occurred or not.
• Another consequence, this barrier is one-shot and we have to instantiate a new one if we need another barrier.

 

Exemple 2 : the semaphore

• The semaphore is a token box where a thread can put or get n tokens
• If there is not a sufficient amount of token to be withdrawn, the thread must wait.
• A semaphore can be used to build a reusable barrier.

class Semaphore {
    int nb; // nb tokens
    public Semaphore(int nb) { this.nb = nb; }
    public synchronized void put(int n) {
        nb += n; // put n tokens
    }
    public synchronized void get(int n) {
        while(n > nb) {
            try { wait(); }
            catch{InterruptedException e) {}
            nb -= n; // withdraw de n tokens
        }
    }
}

 

• The barrier can be re-implemented using semaphores, so that it can be used several times during execution :

class Barrier {
    int nb; // nb to reach atteindre
    AtomicInteger in; // nb currently waiting
    Semaphore sem;
    public Barrier(int nb) { 
        this.nb = nb;
        in = new AtomicInteger();
        sem = new Semaphore(0); // 0 tokens
    }
    public void enter() {
        in.incrementAndGet(); // does in +=1 thread safely
        if (in.get() == nb) {
            in.set(0);
            sem.put(nb);
        }
        sem.get(1);
    }
}

Remarks :

• The instruction in+=1 is not naturally atomic: it is compiled in several assembler instructions. Thus, it should be protected by a mutex. Since it is juste a single instruction to protect and it concerns an arithmetic operation on an int, we can simply use the AtomicInteger class. In fact, this class proposes synchronized methods to manipulate an int.
• enter() must not be synchronized. It would lead to a dead-lock because of a double-lock situation.
• Indeed, if an object Barrier is shared over threads and enter() is synchronized, then:
  • the first thread that calls enter() locks the mutex of barrier, increment in, then calls sem.get(1), which makes it waiting. But, these wait release the mutex of the semaphore and not the one of the barrier.
  • A second thread calling enter() is blocked.
• This kind of barrier is reusable but not totally fairly. Indeed, assuming that a thread calls enter() two times in a row, it could withdraw two tokens and take the place of another thread that was waiting before it.

 

Example 3 : producer/consummer

• This example presents how to schedule 2 threads sharing a box, one is producing a value, the other one consumes it.
• Production only occurs if the box is empty, and consumption when the box is full.

class Box {
    int value;
    boolean isEmpty;
    public Box() { value = 0; isEmpty = true; }
    public synchronized void put(int value) {
        while(!isEmpty) {
            try { wait(); } catch(InterruptedException e) {}
        }
        this.value = value;
        isEmpty = false;
        notifyAll()
    }
    public synchronized int get() {
        while(isEmpty) {
            try { wait(); } catch(InterruptedException e) {}
        }
        isEmpty = true;
        notifyAll();
        return value;
    }

class ThreadProd extends Thread {
    Box b;
    public ThreadProd(Box b) { this.b = b; }
    public void run() {
        while (true) {
            int val = ...; // tirage aléatoire
            b.put(val);
            sleep(val*10); // au dodo
        }
    }
}

class ThreadConso extends Thread {
    Box b;
    public ThreadConso(Box b) { this.b = b; }
    public void run() {
        while (true) {
            int val = ...; // tirage aléatoire
            sleep(val*10); // au dodo
            System.out.println(b.get());
        }
    }
}

class TestBox {
    public static void main(String[] args) {
        Box b = new Box();
        ThreadProd p = new ThreadProd(b);
        ThreadConso c = new ThreadConso(b);
        p.start(); c.start();
    }
}

Remarque : in this example, each thread calls a different method in the shared box, but the principles to wait/wake are unchanged.

 

2.5°/ Problems related to mutex/event wait

• Two problems arise in the previous example.
• The first one occurs with an uncorrect code for the barrier, taht leads to a dead-lock.
• Nevertheless, a dead-lock is also possible even if the code is corect.
• The other problem comes from the unfair access to a shared object. It may lead to threads that have barely no access to the object. It is called starvation.

2.5.1°/ dead-lock

• A dead-lock occurs as soon as threads are mutually waiting a mutex to be unlocked.
• This situation arises only if there are several shared resources objects and for a particular order of thread execution.
• Analogy : a corssroad
  • 4 directions = shared resources.
  • car = thread and when a car is engaged, it blocks for a while a direction taken by another car = mutex.
  • if we assume that 4 cars are engaging the crossroad at the same time, they will all block the movement of another car, yielding a dead-lock situation.
• Generally, we enforce an execution order that never lead to such a situation.
• If it is not possible, there are mainly 2 solutions that are quite complex:
  • a supervisor thread that can unlock the dead-lock by freeing a resource (like a police agent that tells a car to get backward).
  • each thread is auto-supervised and can release by itself a resource when a dead-lock occurs.

2.5.2°/ Starvation

• This phenomena is more complex to fix because it greatly depends on mechanisms that cannot be influenced by the developer.
• Nevertheless, a good practice is to give the same amount of workload to each thread.
• We can also play the thread priority.

2.5.3°/ Example : the 5 philosophers

• 5 philosophers are sitting around a round table.
• each philosopher eat for a while, then think for a while, and so on.
• the problem comes from the forks. There are only 5 forks, one between 2 philosophers, and each needs 2 forks to eat.
• moreover, philosophers must eat equally.
• code translation
  • philosopher = thread
  • fork = shared object, each between entre 2 threads.
  • no dead-lock and starvation.
• Ti implement this problem, we take the principle od dumb-thread: the functional logic is in the fork.
• A fork can be taken and put by a thread, assuming that it can be put down only by the thread that owns it.
• The dumb thread must not be block trying to take a fork that it already owns.
• It yields:

class Fork {
    boolean isTaken;
    Thread owner;
    public Fork() { owner = null; isTaken = false; }
    public synchronized void take(Thread t) {
        if ((isTaken) && (t==owner)) return; // t has already the fork        while (isTaken) {
            try { wait(); } catch(InterruptedException e) {}
        }
        owner = t;
        isTaken = true;
    }
    public synchronized void put(Thread t) {
        if (!isTaken) return; // fork already put down
        if (t != owner) return; // bad thread
        isTaken = false;
        owner = null;
        notifyAll(); // wake up waiting threads
    }
}

• Even with this correct doe, we can easily fall into a dead-lock :

class Philo extends Thread {
    Fork left; Fork right;
    public Philo(Fork f, Fork r) { left = l; right = r; }
    public void run() {
        while(true) {
            l.take(this);
            r.take(this);
            // manger
            l.put(this);
            r.put(this);
            //penser
        }
    }
}

• Indeed, if each thread looses the hand after l.take(this), a dead-lock occurs: each thread waits for its neighbors to release the fork it misses.
• The solution: creating initial conditions that avoid dead-lock and possibly, starvation.
• In the present cas, it is sufficient to give 1 or 2 forks to some philosophers before starting the execution.
• BEWARE : this gift cannot be done in run() since we do not know the order of execution.
• Exemple complet :

class Philo extends Thread {
    int id; Fork left; Fork right;
    public Philo(int id, Fork f, Fork r) { 
        this.id = id; left = l; right = r; 
        if (id%2==0) {
            l.take(this);
            if (id != 4) r.take(this);
        }
    }
    public void run() {
        while(true) {
            l.take(this);
            r.take(this);
            // manger
            l.put(this);
            r.put(this);
            //penser
        }
    }
}

class Philo5 {
    public static void main(String[] args) {
        Fork[] forks= new Fork[5];
        Philo[] philos = new Philo[5];
        for(int i=0;i<5;i++) forks[i] = new Fork();
        for(int i=0;i<5;i++) philos[i] = new Philo(i,forks[i],forks[(i+1)%5]);
        for(int i=0;i<5;i++) philos[i].start();
    }
}