REAL TIME SYSTEMS - EMBEDDED SYSTEMS AND INTERNET OF THINGS

REAL TIME SYSTEMS
Foreground/Background Systems – Context Switching – Non-Preemptive Kernel, Preemptive Kernel –
Scheduler – Scheduling Reentrancy – Priority Inversion – Assigning Task Priorities – Priority
Inheritance – Mutual Exclusion – Semaphores – Deadlock – Synchronization – Event Flags – Inter Task
Communications – Message Mailboxes – Message Queues – Interrupts – Clock Tick – Memory
Requirements.

1. SRI RAMAKRISHNA ENGINEERING COLLEGE [Educational Service : SNR Sons Charitable Trust] [Autonomous Institution, Rea ccredited by NAAC with ‘A+’ Grade] [Approved by AICTE and Permanently Affiliated to Anna University, Chennai] [ISO 9001:2015 Certified and all Eligible Programmes Accredited by NBA] VATTAMALAIPALAYAM, N.G.G.O. COLONY POST, COIMBATORE – 641 022. 20EC211 – EMBEDDED SYSTEMS AND INTERNET OF THINGS Module 3: REALTIME SYSTEMS Department of Information Technology

2. REALTIME SYSTEMS Foreground/Background Systems -- Context Switching - Non-Preemptive Kernel, Preemptive Kernel - Scheduler - Scheduling Reentrancy - Priority Inversion - Assigning Task Priorities - Priority Inheritance - Mutual Exclusion - Semaphores - Deadlock - Synchronization - Event Flags - Inter Task Communications - Message Mailboxes - Message Queues - Interrupts - Clock Tick - Memory Requirements.

3. CO4: Explain real time embedded systems using the concepts of RTOS . Course Outcome

4. Introduction An RTOS is an operating system designed to manage hardware resources of an embedded system It creates multiple threads of software execution and a scheduler for managing these threads. Another way to put it is a scheduling kernel that creates a multi-tasking and deterministic run-time environment. An RTOS is commonly used when there are more interrupt sources, more functions, and more communication interfaces. In short, it’s the application complexity that mostly decides the use of RTOS tailored for MCUs. Once an embedded developer decides to use an RTOS solution, the first thing to see is the amount of RAM and flash available in a microcontroller. An RTOS solution may require 6 KB to 10 KB of flash, so as a rule of thumb, the MCU should have around 32 KB of flash memory to ensure that there is ample space for the application code. * 16EC213 EMBEDDED SYSTEMS AND IOT - S.BHAGGIARAJ 4

5. Foreground/Background Systems A real-time operating system (RTOS) is intended to serve real-time applications that process data without buffer delays. A real-time system is a time-bound system with well-defined and fixed time constraints, and processing must be done within the defined constraints; otherwise, the system will fail. In a real-time operating system, processing time requirements are measured in tenths of seconds.

6. Foreground/Background Systems Real-Time System is used at those Places where we require higher and timely responses. Real-time operating systems involve a set of applications where the operations are performed on time to run the activities in an external system. It uses the quantitative expression of time to analyze the system's performance. The deadline in the context of a real-time system is the moment of the time by which the job's execution is needed to be accomplished. Most real-time operating systems use a pre-emptive scheduling algorithm.

7. Foreground/Background Systems The real-time operating system has the following advantages, such as: Task switching:  Real-time operating systems are designed, so that starting switching is a very quick process. A normal traditional operating system takes a lot of time while switching from one person to another process. The real-time operating system completes the task switching only within some of the microseconds. Focus execution:  The main focus of real-time operating systems is to handle the task in execution, and just a little focus is on the task in waiting. Error-free:  Real-time operating systems are designed very carefully, and different kinds of software testing techniques are applied to the real-time operating system to test the system. This detailed testing makes the real-time operating system approximately error-free.

8. Foreground/Background Systems Maximum resource utilization:  Real-time operating systems are designed to follow the task within a given time secretly. This is not simple and easy to complete the task within time. The real-time operating system utilizes all the hardware efficiently and completely. The main focus of the real-time operating system is not to save energy or resources. So we can see that the real-time operating system utilize the resources completely and very efficiently. Usage in embedded systems:  Real-time operating systems can also work with embedded systems. All-time performance:  Real-time operating systems are designed to works 24 hours a day and every day.

9. Types of Real-Time System A real-time operating system is divided into two systems, such as: Hard real-time system Soft real-time system Hard and Soft real-time systems are the variants of real-time systems where the hard real-time system is more restrictive than the soft real-time system. The hard real-time system must assure to finish the real-time task within the specified deadline. While this is not the case in the soft real-time system, it assigns superior scheduling priority to real-time tasks.

10. Hard Real-Time System(HRTS) A hard real-time system considers timelines as a deadline, and it should not be omitted in any circumstances. Hard real-time Systems do not use any permanent memory, so their processes must be complete properly in the first time itself.

11. Hard Real-Time System must generate accurate responses to the events within the specified time. A hard real-time system is a purely deterministic and time constraint system. For example, users expected the output for the given input in 5 sec then the system should process the input data and give the output exactly by the 5 th  second. It should not give the output by the 6 th  second or by the 4 th  second. Here above 5 seconds is the deadline to complete the process for given data. In the hard real-time system, meeting the deadline is very important if the deadline is not met, the system performance will fail.

12. Examples of Hard Real-Time Systems Flight Control Systems Missile Guidance Systems Weapons Defense System Medical System Inkjet printer system Railway signalling system Air traffic control systems Nuclear reactor control systems Anti-missile system Chemical plant control Autopilot System in Plane Pacemakers

13. Soft Real-Time System(SRTS) A soft real-time system is a system whose operation is degraded if results are not produced according to the specified timing requirement. In a soft real-time system, the meeting of deadline is not compulsory for every task, but the process should get processed and give the result. Even the soft real-time systems cannot miss the deadline for every task or process according to the priority it should meet the deadline or miss the deadline.

14. If a system is missing the deadline every time, the system's performance will be worse and cannot be used by the users. The best example for the soft real-time system is a personal computer, audio and video systems, etc. Soft real-time systems consider the processes as the main task and control the entire task. Personal computer Audio and video systems Set-top boxes DVD Players Weather Monitoring Systems Electronic games Multimedia system Web browsing Online transaction systems Telephone switches Virtual reality Mobile communication

15. Difference between Hard and Soft Real-Time System Terms Hard Real-Time System Soft Real-Time System Definition A hard-real time system is a system in which a failure to meet even a single deadline may lead to complete or appalling system failure. A soft real-time system is a system in which one or more failures to meet the deadline are not considered complete system failure, but that performance is considered to be degraded. File size In a hard real-time system, the size of a data file is small or medium. In a soft real-time system, the size of the data file is large. Response time In this system, response time is predefined that is in a millisecond. In this system, response time is higher. Utility A hard-real time system has more utility. A soft real-time system has less utility. Database A hard real-time system has short databases. A soft real-time system has enlarged databases. Performance Peak load performance should be predictable. In a soft real-time system, peak load can be tolerated. Safety In this system, safety is critical. In this system, safety is not critical.

16. Difference between Hard and Soft Real-Time System Terms Hard Real-Time System Soft Real-Time System Integrity Hard real-time systems have short term data integrity. Soft real-time systems have long term data integrity. Restrictive nature A hard real-time system is very restrictive. A Soft real-time system is less restrictive. Computation In case of an error in a hard real-time system, the computation is rolled back. In a soft real-time system, computation is rolled back to a previously established checkpoint to initiate a recovery action. Flexibility and laxity Hard real-time systems are not flexible, and they have less laxity and generally provide full deadline compliance. Soft real-time systems are more flexible. They have greater laxity and can tolerate certain amounts of deadline misses. Validation All users of hard real-time systems get validation when needed. All users of soft real-time systems do not get validation. Examples Satellite launch, Railway signalling systems, and Safety-critical systems are good examples of a hard real-time system. DVD player, telephone switches, electronic games, Linux, and many other OS provide a soft real-time system.

17. Applications

18. Disadvantages of RTOS RTOS system can run minimal tasks together, and it concentrates only on those applications which contain an error so that it can avoid them. RTOS is the system that concentrates on a few tasks. Therefore, it is really hard for these systems to do multi-tasking. Specific drivers are required for the RTOS so that it can offer fast response time to interrupt signals, which helps to maintain its speed. Plenty of resources are used by RTOS, which makes this system expensive. The tasks which have a low priority need to wait for a long time as the RTOS maintains the accuracy of the program, which are under execution. Minimum switching of tasks is done in Real time operating systems. It uses complex algorithms which is difficult to understand. RTOS uses lot of resources, which sometimes not suitable for the system

19. RTOS Architecture

20. Kernel - Monolithic kernel

21. Microkernel

22. Exokernel

23. RTOS Kernel Services

24. A  Context switch  is a time spent between two processes (i.e., bringing a waiting process into execution and sending an executing process into a waiting for state). This happens in multitasking. The operating system must bring the state information if waiting for process into memory and save the state information of the currently running process.  In order to solve this problem, we would like to record the timestamps of the first and last instructions of the swapping processes. The context switch time is the difference between the two processes. 

25. Assume there are only two processes, P1 and P2.  P1 is executing and P2 is waiting for execution. At some point, the operating system must swap P1 and P2, let’s assume it happens at the nth instruction of P1. If t(x, k) indicates the timestamp in microseconds of the kth instruction of process x, then the context switch would take t(2, 1) – t(1, n).  Another issue is that swapping is governed by the scheduling algorithm of the operating system and there may be many kernel-level threads that are also doing context switches. Other processes could be contending for the CPU or the kernel handling interrupts. The user does not have any control over these extraneous context switches. For instance, if at time t(1, n) the kernel decides to handle an interrupt, then the context switch time would be overstated. 

26. In order to avoid these obstacles, we must construct an environment such that after P1 executes, the task scheduler immediately selects P2 to run. This may be accomplished by constructing a data channel, such as a pipe between P1 and P2.  That is, let’s allow P1 to be the initial sender and P2 to be the receiver. Initially, P2 is blocked(sleeping) as it awaits the data token. When P1 executes, it delivers the data token over the data channel to P2 and immediately attempts to read the response token. A context switch results and the task scheduler must select another process to run. Since P2 is now in a ready-to-run state, it is a desirable candidate to be selected by the task scheduler for execution. When P2 runs, the role of P1 and P2 are swapped. P2 is now acting as the sender and P1 as the blocked receiver. 

27. To summaries P2 blocks awaiting data from P1 P1 marks the starting time. P1 sends a token to P2. P1 attempts to read a response token from P2. This induces a context switch. P2 is scheduled and receives the token. P2 sends a response token to P1. P2 attempts to read a response token from P1. This induces a context switch. P1 is scheduled and receives the token. P1 marks the end time.

28. The key is that the delivery of a data token induces a context switch. Let Td and Tr be the time it takes to deliver and receive a data token, respectively, and let Tc be the amount of time spent in a context switch. At step 2, P1 records the timestamp of the delivery of the token, and at step 9, it records the timestamp of the response. The amount of time elapsed, T, between these events, may be expressed by:  T = 2 * (Td + Tc + Tr )

29. Consider three CPU-intensive processes, which require 10, 20 and 30 time units and arrive at times 0, 2 and 6, respectively. How many context switches are needed if the operating system implements a shortest remaining time first scheduling algorithm? Do not count the context switches at time zero and at the end.

30. Let three process be P0, P1 and P2 with arrival times 0, 2 and 6 respectively and CPU burst times 10, 20 and 30 respectively. At time 0, P0 is the only available process so it runs. At time 2, P1 arrives, but P0 has the shortest remaining time, so it continues. At time 6, P2 also arrives, but P0 still has the shortest remaining time, so it continues. At time 10, P1 is scheduled as it is the shortest remaining time process. At time 30, P2 is scheduled. Only two context switches are needed. P0 to P1 and P1 to P2.

31. Non-Preemptive Kernel Non-preemptive Scheduling is used when a process terminates, or a process switches from running to the waiting state. In this scheduling, once the resources (CPU cycles) are allocated to a process, the process holds the CPU till it gets terminated or reaches a waiting state. In the case of non-preemptive scheduling does not interrupt a process running CPU in the middle of the execution. Instead, it waits till the process completes its CPU burst time, and then it can allocate the CPU to another process. Algorithms based on non-preemptive scheduling are:  Shortest Job First (SJF basically non preemptive)  and  Priority (non preemptive version) , etc. 

32. Preemptive Kernel Preemptive scheduling is used when a process switches from running state to ready state or from the waiting state to ready state. The resources (mainly CPU cycles) are allocated to the process for a limited amount of time and then taken away, and the process is again placed back in the ready queue if that process still has CPU burst time remaining. That process stays in the ready queue till it gets its next chance to execute.  Algorithms based on preemptive scheduling are:  Round Robin (RR) , Shortest Remaining Time First (SRTF) ,  Priority (preemptive version) , etc. 

33. Preemptive Kernel    Non-Preemptive Kernel  It is a process that might be replaced immediately.  It is a process that continuous to run until it finishes handling execution handler or voluntarily relinquishes CPU.  It is more suitable for real time programming as compared to non-preemptive kernels.   It is less suitable for real-time programming as compared to preemptive kernel.   In this, higher priority task that are ready to run is given CPU control.   In this, each and every task are explicitly given up CPU control.   It generally allows preemption even in kernel mode.   It generally does not allow preemption of process running in kernel mode.   Responsive time is deterministic and is more responsive as compared to non-preemptive kernel. Response time is nondeterministic and is less responsive as compared to preemptive kernel. Higher priority task becomes ready, currently running task is suspended and moved to ready queue. Higher priority task might have to wait for long time.   It does not require semaphores.   Shared data generally requires semaphores.   It cannot use non-reentrant code.   It can use non-reentrant code.   It is more difficult to design preemptive kernels as compared to non-preemptive kernel. It is less difficult to design non-preemptive kernels as compared to preemptive kernels.   They are more secure and more useful in real-world scenarios.   They are less secure and less useful in real-world scenarios. 

34. Scheduler In modern computer systems, there may be many threads waiting to be served at the same time. Thus, one of the most important jobs of the kernel is to decide which thread to run for how long. The part of the kernel in charge of this business is called the scheduler. On a single processor system, the scheduler alternates different threads in a time-division manner, which may lead to the illusion of multiple threads running concurrently. On a multi-processor system, the scheduler assigns a thread at each processor so that the threads can be truly concurrent.

35. Priority Most of scheduling algorithms are priority-based. A thread is assigned a priority according to its importance and need for processor time. The general idea, which isn’t exactly implemented on Linux, is that threads with a higher priority run before those with a lower priority, whereas threads with the same priority are scheduled in a round-robin fashion.

36. Scheduling in RTOS More information about the tasks are known No of tasks Resource Requirements Release Time Execution time Deadlines Being a more deterministic system better scheduling algorithms can be devised. 22-08-2025 20EC211 39

37. Scheduling Algorithms in RTOS Clock Driven Scheduling Weighted Round Robin Scheduling Priority Scheduling (Greedy / List / Event Driven) 20EC211 40

38. Scheduling Algorithms in RTOS ( contd) Clock Driven All parameters about jobs (release time/ execution time/deadline) known in advance. Schedule can be computed offline or at some regular time instances. Minimal runtime overhead. Not suitable for many applications. 22-08-2025 20EC211 41

39. Scheduling Algorithms in RTOS ( contd ) Weighted Round Robin Jobs scheduled in FIFO manner Time quantum given to jobs is proportional to it’s weight Example use : High speed switching network QOS guarantee. Not suitable for precedence constrained jobs. Job A can run only after Job B. No point in giving time quantum to Job B before Job A. 22-08-2025 20EC211 42

40. Scheduling Algorithms in RTOS ( contd ) Priority Scheduling (Greedy/List/Event Driven) Processor never left idle when there are ready tasks Processor allocated to processes according to priorities Priorities static - at design time Dynamic - at runtime 22-08-2025 20EC211 43

41. 22-08-2025 20EC211 44

42. Basic Concepts Maximum CPU utilization obtained with multiprogramming CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait CPU burst distribution is important in the selection of appropriate CPU Scheduling algorithm. I/O bound program has many short CPU burst CPU bound program has few long CPU burst 45 20EC211

43. Alternating Sequence of CPU and I/O Bursts 46 20EC211

44. CPU Scheduler Selects from among the processes in ready queue, and allocates the CPU to one of them Queue may be ordered in various ways CPU scheduling decisions may take place when a process: 1. Switches from running to waiting state 2. Switches from running to ready state 3. Switches from waiting to ready Terminates Scheduling under 1 and 4 is nonpreemptive All other scheduling is preemptive Consider access to shared data Consider preemption while in kernel mode Consider interrupts occurring during crucial OS activities 47 20EC211

45. Scheduling 48

46. Dispatcher Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves: switching context switching to user mode jumping to the proper location in the user program to restart that program The dispatcher should be as fast as possible, since it is invoked during every process switch . Dispatch latency – time it takes for the dispatcher to stop one process and start another running 49 20EC211

47. CPU Scheduling Algorithms A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. Types of CPU Scheduling 50 20EC211

48. CPU Scheduling Criteria 51 20EC211

49. CPU scheduling Terminologies Burst Time/Execution Time: It is a time required by the process to complete execution Arrival Time: when a process enters in a ready state Finish Time: when process complete and exit from a system Process: running program. CPU/IO burst cycle: Characterizes process execution, which alternates between CPU and I/O activity. CPU times are usually shorter than the time of I/O. 52 20EC211

50. CPU Scheduling Criteria CPU utilization: CPU utilization is the main task in which the operating system needs to make sure that CPU remains as busy as possible. Throughput: The number of processes that finish their execution per unit time. Waiting time: Waiting time is an amount that specific process needs to wait in the ready queue. Response time: It is an amount to time in which the request was submitted until the first response is produced. Turnaround Time: Turnaround time is an amount of time to execute a specific process. 53 20EC211

51. Types of CPU scheduling Algorithm 54 20EC211

52. Scheduling Process State Diagram 55

53. Scheduling Types of Scheduling Algorithms There are many scheduling algorithms that can be used for scheduling task execution on a CPU. They can be classified into two main types : preemptive scheduling algorithms and non-preemptive scheduling algorithms. Preemptive Scheduling Preemptive scheduling allows the interruption of a currently running task, so another one with more “urgent” status can be run . The interrupted task is involuntarily moved by the scheduler from running state to ready state. This dynamic switching between tasks that this algorithm employs is, in fact, a form of multitasking. It requires assigning a priority level for each task. A running task can be interrupted if a task with a higher priority enters the queue. 56

54. Scheduling Preemptive Scheduling 57

55. Scheduling Non-Preemptive Scheduling In non-preemptive scheduling, the scheduler has more restricted control over the tasks. It can only start a task and then it has to wait for the task to finish or for the task to voluntarily return the control. A running task can’t be stopped by the scheduler. 58

56. Scheduling Popular Scheduling Algorithm We will now introduce some of the most popular scheduling algorithms that are used in CPU scheduling. Not all of them are suitable for use in real-time embedded systems. Currently, the most used algorithms in practical RTOS are non-preemptive scheduling, round-robin scheduling, and preemptive priority scheduling. 59

57. Scheduling First Come, First Served (FCFS) FCFS is a non-preemptive scheduling algorithm that has no priority levels assigned to the tasks. The task that arrives first into the scheduling queue ( i.e enters ready state), gets put into the running state first and starts utilizing the CPU. It is a relatively simple scheduling algorithm where all the tasks will get executed eventually. The response time is high as this is a non-preemptive type of algorithm. 60

58. Scheduling First Come, First Served (FCFS) Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is: Waiting time for P1 = 0; P2 = 24; P3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 61

59. Scheduling First Come, First Served (FCFS) Suppose that the processes arrive in the order P2 , P3 , P1 . The Gantt chart for the schedule is: Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 62 P 1 P 3 P 2 6 3 30

60. First-Come, First-Served (FCFS) Scheduling Process Burst Time P 1 24 P 2 3 P 3 3 Suppose that the processes arrive in the order: P 1 , P 2 , P 3 The Gantt Chart for the schedule is: Waiting time for P 1 = 0; P 2 = 24; P 3 = 27 Average waiting time: (0 + 24 + 27)/3 = 17 P 1 P 2 P 3 24 27 30 22-08-2025 63 20EC211

61. FCFS Scheduling (Cont.) Suppose that the processes arrive in the order: P 2 , P 3 , P 1 The Gantt chart for the schedule is: Waiting time for P 1 = 6 ; P 2 = 0 ; P 3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect - short process behind long process Consider one CPU-bound and many I/O-bound processes P 1 P 3 P 2 6 3 30 22-08-2025 64 20EC211

62. Example Problem -FCFS Gantt Chart Solution: 22-08-2025 65 20EC211

63. Contd… Formula to calculate TAT and WT Turn Around Time = Completion Time - Arrival Time    Waiting Time = Turnaround time - Burst Time    22-08-2025 66 20EC211

64. Completion Time Calculation 22-08-2025 67 20EC211

65. Turn Around Time Calculation Turn Around Time = Completion Time - Arrival Time   68 20EC211

66. Waiting Time Calculation Waiting Time = Turnaround time - Burst Time    22-08-2025 69 20EC211

67. Response Time Calculation Response Time = Time at which process first gets the CPU – Arrival time 22-08-2025 70 20EC211

68. Scheduling Shortest Job First (SJF) In the shortest job first scheduling algorithm, the scheduler must obtain information about the execution time of each task and it then schedules the one with the shortest execution time to run next. SJF is a non-preemptive algorithm, but it also has a preemptive version . In the preemptive version of the algorithm (aka shortest remaining time) the parameter on which the scheduling is based is the remaining execution time of a task. If a task is running it can be interrupted if another task with shorter remaining execution time enters the queue. A disadvantage of this algorithm is that it requires the total execution time of a task to be known before it is run. 71

69. Scheduling Shortest Job First (SJF)- Non-Preemptive Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 Average waiting time = (0 + 6 + 3 + 7)/4 = 4 72 P 1 P 3 P 2 7 3 16 P 4 8 12

70. Scheduling Shortest Job First (SJF)- Preemptive Process Arrival Time Burst Time P1 0.0 7 P2 2.0 4 P3 4.0 1 P4 5.0 4 Average waiting time = (9 + 1 + 0 +2)/4 = 3 73 P 1 P 3 P 2 4 2 11 P 4 5 7 P 2 P 1 16

71. Example Problem - SJF Solution: Gantt Chart 22-08-2025 74 20EC211

72. Completion Time Calculation 22-08-2025 75 20EC211

73. Turn Around Time Calculation Turn Around Time = Completion Time - Arrival Time   22-08-2025 76 20EC211

74. Waiting Time Calculation Waiting Time = Turnaround time - Burst Time    22-08-2025 77 20EC211

75. Response Time Calculation Response Time = Time at which process first gets the CPU – Arrival time 22-08-2025 78 20EC211

76. Scheduling Priority Scheduling Priority scheduling is one of the most popular scheduling algorithms. Each task is assigned a priority level . The basic principle is that the task with the highest priority will be given the opportunity to use the CPU. In the preemptive version of the algorithm, a running task can be stopped if a higher priority task enters the scheduling queue. In the non-preemptive version of the algorithm once a task is started it can’t be interrupted by a higher priority task. Of course, not all tasks can have unique priority levels and there will always be tasks that have the same priority. Different approaches can be used for handling the scheduling of those tasks ( e.g FCFS scheduling or round-robin scheduling). 79

77. Scheduling Priority Scheduling 80

78. Scheduling Priority Scheduling Advantages of priority scheduling Easy to use scheduling method Processes are executed on the basis of priority so high priority does not need to wait for long which saves time This method provides a good mechanism where the relative important of each process may be precisely defined. Suitable for applications with fluctuating time and resource requirements. 81

79. Scheduling Priority Scheduling Disadvantages of priority scheduling If the system eventually crashes, all low priority processes get lost. If high priority processes take lots of CPU time, then the lower priority processes may starve and will be postponed for an indefinite time. This scheduling algorithm may leave some low priority processes waiting indefinitely. A process will be blocked when it is ready to run but has to wait for the CPU because some other process is running currently. If a new higher priority process keeps on coming in the ready queue, then the process which is in the waiting state may need to wait for a long duration of time. 82

80. Scheduling Round-Robin Scheduling Round-robin is a preemptive type of scheduling algorithm. There are no priorities assigned to the tasks. Each task is put into a running state for a fixed predefined time . This time is commonly referred to as time-slice (quantum). A task can not run longer than the time-slice. In case a task has not completed by the end of its dedicated time-slice, it is interrupted, so the next task from the scheduling queue can be run in the following time slice. A pre-emptied task has an opportunity to complete its operation once it’s again its turn to use a time-slice. An advantage of this type of scheduling is its simplicity and relatively easy implementation 83

81. Scheduling Round-Robin Scheduling 84

82. Scheduling Round-Robin Scheduling Advantages- It gives the best performance in terms of average response time. It is best suited for time sharing system, client server architecture and interactive system. Disadvantages- It leads to starvation for processes with larger burst time as they have to repeat the cycle many times. Its performance heavily depends on time quantum. Priorities can not be set for the processes. 85

83. Scheduling Round-Robin Scheduling 86 Ready Queue- P5, P1, P2, P5, P4, P1, P3, P2, P1

84. Scheduling Round-Robin Scheduling 87

85. Scheduling Round-Robin Scheduling 88 Ready Queue- P5, P6, P2, P5, P6, P2, P5, P4, P1, P3, P2, P1

86. Scheduling Round-Robin Scheduling 89

87. Priority inversion 90 Priority inversion is a operating system scenario in which a higher priority process is preempted by a lower priority process. This implies the inversion of the priorities of the two processes. Some of the problems that occur due to priority inversion are given as follows − A system malfunction may occur if a high priority process is not provided the required resources. Priority inversion may also lead to implementation of corrective measures. These may include the resetting of the entire system. The performance of the system can be reduces due to priority inversion. This may happen because it is imperative for higher priority tasks to execute promptly. System responsiveness decreases as high priority tasks may have strict time constraints or real time response guarantees. Sometimes there is no harm caused by priority inversion as the late execution of the high priority process is not noticed by the system.

88. Solutions of Priority Inversion 91 Priority Ceiling: All of the resources are assigned a priority that is equal to the highest priority of any task that may attempt to claim them. This helps in avoiding priority inversion. Disabling Interrupts: There are only two priorities in this case i.e. interrupts disabled and preemptible . So priority inversion is impossible as there is no third option. Priority Inheritance: This solution temporarily elevates the priority of the low priority task that is executing to the highest priority task that needs the resource. This means that medium priority tasks cannot intervene and lead to priority inversion. No blocking: Priority inversion can be avoided by avoiding blocking as the low priority task blocks the high priority task. Random boosting: The priority of the ready tasks can be randomly boosted until they exit the critical section.

89. Assigning Task Priorities 92 When the number of tasks with different relative deadlines are more than the priority levels supported by the operating system, then some tasks share the same priority value. But the exact method of assigning priorities to tasks can proficiently affect the utilization of processor. If the tasks are randomly selected for sharing the same priority level then the utilization of the processor would be lessen. It is required to select the tasks systematically to share a priority level so that the achievable schedulable utilization would be higher. There are several priority assignment methods used when tasks share the same priority level. Some of the most used methods are:

90. Assigning Task Priorities 93 Uniform Priority Assignment : In this assignment method, all the tasks are uniformly divided among the available priority levels. If the number of priority levels completely divides the number of tasks then uniform division tasks among priority levels can be done easily. Arithmetic Priority Assignment : in this assignment method, an arithmetic progression is formed by the number of tasks assigned to each priority level. For example, If N are number of tasks and p is number of priority levels then N = a + 2a + 3a + 4a + ... + pa where ‘a’ tasks are assigned to highest priority level, ‘2a’ tasks are assigned to next highest priority level and so on

91. Assigning Task Priorities 94 Geometric Priority Assignment : In this assignment method, a geometric progression is formed by the number of tasks assigned to each priority level. For example, If N are number of tasks and p is number of priority levels then N = a + a^2 + a^3 + a^4 + ... + a^p Logarithmic Priority Assignment : In this assignment method, shorter period tasks are allotted distinct priority levels as much as possible and lower priority tasks (tasks with higher period) are combined together and assigned to same priority level so that higher priority tasks would not be affected. For this the tasks are arranged in increasing order of their period. If p max  is the maximum period and p min  is the minimum period among period of all tasks and p is the number of priority levels then, k = ( p max / p min )^(1/p) is calculated,

92. Priority Inheritance 95 Priority Inheritance is the solution to priority inversion. Task L takes the lock. Only when Task H attempts to take the lock is the priority of Task L boosted to that of Task H’s. Once again, Task M can no longer interrupt Task L until both tasks are finished in the critical section. Note that in both priority ceiling protocol and priority inheritance, Task L’s priority is dropped back to its original level once it releases the lock. Also note that both systems only prevent unbounded priority inversion. Bounded priority inversion can still occur. We can only avoid or mitigate bounded priority inversion through good programming practices. Some possible tips include (pick and choose based on your project’s need): Keep critical sections short to cut down on bounded priority inversion time Avoid using critical sections or locking mechanisms that can block a high priority task Use one task to control a shared resource to avoid the need to create locks to protect it

93. Priority Inheritance 96

94. Priority Inheritance 97 Priority Inversion Priority Inheritance 1. In  priority inversion , a higher-priority process is preempted by a lower-priority process. It is a method that is used to eliminate the problems of Priority inversion. 2. It is the inversion of the priorities of the two processes With the help of this, a process scheduling algorithm increases the priority of a process, to the maximum priority of any other process waiting for any resource. 3. It can cause a system to malfunction in our system. Priority inheritance  can lead to poorer worst-case behavior when there are nested locks. 4. Priority inversions can lead to the implementation of corrective measures. Priority inheritance can be implemented such that there is no penalty when the locks do not contend, 5. To deal with the problem of priority inversion we can have several techniques such as  Priority ceiling, Random boosting, etc. It is the basic technique at the application level for managing priority inversion.

95. Mutual Exclusion 98 During concurrent execution of processes, processes need to enter the critical section (or the section of the program shared across processes) at times for execution. It might so happen that because of the execution of multiple processes at once, the values stored in the critical section become inconsistent. In other words, the values depend on the sequence of execution of instructions – also known as a race condition. The primary task of process synchronization is to get rid of race conditions while executing the critical section. This is primarily achieved through mutual exclusion. Mutual exclusion  is a property of  process synchronization  which states that “no two processes can exist in the critical section at any given point of time”. The term was first coined by Dijkstra . Any process synchronization technique being used must satisfy the property of mutual exclusion, without which it would not be possible to get rid of a race condition. 

96. 99

97. 100 Boy A decides upon some clothes to buy and heads to the changing room to try them out. Now, while boy A is inside the changing room, there is an ‘occupied’ sign on it – indicating that no one else can come in. Girl B has to use the changing room too, so she has to wait till boy A is done using the changing room.  Once boy A comes out of the changing room, the sign on it changes from ‘occupied’ to ‘vacant’ – indicating that another person can use it. Hence, girl B proceeds to use the changing room, while the sign displays ‘occupied’ again.   

98. Semaphores 101 In programming, a semaphore is a variable used to control access to a common, shared resource that needs to be accessed by multiple threads or processes. It is similar to a mutex in that it can prevent other threads from accessing a shared resource or critical section.

99. Semaphores 102 In theory, a semaphore is a shared counter that can be incremented and decremented  atomically . For example, Tasks A, B, and C wish to enter the critical section in the image above. They each call semaphoreTake (), which decrements the counting semaphore. At this point, all 3 tasks are inside the critical section and the semaphore’s value is 0. If another task, like Task D, attempts to enter the critical section, it must first call semaphoreTake () as well. However, since the semaphore is 0, semaphoreTake () will tell Task D to wait. When any of the other tasks leave the critical section, they must call semaphoreGive (), which atomically increments the semaphore. At this point, Task D may call semaphoreTake () again and enter the critical section. This demonstrates that semaphores work like a generalized mutex capable of counting to numbers greater than 1. However, in practice, you rarely use semaphores like this, as even within the critical section, there is no way to protect individual resources with just that one semaphore; you would need to use other protection mechanisms, like queues or mutexes to supplement the semaphore. In practice, semaphores are often used to signal to other threads that some common resource is available to use. This works well in producer/consumer scenarios where one or more tasks generate data and one or more tasks use that data

100. 103 In the example above, Tasks A and B (producers) create data to be put into a shared resource, such as a buffer or linked list. Each time they do, they call semaphoreGive () to increment the semaphore. Tasks C and D can read values from that resource, removing the values as they do so (consumers). Each time a task reads from the resource, it calls semaphoreTake (), which decrements the semaphore value.

101. Deadlock 104 Deadlock  is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.  Consider an example when two trains are coming toward each other on the same track and there is only one track, none of the trains can move once they are in front of each other. A similar situation occurs in operating systems when there are two or more processes that hold some resources and wait for resources held by other(s). For example, in the below diagram, Process 1 is holding Resource 1 and waiting for resource 2 which is acquired by process 2, and process 2 is waiting for resource 1. 

102. Deadlock 105 Examples Of Deadlock 1.System has 2 tape drives. P1 and P2 each hold one tape drive and each needs another one. 2.Semaphores A and B, initialize to 1, P0 and P1 are in deadlock as follows: P0 executes wait(A) and preempts. P1 executes wait(B). Now P0 and P1 enters in deadlock. 3.  Assume the space is available for allocation of 200K bytes, adn the following sequence of events occur  P0                 P1                 wait(A);                                      wait(B)                               wait(B);             wait(A)  

103. Deadlock 106 Deadlock can arise if  the  following four conditions hold simultaneously (Necessary Conditions)  Mutual Exclusion:  Two or more resources are non-shareable (Only one process can use at a time)  Hold and Wait:   A process is holding at least one resource and waiting for resources.  No Preemption:  A resource cannot be taken from a process unless the process releases the resource.  Circular Wait:  A set of processes are waiting for each other in circular form.  Methods for handling deadlock   Deadlock prevention or avoidance: Deadlock detection and recovery:  Deadlock ignorance:

104. 1  Deadlock prevention or avoidance: 107 Prevention: The idea is to not let the system into a deadlock state. This system will make sure that above mentioned four conditions will not arise. These techniques are very costly so we use this in cases where our priority is making a system deadlock-free. One can zoom into each category individually, Prevention is done by negating one of above mentioned necessary conditions for deadlock. Prevention can be done in four different ways:        1. Eliminate mutual exclusion                                        3. Allow preemption        2. Solve hold and Wait                                                   4. Circular wait Solution Avoidance: Avoidance is kind of futuristic. By using the strategy of “Avoidance”, we have to make an assumption. We need to ensure that all information about resources that the process will need is known to us before the execution of the process. We use Banker’s algorithm (Which is in turn a gift from Dijkstra ) to avoid deadlock.  In prevention and avoidance, we get correctness of data but performance decreases.        

105. 2) Deadlock detection and recovery:  108 If Deadlock prevention or avoidance is not applied to the software then we can handle this by deadlock detection and recovery. which consist of two phases:  In the first phase, we examine the state of the process and check whether there is a deadlock or not in the system.  If found deadlock in the first phase then we apply the algorithm for recovery of the deadlock. In Deadlock detection and recovery, we get the correctness of data but performance decreases.

106. 3) Deadlock ignorance:   109 If a deadlock is very rare, then let it happen and reboot the system. This is the approach that both Windows and UNIX take. we use the ostrich algorithm for deadlock ignorance. In Deadlock, ignorance performance is better than the above two methods but the correctness of data .

107. Synchronization 110 Synchronization is classified into two categories:  resource synchronization  and  activity synchronization  . Resource synchronization determines whether access to a shared resource is safe, and, if not, when it will be safe. Activity synchronization determines whether the execution of a multithreaded program has reached a certain state and, if it hasn't, how to wait for and be notified when this state is reached. Process Synchronization is the coordination of execution of multiple processes in a multi-process system to ensure that they access shared resources in a controlled and predictable manner. It aims to resolve the problem of race conditions and other synchronization issues in a concurrent system. The main objective of process synchronization is to ensure that multiple processes access shared resources without interfering with each other, and to prevent the possibility of inconsistent data due to concurrent access. To achieve this, various synchronization techniques such as semaphores, monitors, and critical sections are used. In a multi-process system, synchronization is necessary to ensure data consistency and integrity, and to avoid the risk of deadlocks and other synchronization problems. Process synchronization is an important aspect of modern operating systems, and it plays a crucial role in ensuring the correct and efficient functioning of multi-process systems.

108. Inter Task Communications 111 The term  inter-task communication  comprises all mechanisms serving to exchange information among tasks. RTKernel-32 offers three different techniques: semaphores, mailboxes, and message passing. Semaphores  are offered by virtually all multitasking systems. They allow the exchange of signals for activating and suspending tasks. A semaphore is a variable signals can be stored in or read from. Task switches may take place whenever a semaphore containing 0 signals is accessed. RTKernel-32 defines five different types of semaphores: counting, binary, event, resource, and mutex . Mailboxes  extend the concept of semaphores. Instead of signals, data of any type can be stored in or read from a mailbox. A task switch occurs whenever an empty or a full mailbox is accessed. The number of data records a mailbox can store is configurable. Mailboxes are especially suited for data buffering between tasks or between interrupt handlers and tasks. Message passing  serves to exchange data directly between two tasks; specifically, no data or signals will be buffered. This represents the tightest coupling between tasks because the tasks involved must synchronize for the data exchange.

109. Mailboxes 112 A mailbox is simply a storage location, big enough to hold a single variable of type  ADDR  , access to which is controlled so that it may be safely utilized by multiple tasks. One task can write to a mailbox. It is then full, and no task can send to it until a task does a read on the mailbox or the mailbox is reset. Trying to send to a full mailbox or read from an empty one may result in an error or task suspension, depending on options selected in the API call and the Nucleus SE configuration In some OS implementations, mailboxes are not implemented, and the use of a single-entry queue is recommended as an alternative. This sounds reasonable, as such a queue would provide the same functionality as a mailbox. However, a queue is a rather more complex data structure than a mailbox and carries considerably more overhead in data (head and tail pointers etc.), code and execution time. With Nucleus SE, like Nucleus RTOS, you have the choice of both object types and can make the decision for yourself. It is worth considering the alternative approach if your application includes multiple queues, but perhaps a single mailbox. Replacing that mailbox with a queue will incur a small data overhead, but eliminates all the mailbox-related API code. It would be very easy to configure the application both ways and compare the memory footprints and performance. .

110. Message Queues 113 An RTOS is software that manages the time of a central processing unit (CPU), a microprocessing unit (MPU), or even a digital signal processor (DSP) as efficiently as possible. Most RTOS kernels are written in C and require a small portion of code written in ASSEMBLY language to adapt the kernel to different CPU architectures.

111. 114 a message queue is a  kernel object  (i.e., a data structure) through which  messages  are sent (i.e., posted) from either interrupt service routines (ISRs) or tasks to another task (i.e., pending). An application can have any number of message queues, each one having its own purpose. For example, a message queue can be used to pass packets received from a communication interface ISR to a task, which in turn would be responsible for processing the packet. Another queue can be used to pass content to a display task that will be responsible for properly updating a display.

112. 115 Messages are typically void pointers to a storage area containing the actual message. However, the pointer can point to anything, even a function for the receiving task to execute. The meaning of the message is thus application-dependent. Each message queue is configurable in the amount of storage it will hold. A message queue can be configured to hold a single message (a.k.a., a mailbox) or  N  messages. The size of the queue depends on the application and how fast the receiving task can process messages before the queue fills up. 

113. 116 A message queue is typically implemented as first-in-first-out (FIFO), meaning that the first message received will be the first message extracted from the queue. However, some kernels allow you to send messages that are deemed more important than others, and thus post at the head of the queue. In other words, in last-in-first-out (LIFO) order, making that message the first one to be extracted by the task. One important aspect of a message queue is that the message itself needs to remain in scope from the time it’s sent to the time it’s processed. This implies that you cannot pass a pointer to a stack variable, a global variable that could be altered by other code, and so on

114. Message Queue mechanism 117 1.  The counting semaphore is initialized with a value corresponding to the maximum number of entries that the queue can accept.  2.  The sending task pends on the semaphore before it’s allowed to post the message to the queue. If the semaphore value is zero, the sender waits.  3.  If the value is non-zero, the semaphore count is decremented, and the sender post its message to the queue.  4.  The recipient of the message pend one the message queue as usual.  5.  When a message is received the recipient extracts the pointer to the message from the queue and signals the semaphore, indicating that an entry in the queue has been freed up. 

115. use of message queues 118 Message queues are typically used to send messages from an ISR or a task to another task However, you don’t have to send an actual message and allocate storage area if the message fits within the word size of a pointer. For example, if a pointer is 32 bits wide then you can cast an analog to digital converter (ADC) reading from a 12-bit ADC to a pointer and send it through the message queue. As long as the recipient knows to cast the value back to an integer, it’s perfectly legal. A task can use the timeout mechanism to delay itself for a certain amount of time if it knows that the messages will not be sent to it. In this case, a queue capable of holding a single entry would be sufficient. In fact, if another task or ISR sends a message, the delay would be aborted which could be the behavior you’d want to implement. A message queue can be used as a semaphore to simply signal to a task that an event occurred. In this case, the message can be anything. The size of the queue would depend on how many signals the application would need to  buffer . A message queue can be used as a semaphore to simply signal to a task that an event occurred. In this case, the message can be anything. The size of the queue would depend on how many signals the application would need to  buffer . Messages can actually be used to emulate event flags where each bit of a 32-bit pointer size variable (cast to an integer) can represent an event.

116. use of message queues 119

117. Difference between message queues and mailboxes 120 A queue in standard has very particular that means in computing as a box facts shape with first-in-first-out (FIFO) get right of entry to semantics. In an RTOS queue specifically, get the right of entry to the queue could be thread-secure and feature blocking off semantics.   A mailbox alternatively has no usually time-honored unique semantics, and I even have visible the time period used to consult very extraordinary RTOS IPC mechanisms. In a few instances, there are in truth queues, however, if the RTOS additionally helps an IPC queue, a mailbox may have someway extraordinary semantics – frequently with appreciation to reminiscence management. In different instances a mailbox may also basically be a queue of period 1 – i.e. it has the blocking off and IPC functionality of a queue, however, and not using a buffering. Such a mechanism lets in synchronous conversation among processes.

118. Clock Tick 121 Same as a cycle, the smallest unit of time recognized by a device. For personal computers, clock ticks generally refer to the main system clock, which runs at 66 MHz. This means that there are 66 million clock ticks (or cycles) per second. Since modern CPUs run much faster (up to 3 GHz), the CPU can execute several instructions in a single clock tick.

119. 122 When sleeping, an RTOS task will specify a time after which it requires 'waking'. When blocking, an RTOS task can specify a maximum time it wishes to wait.The FreeRTOS real time kernel measures time using a  tick  count variable. A timer interrupt (the RTOS  tick interrupt ) increments the tick count with strict temporal accuracy - allowing the real time kernel to measure time to a resolution of the chosen timer interrupt frequency. Each time the tick count is incremented the real time kernel must check to see if it is now time to unblock or wake a task. It is possible that a task woken or unblocked during the tick ISR will have a priority higher than that of the interrupted task. If this is the case the tick ISR should return to the newly woken/unblocked task - effectively interrupting one task but returning to another.

120. 123 At (1) the RTOS idle task is executing. At (2) the RTOS tick occurs, and control transfers to the tick ISR (3). The RTOS tick ISR makes vControlTask ready to run, and as vControlTask has a higher priority than the RTOS idle task, switches the context to that of vControlTask . As the execution context is now that of vControlTask , exiting the ISR (4) returns control to vControlTask , which starts executing (5).

121. Memory Requirements 124 A typical RTOS will load the CPU less than 4%, require less than 16 KB of flash space and  less than 4 KB of RAM . In most cases, the issues with performance and memory are related to how the developer is using the RTOS and gaps in their knowledge on how to properly use and configure the RTOS. Memory management keeps track of the status of each memory location, whether it is allocated or free. It allocates the memory dynamically to the programs at their request and frees it for reuse when it is no longer needed. Memory management meant to satisfy some requirements that we should keep in mind.

122.  Requirements of memory management 125 Relocation –  The available memory is generally shared among a number of processes in a multiprogramming system, so it is not possible to know in advance which other programs will be resident in main memory at the time of execution of this program. Swapping the active processes in and out of the main memory enables the operating system to have a larger pool of ready-to-execute process. Protection –  There is always a danger when we have multiple programs at the same time as one program may write to the address space of another program. So every process must be protected against unwanted interference when other process tries to write in a process whether accidental or incidental. Between relocation and protection requirement a trade-off occurs as the satisfaction of relocation requirement increases the difficulty of satisfying the protection requirement. Sharing –  A protection mechanism must have to allow several processes to access the same portion of main memory. Allowing each processes access to the same copy of the program rather than have their own separate copy has an advantage. Logical organization –  Main memory is organized as linear or it can be a one-dimensional address space which consists of a sequence of bytes or words. Most of the programs can be organized into modules, some of those are unmodifiable (read-only, execute only) and some of those contain data that can be modified. To effectively deal with a user program, the operating system and computer hardware must support a basic module to provide the required protection and sharing. 

123. 126 Physical organization –  The structure of computer memory has two levels referred to as main memory and secondary memory. Main memory is relatively very fast and costly as compared to the secondary memory. Main memory is volatile. Thus secondary memory is provided for storage of data on a long-term basis while the main memory holds currently used programs

124. 51 * 127