embedded 6392122.ppt

With the help of a diagram show how ROM and RAM are interfaced to a
processor. Explain the read/write processes.CO210Mention the features of I2C protocol. Draw the diagram of I2C frame
format and explain the Read/Write operation.Mention the pros and cons of
I2C protoco

1. Interprocess Communication and
Synchronization of processes,
Thread and Task
Embedded Systems – Raj Kamal

2. SVBIT,Gandhinagar 2
Operating System
•Developed to use bare machines (hardware)
•Essential software required to work with a
computer
•Manage basic hardware resources and provide
interface to users and their programs
•Also Controls the execution of application
programs
ET-2012

3. SVBIT,Gandhinagar 3
Appointment with CPU
ET-2012

4. SVBIT,Gandhinagar 4
Process
•“Process is a program in execution.” It includes current
activity as represented by PC, Registers, Stack, etc.
•Unit of Work in Modern Time Sharing systems
ET-2012
Process Program
A process is sequence of instruction.Program contains the instruction.
Process is a dynamic entity, that is a
program in execution.
Program is static entity made up of
program statement.
Process is active part. During execution
it gives the result
Program is passive part. It doesn’t give
any result but gives result after starting
its execution and becomes process.
Process is stored into memory Program is stored in disk.
Process compete for computing
resources like CPU time or memory.
Program does not compete for
Computing resources.

5. SVBIT,Gandhinagar 5
Process State
•As process executes it changes state. State is defined by the current
activity of the process.
•Each process may be in one of the following States:
1.New: To start execution of a program, a new process is created in
memory.
2.Ready: Process is waiting to be assigned to the CPU for further execution
A process which is not waiting for external event or not running is in READY state. When CPU
is free OS chooses one from list of the ready state processes and dispatch for execution as per
scheduling algorithm.
3.Running: Instructions are being executed.
Only one process execution by CPU at any given moment.
4.Blocked/Waiting: Process is waiting for some event to occur e.g. I/O
operation finish.
Blocked process cannot be scheduled for running even if CPU is free.
5.Terminated: Process has finished its executionET-2012

6. SVBIT,Gandhinagar 6
Process State Switching 5-states model
•Runs when it is scheduled to run by the OS (kernel)
•OS gives the control of the CPU on a process’s request (system
call).
•Runs by executing the instructions and the continuous
changes of its state takes place as the program counter (PC)
changes
ET-2012
new admitted
interrupt
I/O or
event
completion
Scheduler
dispatch I/O or
event wait
exit
ready
running
terminated
waiting

7. SVBIT,Gandhinagar 7
Process Definition
•Process is that executing unit of computation, which is
controlled by some processes of the OS
–for a scheduling mechanism that lets it execute on the CPU
–for a resource-management mechanism that lets it use the
system-memory and other system-resources such as
network, file, display or printer
–for access control mechanism
–for inter-process communication
–concurrently
•Application program can be said to consist of number
of processes
ET-2012

8. SVBIT,Gandhinagar 8
Process Control Block
•Information about each and every
process in our computer is stored into
Process Control Block (PCB)
•Also known as Task Control Block.
•Created when a user creates a process
•Removed from system when process
is terminated
•Stores in protected memory area of
the kernel (Memory reserved for OS)
ET-2012

9. SVBIT,Gandhinagar 9
PCB Contents
•Process State: - Information about various process states such as new, ready, running,
waiting, etc.
•Program Counter: - It shows the address of the next instruction to be executed in the
process.
•CPU registers: - There are various registers in CPU such as accumulators, stack
pointer, working register, instruction pointer. PCB stores the state of all these register
when CPU switch from one process to another process.
•CPU Scheduling information: - It includes process priority, pointer to the ready queue
and device queue, and scheduling information.
•Accounting information: - It includes total CPU time used, real time used, process
number, etc.
•I/O status information: - It includes list of I/O device allocated to the process. It also
includes the list of opened file by process in disk. File is opened either for read or
write.
•Memory-management information: - PCB stores the value of base and limit registers,
address of page table or segment table, and other memory management information.
ET-2012

10. SVBIT,Gandhinagar 10
Context Switching
•When CPU switch from one process to another process, CPU saves the
information about the one process into PCB (Process Control Block) and
then starts the new process.
•The present CPU registers, which include program counter and stack pointer
are called context.
•When context saves on the PCB pointed process-stack and register-save
area addresses, then the running process stops.
•Other process context now loads and that process runs ─ This means that
the context has switched.
•Context switch is purely overhead because system does not perform any
useful work while context switch.
•Context switch times are highly dependent on hardware. Its speed vary from
machine to machine depending on the memory speed, registers to be
copied and existence of special instructions.
ET-2012

11. SVBIT,Gandhinagar 11
Thread
•Many software that run on desktop PCs are multithreaded. An
application typically is implemented as a separate process with
several threads of control.
•A web browser may have one thread display images or text
while another thread retrieves data from the network.
•Another example, a word processor may have a thread for
displaying graphics, another thread for reading key stroke from
the user, and third thread for performing spelling and grammar
checking in the background.
ET-2012

12. 12
Thread …
•A Thread, sometimes called lightweight process (LWP), is basic unit of CPU
utilization.
•Each thread has independent parameters -- a thread ID, a program counter, a
register set, and a stack, priority and its present status .
•A traditional heavyweight Process (a kernel-level controlled entity) has a
single thread of control. If the process has multiple threads of control, it can
do more than one task at a time.
ET-2012 SVBIT,Gandhinagar

13. SVBIT,Gandhinagar 13
Thread …
•A thread can either be a sub-process within a process (kernel level thread)
or a process within an application program (user level thread)
•Thread states─ starting, running, blocked (sleep) and finished.
•A thread does not call another thread to run.
ET-2012

14. SVBIT,Gandhinagar 14
Process vs. Thread
ET-2012
Process Thread
Process is considered heavy weightThread is considered light weight
Unit of Resource Allocation and of
protection
Unit of CPU utilization
Process creation is very costly in terms
of resources
Thread creation is very economical
Program executing as process are
relatively slow
Programs executing using thread are
comparatively faster
Process cannot access the memory area
belonging to another process
Thread can access the memory area
belonging to another thread within the
same process
Process switching is time consumingThread switching is faster
One Process can contain several threadsOne thread can belong to exactly one
process

15. SVBIT,Gandhinagar 15
Task
•Task ─ term used for the process in the RTOS for the
embedded systems.
•An application program consist of the tasks and task
behaviors in various states that are controlled by OS.
•A task is like a process or thread in an OS.
•Runs when it is scheduled to run by the OS (kernel),
which gives the control of the CPU on a task request
(system call) or a message.
•Runs by executing the instructions and the continuous
changes of its state takes place as the program counter
(PC) changes
•A task─ an independent process. No task can call
another task.
ET-2012

16. SVBIT,Gandhinagar 16
Task…
•Includes task context and TCB
•TCB ─ A data structure having the information using
which the OS controls the process state.
•Stores in protected memory area of the kernel.
•Consists of the information about the task state
ET-2012

17. SVBIT,Gandhinagar 17
Task…
•TaskID, e.g. a number
between 0 and 255
•task priority, between
0 and 255,
represented by a byte
•parent task (if any),
•child task (if any),
•address to the next
task’s TCB of task that
will run next
ET-2012

18. SVBIT,Gandhinagar 18
Task States
1.Idle state [Not attached or not registered]
2.Ready State [Attached or registered]
3.Running state
4.Blocked (waiting) state
5.Delayed for a preset period
•Number of possible states depends on the RTOS.
ET-2012

19. SVBIT,Gandhinagar 19
Scheduling
•Scheduling implies selection of a process for
execution in a way to meet the objective of
the system (throughput, response time, etc.)
•Scheduler is the program responsible for
scheduling
ET-2012

20. SVBIT,Gandhinagar 20
Scheduling Criteria
•Turn around Time
–Interval of time between submission & completion
•Waiting Time
–Time spent waiting in ready queue
•Response Time
–Time from submission until response received
•CPU Utilisation
–Keep busy
•Throughput
–Number of process completed per unit time
•Fairness
–No process should starve
•Enforcing Priorities
–Scheduling policy should favors higher priority process
ET-2012

21. SVBIT,Gandhinagar 21
Scheduling Algorithms
•Non Preemptive Mode: process would be taken away from the processor if
any one of the following events occur
–Its completion
–It requires some I/O
–It executes a system call
1. FCFS(First Come First Serve)
2. SJF(Shortest Job First)
3. Priority
•Preemptive Mode: process would be taken away from the processor if any
one of the following events occur
–Timeout occurs
–Arrival of new process with higher priority
1. Round Robin
2. SRT(Shortest Remaining Time)
3. PriorityET-2012

22. SVBIT,Gandhinagar 22
First Come First Serve Scheduling
•Non preemptive algorithm
•Simplest – process that request CPU first is
allocated CPU first.
•Implemented with FIFO queue.
•When a process enters the ready queue, its PCB
would always be inserted at the tail of the queue.
•When CPU is free it is allocated with the process
at the head of the queue.
•The running process is then removed from the
queue.
ET-2012

23. SVBIT,Gandhinagar 23
FCFS Example
•Code is simple to write and understand
•Effect: large process blocking few smaller processes
which degrade the scheduling parameters.
•Assume Burst time, P1=24, P2=3, P3=3 (in ms)
•Order P1,P2,P3
–P2 waits 24, P3 waits 24+3=27
–Average wait = (0+24+27)/3=17ms (AWT or ART)
–ATAT= ((0+24)+(24+3)+(27+3))/3=27ms
•Order P2,P3,P1
–P3 waits 3, P1 waits 3+3=6
–Average wait = (0+3+6)/3=3ms
–ATAT= ?
ET-2012

24. SVBIT,Gandhinagar 24
Shortest Job First Scheduling
•Non preemptive algorithm
•Process which requires shortest burst time
would be given first chance for execution.
•Burst time cannot be determined exactly, it
can only be estimated by empirical formula
•P1=6,P2=8,P3=7,P4=3
•SJFS Order P4,P3,P1,P2
ET-2012

25. SVBIT,Gandhinagar 25
Shortest Remaining Time Scheduling
•Preemptive SJF algorithm
•Process which requires shortest remaining time
would be given first chance for execution.
•Burst time cannot be determined exactly, it can only
be estimated by empirical formula
ET-2012

26. SVBIT,Gandhinagar 26
Round Robin Scheduling
•Preemptive FCFS algorithm
•Implemented by adding a time slice mechanism to the
FIFO queue.
•Each process would be assigned to the processor for a
time interval called time slice or time quantum.
•No process in CPU is allocated more than one time
quantum in a row.
•If a process CPU burst time exceeds one time quantum
that process is preempted and put back in the ready
queue.
•If time slice is too low then more time would be spent in
context switching and if time slice is too high then other
process may suffer from starvation.ET-2012

27. SVBIT,Gandhinagar 27
Round Robin Example
•P1=24, P2=3, P3=3 (in ms)
•Time Quantum=4ms
•By RR strategy
•AWT= (?) 5.66ms
–improved
ET-2012

28. SVBIT,Gandhinagar 28
Priority Scheduling Algorithm
•Both Preemptive and Non-Preemptive mode
–Preemptive: newly arrived process’ priority is compared with existing priority,
if it is higher then current process is preempted else process continues.
–Non preemptive: newly arrived process is put at the head of the priority
queue.
•Process having highest priority would be scheduled for
execution first
•Equal Priorities scheduled in FCFS
•Internal Priorities
–Time limit
–Memory requirement
–Number of open files
•External Priorities
–Type of process
–Resources paid for running the process
ET-2012

29. SVBIT,Gandhinagar 29
Scheduling Examples
•AWT = 8.2
•Drawback: In heavily loaded system, continuous stream of
higher priority processes will keep the lower priority process
from getting access to the CPU.
•Solution: Aging – technique of gradually increasing the
priority of the process waiting in the queue
ET-2012

30. SVBIT,Gandhinagar 30
Principles of Concurrency
Three contexts:
•Multiple applications: Multiprogramming was invented to allow
the processing time of the computer to be dynamically shared
among a number of active jobs
•Structured application: As an extension of principles of modular
design and structured programming , some application can be
effectively implemented as a set of concurrent process
•Operating System Structure: The same structuring advantages
apply to the systems programmer and some OS are themselves
implemented as a set of processes.
ET-2012

31. SVBIT,Gandhinagar 31
Single vs. Multi-processor
•In single processor multiprogramming system, processes are
interleaved in time to yield the appearance of simultaneous
execution. (a)
•In multiple processor system, it is possible not only to interleave
processes but to overlap them. (b)
ET-2012

32. SVBIT,Gandhinagar 32
Process Interaction
•Independent Process(Unaware of each other)
–If it can’t affect or can’t be affected by another
process executing in the system
–No data sharing with another process in system
•Cooperative Process
–If it can affect or can be affected by another
process executing in the system
1.Cooperation by Sharing (access to some common
object) – Indirectly Aware
2.Cooperation by Communication – Directly Aware
ET-2012

33. SVBIT,Gandhinagar 33
Process Cooperation by Sharing
(Process Synchronization)
•Race Condition – When several process access and manipulate
the shared data concurrently, then outcome of execution depends
on the particular order of execution in which the access takes
place.
•Critical Section
Each processhas
a segment of code
in which the process may be
–Changing common variables
–Updating a table
–Writing on a file, etc.
ET-2012

34. SVBIT,Gandhinagar 34
Control Requirements to Critical Section
1.Mutual Exclusion
–If a process isinside critical section then another
process should not be allowed to enter critical section.
2.Progress
–If there is no process inside critical section AND if a process
wants to enter critical section then it should not be stopped
by another process.
3.Bounded Waiting
–There exist a limit on the number of times the other
process should be allowed to enter the critical section after
a process has requested for the same.
–Decision of entering critical section should not be
postponed indefinitely.
All of above three conditions must be satisfied.
ET-2012

35. SVBIT,Gandhinagar 35
Requirements for Mutual Exclusion
1.Mutual Exclusion must be forced: Among all the process that have
critical sections for shared object, only one process at a time is
allowed into its Critical section
2.A process that halts in its non-critical section must do so without
interfering with other processes.
3.It must not be possible for a process requiring access to critical
section to be delayed indefinitely: no deadlock or starvation
4.When no process is in a critical section, any process that request
entry into critical section must be permitted to enter without delay
5.No assumptions are made about relative process speeds or number
of processors
6.A process remains inside its critical section for a finite time only.
ET-2012

36. SVBIT,Gandhinagar 36
Process Cooperation by Communication
(Inter-Process Communication)
•Various processes participate in common effort that link all the
processes.
•Communication can be characterized as consisting of message of
some sort.
•Nothing is shared between processes in the act, so mutual
exclusion is NOT a control requirement
•Concurrency mechanisms for inter-process communication and
synchronization
–Queue to communicate data
–Mailbox/Messages”
–Pipes and Sockets”
–Semaphoresto trigger actions
–Signals”
–Remote Procedure Call (RPC) for distributed systems
ET-2012

37. SVBIT,Gandhinagar 37
Semaphore
•Programming language concept proposed for IPC
•Two elements – count and queue
•Semaphore is a variable upon which three operations are
defined:
1.Count is always initialized to non-negative value
2.WAIT operation decrements the semaphore value. If negative
then process that executed wait would get blocked.
• To receive a signal by semaphore, a process executes the primitive
wait(s)
3.SIGNAL operation increments the semaphore. If not positive
then semaphore will unblock one of the process from its
queue and that process to ready queue.
• To transmit a signal by semaphore, a process executes the primitive
signal(s)
ET-2012

38. SVBIT,Gandhinagar 38
Semaphore…
•Other than these three operations there is no way to inspect or
manipulate semaphore
•Wait and Signal primitives are assumed to be atomic i.e. they cannot
be interrupted and each routine can be treated as indivisible step.
•P (for wait operation) ─ derived from a Dutch word ‘Proberen’, which
means 'to test'. P semaphore function signals that the task requires a
resource and if not available waits for it.
•V (for signal passing operation) ─ derived from the word 'Verhogen'
which means 'to increment'. V semaphore function signals which the
task passes to the OS that the resource is now free for the other users.
•Semaphore are used to count the number of wakeups saved or some
positive value then one or more wakeups are pending
•For any semaphore a queue is used to hold processes waiting on the
semaphore.
ET-2012

39. SVBIT,Gandhinagar 39
Semaphore…
•General semaphore (Counting or P-V semaphore)
–Count can take any integer value
–Used for process synchronisation
•Binary semaphore (MUTEX)
–Value of count 0 or 1, Easier to implement
–Used for mutual exclusion purpose
–A process using the mutex locks on to a critical section in a task.
•Strong semaphore
–Queue implemented as FIFO queue
• The process blocked longest would be released first
–Never suffer starvation, Convenient to implement
•Weak semaphore
–Queue implemented as priority queue
–May suffer from starvation
ET-2012

40. SVBIT,Gandhinagar 40
Mutex Semaphore
•Mutex means mutually exclusive key
•Mutex is a binary semaphore usable for protecting use of resource
by other task section at an instance
•Let the key sm initial value = 1
•When the key is taken by section the key sm decrements from 1 to
0 and the waiting task codes starts.
•Assume that the sm increments from 0 to 1 for signaling or
notifying end of use of the key that section of codes in the task or
thread.
•When sm = 0 ─> assumed that it has been taken (or accepted) and
other task code section has not taken it yet and using the resource
•When sm = 1 ─> assumed that it has been released (or sent or
posted) and other task code section can now take the key and use
the resource
ET-2012

41. SVBIT,Gandhinagar 41
Signal
•A signal is the software equivalent of the flag at a register
that sets on a hardware interrupt.
•Unless masked by a signal mask, the signal allows the
execution of the signal handling function and allows the
handler to run just as a hardware interrupt allows the
execution of an ISR
•Signal is a one/two byte IPC used for signaling from a
process to OS (to enable start of another process)
•A provision for interrupt-message from a process or task to
another process or task
•When the IPC functions for signal are not provided by an
OS, then the OS employs semaphore for the same purpose.
ET-2012

42. SVBIT,Gandhinagar 42
Signal Pros and Cons
•PROS
1.The simplest IPC for messaging & synchronizing processes is signal.
2.Unlike semaphores, it takes the shortest possible CPU time.
3.A signal is the software equivalent of the flag at a register that sets on a hardware
interrupt.
4.A signal is identical to setting a flag that is shared and used by another interrupt servicing
process.
5.It is sent on some exception or on some condition, which can set during running of a
process or task or thread.
6.Sending a signal is software equivalent of throwing exception in C/C++ or Java program
7.A signal raised by one process forces another process to interrupt and to catch that signal
provided the signal is not masked at that process.
8.Unless process is masked by a signal mask, the signal allows the execution of the signal
handling process, just as a hardware interrupt allows the execution of an ISR.
•CONS
1.Signal is handled only by a very high priority process (service routine). That may disrupt
the usual schedule and usual priority inheritance mechanism.
2.Signal may cause reentrancy problem [process not returning to state identical to the one
before signal handler process executed]
ET-2012

43. SVBIT,Gandhinagar 43
Queue
•Every OS provides queue IPC functions for inserting and deleting
the message-pointers or messages in FIFO or priority mode.
•Each queue for a message need initialization (creation) before
using the functions in the scheduler for the message queue.
•Each queue either has a user definable size (upper limit for
number of bytes) or a fixed pre-defined size assigned by the
scheduler.
•When a queue becomes full, there may be a need for error
handling and user codes for blocking the task(s). There may not
be self-blocking.
•Queue functions: Create, Post, PostFront, Pend, Flush, Query,
Accept, and Delete
ET-2012

44. SVBIT,Gandhinagar 44
Mailbox
•Mailbox (for message) is an IPC through a message-block at an
OS that can be used only by a single destined task.
•Each mailbox usually has one message pointer only, which can
point to message.
•OS mailbox functions: Create, Query, Post, Pend, Accept, Delete
ET-2012

45. SVBIT,Gandhinagar 45
Pipe
•Pipe is a device used for the inter process communication.
•Pipe has the functions create, connect and delete and
functions similar to a device driver (open, write, read, close)
•A message-pipe ─ a device for inserting (writing) and deleting
(reading) from that between two given inter-connected tasks
or two sets of tasks.
•Pipes are also like Java IO stream.
•In a pipe there may be no fixed number of bytes per message
with an initial pointer for the back and front.
•Pipe is unidirectional.
•A pipe could be used for inserting the byte steam by a process
and deleting the bytes from the stream by another process.
ET-2012

46. SVBIT,Gandhinagar 46
Socket
•Socket Provides for a bi-directional pipe like device, which also use a protocol between
source and destination processes for transferring the bytes.
•Provides for establishing and closing a connection between source and destination
processes using a protocol for transferring the bytes.
•Two tasks at two distinct places or locally interconnect through the sockets.
•Multiple tasks at multiple distinct places interconnect through the sockets to a socket at
a server process.
•The client and server sockets can run on same CPU or at distant CPUs on the Internet.
•Sockets can be using a different domain/protocol.
•Two processes (or sections of a task) at two sets of ports interconnect (perform ipc)
through a socket at each.
•A pipe does not have protocol based inter-processor communication, while socket
provides that.
•A socket can be a client-server socket. Client Socket and server socket functions are
different.
•A socket can be a peer-to-peer socket IPC. At source and destination sockets have similar
functions.
ET-2012

47. SVBIT,Gandhinagar 47
Pipe vs. Socket
ET-2012
Pipe Socket
Pipe is used for IPC. Socket is used for IPC and also for
communication of process in network.
Pipe is created by the
 pipe system call,
which returns two
 descriptors.
A socket is created by the
 socket system call,
which returns a descriptor for it.
Pipe
 is a linear array of bytes, as is a file,
but it is used solely as an I/O stream.
it is logical connection for communication &
support various communication semantics.
Pipe supports destructive reading.
(once if you read it vanishes)
Socket does not, it exists as long as some
process
 holds a descriptor referring to it.
Two types of pipes are: unnamed pipes &
named pipes (FIFO)
Socket when named, is called Port.
Pipe is use for connection link, it is
unidirectional.
Sockets provide point-to-point, two-way
communication between two processes
Piping is a process where the o/p of
one process is made the i/p of another
sockets are usually datagram oriented

48. 48
Pipe vs. Queue
ET-2012 SVBIT,Gandhinagar
Pipe Queue
Pipes are a layer over message QueuesMessage queue is managed by kernel. All the
queue memory allocated at creation.
Pipe is a technique for passing information
from one process to another
Message queue is a method by which process
can pass data using an interface.
Two processes, one feeding the pipe with
data while the other extracts the data at the
other end.
A message queue can be created by one
process and used by multiple processes that
read / write messages to the queue
Pipe
 is a linear array of bytes, as is a file, but it
is used solely as an I/O stream.
Queue is not a streaming interface.
Pipe supports destructive reading. (once if
you read it vanishes)
Datagram-like behavior: reading an entry
removes it from the queue. If you don't read
the entire data, the rest is lost
Pipe is one-way communication only Have a maximum number of elements and
each element has maximum size

49. 49
Remote Procedure Call
•A method used for connecting two remotely placed functions by first
using a protocol for connecting the processes. It is used in the cases of
distributed tasks
•The RTOS can provide for the use of RPCs. These permits distributed
environment for the embedded systems.
•The OS IPC function allows a function or method to run at another
address space of shared network or other remote computer.
•The client makes the call to the function that is local or remote and the
server response is either remote or local in the call.
•Both systems work in the peer-to-peer communication mode. Each
system in peer-to-peer mode can make an RPC.
•An RPC permits remote invocation of the processes in the distributed
systems.
ET-2012 SVBIT,Gandhinagar