Tasks, Semaphores and Message

Queues
• Real-time embedded systems are reactive systems.
• Their primary purpose is to respond to or react to
signals from their environment.
• Finite-state machines (FSMs) are a powerful
mathematical and graphical tool in specifying the
behavior of reactive systems.
• An FSM is an abstract computation model that is used
to design both software and sequential logic circuits.
• a state machine is a device that stores the context of
an object at a given time.
• It operates on input events to change the context
and/or cause an action to take place.
• The context is called a state, which captures the
relevant aspects of the object’s history.
• A change from one state to another is called a
transition.
• A state transition occurs because of the occurrence
of some triggering events or conditions.
• An FSM can be represented by a directed graph
called a state diagram.
• In many FSMs, it is necessary to classify states into
initial states, final states, and intermediate states.
• Normally, an initial state is graphically marked with
an incoming arrow, while a final state is represented
with two circles.
• State Diagram of a Safe
• Consider a safe that is locked with a code 2-0-1-7.
• The states that we are interested in are as follows:
• State q0: locked, with no meaningful input.
• State q1: locked, with an input sequence that ends
with a “2.”
• State q2: locked, with an input sequence that ends
with a “2-0.”
• State q3: locked, with an input sequence that ends
with a “2-0-1.”
• State q4: unlocked (after an input sequence that
ends with a “2-0-1-7.”
• A state machine may have outputs corresponding to
each transition. There are two types of FSMs that
generate outputs:
• Moore machines
• Mealy machines
• A Moore machine is a model whose output depends
only on the current state.
• A Mealy Machine is a model whose output depends
on the current input as well as the current state.
• Moore Machine model of a Vending Machine:
• Consider a vending machine that sells candy bars for
20 cents each.
• Assume that the machine only accepts coins of 5
cents, 10 cents, and 25 cents.
• When coins of 20 cents or more are inserted into the
machine, it releases a candy bar and ejects changes.
• To model the behavior of the vending machine, we
need to find out all possible
• states and inputs and then decide transitions among
the states.
• All possible input events are as follows:
• 5c (insert a coin of 5 cents)
• 10c (insert a coin of 10 cents)
• 25c (insert a coin of 25 cents)

• After each input, the customer’s balance in the

vending machine is changed. All possible balances are
as follows:
• 0c (0 cents)
• 5c (5 cents)
• 10c (10 cents)
• 15c (15 cents)
• In addition, when a coin is inserted, the customer
may receive one of the following outputs, depending
on the total number of coins inserted:
• “-” (nothing).
• “bar” (a candy bar)
• “bar, 5c” (a candy bar and a coin of 5 cents for
change)
• “bar, 10c” (a candy bar and a coin of 10 cents)
• “bar, 15c” (a candy bar and coins of 15 cents)
• “bar, 20c” (a candy bar and coins of 20 cents)
• A seat belt is an important vehicle safety device that
prevents the occupant of a vehicle from movement
in the event of a collision or a sudden stop.
• A seat belt reminder system gives a signal after the
ignition is turned on and if the occupant’s seat belt is
not fastened.
• Assume that we want to design a seat belt reminder
system that would function according to the
following specification:
• The initial state is the car engine being off.
• After being seated, the driver can either turn on the
engine or put the seat belt on.
• When the engine is on, but the driver is seated without
the seat belt buckled, the buzzer timer is turned on.The
timer is turned off if the driver puts the seat belt on
before the timer expires.
• If the timer expires, the buzzer is turned on. When the
driver puts on his seat belt, the buzzer is turned off.
• The driver can turn off the car engine at any moment,
which turns the timer or buzzer off, whichever is on.
• When the driver is seated with the belt buckled, he can
take off the seat belt.
• The driver cannot turn on the car engine before he is
seated.
• The driver cannot leave the seat with the seat belt
buckled or while the engine is on.
• The inputs of the system are from the car key, seat
sensor, belt sensor, and timer.
• Input events are:key, seat, unseat, belt, unbelt, and
timer_expires.
• Outputs are:timer_off . timer_on, buzzer_off , and
buzzer_on.
• The system can take any one of the following states
at any given time:
• Off: The engine is off.
• Seated: Driver is seated with engine off.
• Ready: Driver is seated with seat belt buckled and
engine off.
• Timing: Driver is seated with engine on and timer on.
• Belted: Driver is belted with engine on.
• Buzzer: Buzzer is on.
• Semaphore:
• The Critical-Section Problem:
• Consider a system consisting of n processes {P0, P1, ...,
Pn−1}.
• Each process has a segment of code, called a critical
section.
• In the critical section, the process may be changing
common variables, updating a table, writing a file, and
so on.
• The important feature of the system is that, when one
process is executing in its critical section, no other
process is to be allowed to execute in its critical
section.
• That is, no two processes are executing in their
critical sections at the same time.
• The critical-section problem is to design a protocol
that the processes can use to cooperate.
• Each process must request permission to enter its
critical section.
• The section of code implementing this request is the
entry section.
• The critical section may be followed by an exit
section.
• The remaining code is the remainder section.
• The general structure of a typical process Pi is shown
in figure below:
• A solution to the critical-section problem must satisfy
the following three requirements:
• Mutual exclusion. If process Pi is executing in its
critical section, then no other processes can be
executing in their critical sections.
• Progress. If no process is executing in its critical
section and some processes wish to enter their
critical sections,
• then only those processes that are not executing in
their remainder sections can participate in
• deciding which will enter its critical section next, and
this selection cannot be postponed indefinitely.
• Bounded waiting. There exists a bound, or limit, on
the number of times that other processes are
allowed to enter their critical sections after a
• process has made a request to enter its critical
section and before that request is granted.
• But this process is difficult to apply in real-time.
• Therefore the use of semaphores is guaranteed.
• A semaphore S is an integer variable that, apart from
initialization, is accessed only through two standard
atomic operations:
• wait() and signal().
• wait(S)
• {
• while S <= 0; // no-op
• S--;
• }

• signal(S)
• {
• S++;
• }
• Operating systems often distinguish between counting
and binary semaphores.
• The value of a counting semaphore can range over an
unrestricted domain.
• The value of a binary semaphore can range only
between 0 and 1.
• consider two concurrently running processes: P1 with
a statement S1 and P2 with a statement S2.
• Suppose we require that S2 be executed only after S1
has completed.
• We can implement this scheme readily by letting P1
and P2 share a common semaphore synch, initialized
to 0, and by inserting the statements.
• S1;
• signal(synch);
• in process P1

• the statements
• wait(synch);
• S2;
• in process P2.
• Suppose that P0 executes wait(S) and then P1
executes wait(Q)
• When P0 executes wait(Q), it must wait until P1
executes signal(Q).
• Similarly, when P1 executes wait(S), it must wait until
P0 executes signal(S).
• Since these signal() operations cannot be executed,
P0 and P1 are deadlocked.
• We say that a set of processes is in a deadlock state
when every process in the set is waiting for an event
that can be caused only by another process in the
set.
 Priority Inversion
• A higher-priority process needs to read or modify
kernel data that are currently being accessed by a
lower-priority process.
• Assume we have three processes, L, M, and H, whose
priorities follow the order L < M < H.
• Assume that process H requires resource R, which is
currently being accessed by process L.
• Ordinarily, process H would wait for L to finish using
resource R.
• However, now suppose that process M becomes
runnable.
• thereby preempting process L.
• Indirectly, a process with a lower priority—process M
—has affected how long process H must wait for L to
relinquish resource R.
• This problem is known as priority inversion.
• Typically systems solve the problem by
implementing a priority-inheritance protocol.
• According to this protocol, all processes that are
accessing resources needed by a higher-priority
process
• inherit the higher priority until they are finished with
the resources in question.
• When they are finished, their priorities revert to their
original values.
• In the example above, a priority-inheritance protocol
would allow process L to temporarily inherit the
priority of process H.
• Thereby preventing process M from preempting the
execution of L.
• When process L had finished using resource R, it
would relinquish its inherited priority from H and
assume its original priority.
• Because resource R would now be available, process
H—not M—would run next.
• Resource Sharing
• A task may need some resources in addition to a
processor in order to make progress.
• When a task wants to access the shared data
guarded by a semaphore R,
• it must lock the semaphore first and then enters the
critical section of the code where it accesses the
shared data.
• In this case, we say that the task requires the
resource R for the duration of the critical section.
• Suppose that there are m types of resources in a
system, namely R1, R2, …, Rm
• there are Vi indistinguishable units of Ri, i=1, 2, …,m.
• When a task requests Ni units of a resource Ri, it
executes a lock to request them.
• The action is denoted by L(Ri, Ni).
• When the task no longer needs a resource, it executes
an unlock to release the resource, denoted by U(Ri,
Ni).
• The code segment of a task that begins at a lock and
ends at a matching unlock is called a critical section,
which cannot be concurrently executed by multiple
processes.
• When a task is denied a lock request, the task is in
blocked state.
• The task which enters blocked state is removed from
ready queue.
• It again joins the ready queue when the kernel grants
the lock request of that task.
• This is known as multi-process resource access
synchronization.
Message queue:
• A message queue is a buffer-like object through
which tasks and ISRs send and receive messages to
communicate and synchronize with data.
• A message queue is like a pipeline.
• It temporarily holds messages from a sender until the
intended receiver is ready to read them.
• When a message queue is created, it is assigned a
queue control block.
• A queue has name, ID, memory buffers, queue
length, message length.
• Message Queue can be most appropriately
used for
• a temperature value from a sensor.
• a bitmap to draw on a display.
• a text message to print to an LCD.
• a keyboard event.
• a data packet to send over the network.
• Messages can be read from the head of a message
queue in two different ways:
• destructive read, and
• non-destructive read.
• In a destructive read, when a task successfully
receives a message from a queue,
• the task permanently removes the message from the
message queue’ s storage buffer.
• In a non-destructive read, a receiving task peeks at
the message at the head of the queue without
removing it.
• The message queue can be classified into
• 1. Interlocked, one-way data communication.
• 2. Interlocked, two-way data communication.
• Messages can be sent in LIFO and FIFO order.
• When sending messages, a kernel typically fills a
message queue from head to tail in FIFO order.
• Develop a state-diagram based model for a
tea/coffee vending machine subject to the following
constraints.
• Each cup of tea/coffee costs 5 rupees.
• Develop a state-diagram based model for a
tea/coffee/milk vending machine subject to the
following constraints.
• Each cup of tea/coffee costs 5 rupees.
• Milk costs 10 rupees.(10 rupee coin is available)
• If a 5 rupee coin is inserted and milk option is
selected, then refund the coin.
 Assumptions
• At start the machine asks the user for Tea/Coffee.
• After this choice the machine displays “insert 5 rupee
coin .”Then wait.
• Once user drops a coin, based on the option dispense
tea or coffee.
• Once the user selects the option get an option for
sugar/sugarless.
• If the coin is less than 5 rupee. The change is
returned back.
 States

• Ready
• Tea/Coffee
• Coin
• Change
• Sugar
• Dispense tea.
• Dispense coffee.
 Events
• Check:1
• Coin_insrt: 2
• Sugar_opt: 3
• Tea/coffee: 4/5
• Wrong_coin: 6
• Dispensed/change: 7
• Reset: 8
 State diagram

1 2 Tea/Coff 3
Ready Coin sugar
ee

6 4
5
7

Dispense Dispense
Change
Tea Coffee

7 7