Processes and operating systems

Embedded and Real Time Systems

1. PROCESSES AND OPERATING SYSTEMS T.Ramprakash AP( Sr.Gr )/ECE Ramco Institute of Technology Rajapalayam 1

2. Flow of syllabus Introduction Multiple tasks and multiple processes Multirate systems Preemptive real-time operating systems Priority based scheduling Interprocess communication mechanisms Evaluating operating system performance Power optimization strategies for processes Example Real time operating systems POSIX Windows CE 2

3. Multiple tasks and multiple processes Process Multiprogramming Multitasking Multiprocessing Multithreading 3

4. Process A single execution of a program is called as Process. If we run the same program two different times , we have created two different processes . Each process has its own state that includes not only its registers but all of its memory . In some OSs , the memory management unit is used to keep each process in a separate address space. In others, particularly lightweight RTOSs , the processes run in the same address space . Processes that share the same address space are often called threads 4

5. Multiprogramming Multiprogramming is also the ability of an operating system to execute more than one program on a single processor machine. More than one task/program/job/process can reside into the main memory at one point of time. A computer running excel and firefox browser simultaneously is an example of multiprogramming. 5

6. Memory Layout for Multiprogramming System 6

7. Multitasking 7

8. Multitasking Multitasking is the ability of an operating system to execute more than one task simultaneously on a single processor machine. Though we say so but in reality no two tasks on a single processor machine can be executed at the same time . Actually CPU switches from one task to the next task so quickly that appears as if all the tasks are executing at the same time . 8

9. Multitasking System 9

10. Multiprocessing Multiprocessing is the ability of an operating system to execute more than one process simultaneously on a multi processor machine. In this, a computer uses more than one CPU at a time. 10

11. Multithread Threads are the light wait processes which are independent part of a process or program Processes that share the same address space are often called threads 11

12. Multithread Multithreading is the ability of an operating system to execute the different parts of a program called threads at the same time . Threads are the light wait processes which are independent part of a process or program . In multithreading system, more than one threads are executed parallel on a single CPU. 12

13. Threads vs Process Thread Process Thread is a single unit of execution and is part of process Process is a program in execution and contains one or more threads . A thread does not have its own data memory and heap memory . It shares the data memory and heap memory with other threads of the same process. Process has its own code memory, data memory and stack memory A thread cannot live independently ; it lives within the process A process contains at least one thread Threads are very inexpensive to create Processes are very expensive to create . Involves many OS overhead Context switching is inexpensive and fast Context switching is complex and involves lot of OS overhead and is comparatively slower. If a thread expires, its stack is reclaimed by process If a process dies, the resources allocated to it are reclaimed by the OS and all the associated threads of the process also dies 13

14. Tasks and Processes 14

15. Multirate Systems In multirate systems, certain operation must be executed periodically and each operation is executed at its own rate Ex, Automobile engines, Printers, Cellphones 15

16. Multirate Systems Timing Requirements on processes CPU Usage Metrics Process state and Scheduling Running Periodic processes 16

17. Timing Requirements on processes Each process have several different types of timing requirements Timing requirements strongly influence the type of scheduling Scheduling policy must define the timing requirements that it uses to determine whether a schedule is valid 17

18. Timing Requirements on processes Two important requirements on process : Initiation Time: Deadline Initiation Time : Process goes from waiting state to ready state Deadline It specifies when a computation must be finished 18

19. Timing Requirements on processes 19

20. Timing Requirements on processes 20

21. Sequence of process with a high initiation rate Rate Requirement : it specifies how quickly processes must be initiated Period : It is the time between successive executions 21

22. Jitter : Jitter is the delay between the time when task shall be started , and the time when the task is being started Missing a deadline : Variety of actions can be taken when missing a deadline 22

23. Data Dependencies among process DAG : A directed acyclic graph ( DAG) is a directed graph that contains no cycles A set of processes with data dependencies is known as a task graph 23

24. Communication among processes at different rates 24

25. CPU usage metrics The initiation time is the time at which a process actually starts executing on the CPU . The completion time is the time at which the process finishes its work. The most basic measure of work is the amount of CPU time expended by a process . The CPU time of process i is called C i . CPU time is not equal to the completion time minus initiation time ; several other processes may interrupt execution. 25

26. CPU usage metrics The simplest and most direct measure is Utilization : Utilization is the ratio of the CPU time that is being used for useful computations to the total available CPU time. 26

27. CPU usage metrics This ratio ranges between 0 and 1, with 1 meaning that all of the available CPU time is being used for system purposes. The utilization is often expressed as a percentage . If we measure the total execution time of all processes over an interval of time t , then the CPU utilization is 27

28. Process State and Scheduling The work of choosing the order of running processes is known as scheduling Scheduling States Waiting Ready Executing 28

29. Running Periodic Process While Loop Multiple Timers 29

30. Pre-emptive real-time operating systems Preemptive real time operation system solves the fundamental problems of cooperative multitasking system A RTOS executes processes based upon timing constraints provided by the system designer . The most reliable way to meet timing constraints accurately is to build a preemptive OS and to use priorities to control what process runs at any given time 30

31. Preemptive real-time operating systems Two Important Methods Preemption Priorities Process and Context Processes and Object Oriented Design 31

32. Preemption Pre-emption is an alternative to the C function call as a way to control execution Creating new routines that allow us to jump from one subroutine to another at any point in the program 32

33. Pre-emption The kernel is the part of the OS that determines what process is running Length of the timer period is known as Time Quantum 33

34. Context Switching The set of registers that defines a process is known as context The switching from one process’s register set to another is known as context switching The data structure that holds the state of process is known as record 34

35. Process Priorities Each process is assigned with the numerical priority Kernel simply look at the processes and their priorities and select the highest priority process that is ready to run 35

36. Process and Context A process is known as FreeRTOS.org as a task Lets assume that , everything has been initialized, the operating system is running and we are ready for a timer interrupt 36

37. Process and Context 37

38. vPreemptiveTick 38

39. portSAVE_CONTEXT 39

40. Process and Object oriented design UML often refers to processes as active objects , that is, objects that have independent threads of control. The class that defines an active object is known as an active class . It has all the normal characteristics of a class , including a name , attributes and operations . It also provides a set of signals that can be used to communicate with the process. 40

41. Process and Object oriented design It is a simple collaboration diagram in which an object is used as an interface between two processes 41

42. Priority Based Scheduling Round-Robin Scheduling Process Priorities Rate Monotonic Scheduling Earliest Deadline first scheduling Shared Resources Priority Inversion 42

43. Round-Robin Scheduling Round Robin is the pre-emptive process scheduling algorithm. Each process is provided a fix time to execute, it is called a quantum . Once a process is executed for a given time period, it is preempted and other process executes for a given time period. Context switching is used to save states of preempted processes. 43

44. Round-Robin Scheduling 44

45. Round-Robin Scheduling 45

46. Process Priorities Priority scheduling is a non- preemptive algorithm and one of the most common scheduling algorithms in batch systems. Each process is assigned a priority . Process with highest priority is to be executed first and so on. Processes with same priority are executed on first come first served basis . Priority can be decided based on memory requirements, time requirements or any other resource requirement. 46

47. Process Priorities 47

48. Rate Monotonic scheduling Rate-monotonic scheduling (RMS) , introduced by Liu and Layland It is one of the first scheduling policies developed for real-time systems and is still very widely used Rate Monotonic Scheduling (RMS) assigns task priorities in the order of the highest task frequencies, i.e. the shortest periodic task gets the highest priority , then the next with the shortest period get the second highest priority, and so on. 48

49. Rate Monotonic scheduling This model uses a relatively simple model of the system All processes run periodically on a single CPU. Context switching time is ignored . There are no data dependencies between processes. The execution time for a process is constant. All deadlines are at the ends of their periods. The highest-priority ready process is always selected for execution. 49

50. Rate Monotonic scheduling 50

51. Rate Monotonic scheduling The fraction is the fraction of time that the CPU spends executing task i . It is possible to show that for a set of two tasks under RMS scheduling, the CPU utilization U will be no greater than 2 ( 2 1 / 2 - 1 ) ∼ 0 . 83 In other words, the CPU will be idle at least 17% of the time 51

52. Rate Monotonic scheduling example1 Process Execution Time Period P1 1 3 P2 1 4 P3 2 5 Schedule the process given below using Earliest Deadline First(EDF) scheduling policy. Compute the schedule for an interval equal to the least common multiple of the process . Assume the time starts at t=0. 52

53. Rate Monotonic scheduling example2 Process Execution Time Period P1 2 30 P2 4 40 P3 7 120 P4 5 60 P5 1 15 Schedule the process given below using Earliest Deadline First(EDF) scheduling policy and Rate Monotonic Scheduling 53

54. Earliest Dead line first scheduling Earliest Deadline First ( EDF) is a dynamic priority algorithm The priority of a job is inversely proportional to its absolute deadline ; In other words, the highest priority job is the one with the earliest deadline; 54

55. Earliest Dead line first scheduling Example Execution Time Period T1 1 4 T2 2 6 T3 3 8 55

56. Earliest Dead line first scheduling Observe that at time 6, even if the deadline of task 3 is very close , the scheduler decides to schedule task 2 . This is the main reason why T3 misses its deadline Execution Time Period T1 1 4 T2 2 6 T3 3 8 56

57. Earliest Dead line first scheduling Observe that at time 6, the problem does not appear, as the earliest deadline job is executed. 57

58. Shared Resources While dealing with shared resources, special care must be taken Race Condition Critical Sections Semaphores 58

59. Shared Resources Race Condition Consider the case in which an I/O device has a flag that must be tested and modified by a process Problems may arise when other processes may also want to access the device If combinations of events from the two task operate on the device in the wrong order, we may create a critical timing race or race condition 59

60. Shared Resources Critical Sections To prevent the race condition problems , we need to control the order in which some operations occur We need to be sure that a task finishes an I/O operations before allowing another task to starts its own operation on that I/O device This is achieved by enclosing sensitive sections of code in a critical section that executes without interruption 60

61. Shared Resources Semaphores We create a critical section using semaphores , which are primitive provided by the OS The semaphore is used to guard a resource we start a critical section by calling a semaphore function that does no return until the resource is available When we are done with the resource we use another semaphore function to release it P(); //wait for semaphore //do protected work here V(); //release semaphore 61

62. Priority Inversion A low priority process blocks execution of a higher priority process by keeping hold of its resource. This is Priority Inversion . This priority inversion is dealt with Priority Inheritance In priority inheritance , Promotes the priority of the process temporarily The priority of the process becomes higher than that of any other process that may use the resource. Once the process is finished with the resource, its priority is demoted to its normal value . 62

63. INTERPROCESS COMMUNICATION MECHANISMS Inter-process communication mechanisms are provided by the operating system as part of the process abstraction. Two ways of communication Blocking Communication The process goes into waiting state until it receives a response Non Blocking Communication It allows the process to continue execution after sending the communication 63

64. INTERPROCESS COMMUNICATION MECHANISMS Four major styles of inter-process communication Shared Memory Message passing Signals Mailboxes 64

65. Shared Memory CPU and I/O device communicate through a shared memory location 65

66. Message passing Each communicating entity has its own message send/receive unit The message is stored in the senders/receivers endpoints 66

67. Message passing For example, a home control system has one microcontroller per household device – lamp, fan, and so on. The device must communicate relatively infrequently Their physical separation is large enough that we would not naturally have a sharing a central pool of memory Passing communication packets among the device is a natural implementation of communication in many 8 bit controllers 67

68. Signals Another form of inter-process communication commonly used in Unix is Signal A signal is analogous to an interrupt , but it is entirely a software creation A signal is generated by a process and transmitted to another process by Operating System 68

69. Mailboxes It is a asynchronous communication Mailboxes have a fixed number of bits and can be used for small messages We can also implement a mailbox using P() and V() using main memory for the mailbox storage Mail box should contain two items: Message Mail ready Flag 69

70. Mailboxes void post(message * msg ) { P( mailbox.sem ); //wait for the mailbox copy(mailbox.data.msg); mailbox.flag =TRUE; V( mailbox.sem ) //release the mailbox } 70

71. Mailboxes Boolean pickup(message * msg ) { boolean pickup =False P( mailbox.sem ); //wait for the mailbox pickup= mailbox.flag ; mailbox.flag =FALSE; copy( msg.mailbox.data ); V( mailbox.sem ) //release the mailbox return (pickup) } 71

72. Evaluating Operating System Performance Assumption Context switches requires zero time Ignored interrupts Execution time of process is constant Ignored cache conflicts 72

73. Evaluating Operating System Performance Context Switching Time Interrupt Latency Critical Section and interrupt latency Interrupt priorities and interrupt latency RTOS performance evaluation tools Cache and RTOS performance 73

74. Power optimization strategies for processes The RTOS and system architecture can use static and dynamic power management mechanism A power management policy is a strategy for determining when to perform certain power management operations It examines the state of the system to determine when to take actions 74

75. Power optimization strategies for processes Power down trade offs Predictive power management Advanced Configuration and Power Interface 75

76. Power down trade offs Going in to low power mode takes time The more that is shut off, the longer the delay incurred during restart Avoiding a power down mode can cost unnecessary power Powering down too soon can cause severe performance penalties The best method is to power up the system when a request is received . This works as long as the delay in handling the request is acceptable. 76

77. Predictive Power Management Here, we predict when the next request will be made and to start the system just before that time , saving the requestor the startup time We guess about the activity patterns based on a probabilistic model of expected behavior Because they relay on statistics, they may not always correctly guess the time of next activity They can cause two types of problems The requestor may have to wait for an activity period The system may restart itself when no activity is imminent 77

78. Predictive Power Management A simple predictive technique is to use fixed times For example, if a system does not receive inputs during an interval of length T ON , it shuts down A powered down system waits for a period T OFF before returning to the power on mode The choice of T ON and T OFF must be determined by experimentations 78

79. L shaped distribution Srivastava and Eustace found one a graphic terminal in which they plotted the observed idle time (T OFF ) of a graphics terminal versus the immediately preceding active time (T ON ) The idle period after a long active period is usually very short and the length of the idle period after a short active period is uniformly distributed 79

80. Architecture of Power managed System Service provider whose power is being managed Service Requestor  making request of the power managed system Queue  hold pending requests Power manager  sends power management commands Service Provider Queue Service Requestor Power Manager Request Commands Observations 80

81. Advanced Configuration and Power Interface (ACPI) The Advanced Configuration and Power Interface (ACPI) is an open industry standard for power management services. It is designed to be compatible with a wide variety of OSs. It was targeted initially to PCs . The OS has its own power management module that determines the policy Then OS uses ACPI to send the required controls to the hardware and to observe the hardware’s state as input to the power manager. 81

82. Advanced Configuration and Power Interface (ACPI) 82

83. (ACPI) ACPI supports the following five basic global power states: G3 , the mechanical off state , in which the system consumes no power. G2 , the soft off state , which requires a full OS reboot to restore the machine to working condition . This state has four sub states : S1 , a low wake-up latency state with no loss of system context; S2 , a low wake-up latency state with a loss of CPU and system cache state; S3 , a low wake-up latency state in which all system state except for main memory is lost ; and S4 , the lowest-power sleeping state, in which all devices are turned off. G1 , the sleeping state , in which the system appears to be off and the time required to return to working condition is inversely proportional to power consumption. G0 , the working state , in which the system is fully usable. 83

84. Example of RTOS POSIX Windows CE 84

85. POSIX Portable Operating System Interface POSIX.1 – Core services POSIX.1b – Real-time extensions POSIX.1c – Thread extensions 85

86. POSIX POSIX is a version of Unix Operating system It is created by a standards organization POSIX-complaint operation system are source code compatible ( i.e ) An application can be complied and run without modification on a new POSIX Many RTOS are POSIX compliant and it serves as a good model for basic RTOS techniques 86

87. POSIX Two methods have been proposed to improve interrupt latency Dual Kernel co-kernel for real time process and Standard kernel for non real time processes PREEMP_RT mode It provides priority inheritance to reduce the latency of many kernel operations 87

88. POSIX 88

89. Processes in POSIX In POSIX, a new process is created by making a copy of an existing process The copying process creates two different processes both running the same code The complication comes in ensuring that one process runs the code intended for the new process while the other process continues the work of the old process 89

90. Processes in POSIX A process makes a copy of itself by calling fork() function It creates a new child process which is exact copy of parent process The both have the same code and the same data values with one exceptions  return value Parent Process: returns the process ID of the child process Child process: returns 0 90

91. POSIX fork() childid = fork(); if ( childid == 0) { /* Do the child process*/ } 91

92. Processes in POSIX It would be clumsy to have both processes have all the code for both parent and child processes POSIX provides the exec facility for overloading the code in a process It takes as argument the name of the file that holds the child’s code and the array of arguments 92

93. Processes in POSIX The code that follows the call to perror () and exit(), take care of the case where execv () fails and returns to the parent process 93

94. Real time scheduling in POSIX POSIX supports real time scheduling in the _POSIX_PRIORITY_SCHEDULING resource The sched_setscheduler () function is used to determine a process’s scheduling policy and other parameters i = sched_setscheduler ( process_id , SCHED_FIFO , & sched_params ) SCHED_FIFO , SCHED_RR, SCHED_OTHER sched_getparams () function returns the current parameter values for a process sched_setparams () changes the parameter values 94

95. POSIX POSIX supports Semaphores Shared memory mechanism Message Queues 95

96. POSIX semaphores POSIX supports counting semaphores in the _POSIX_SEMAPHORES option A Counting semaphore allows more than one process to access a resource at a time If a semaphore allows up to to N resources , then it will not block until N process have simultaneously passed the semaphore 96

97. POSIX semaphores Names for the semaphore start with “ / ” sem_open () – To create a semaphore sem_close () – To destroy a semaphore sem_wait () – getting a semaphore sem_post () – releasing a semaphore 97

98. POSIX Shared Memory Shared memory functions create blocks of memory that can be used by several processes shm_open () close () mmap () munmap () 98

99. POSIX Message Queues POSIX supports message queues No need to create a queue before creating a process mq_open () – to create named queue mq_close () – to destroy named queue mq_send () – to transmit a message mq_receive () – to receive a message mq_maxmsg () – Maximum number of messages mq_msgsize () – Maximum size of a message 99

100. Windows CE Windows CE supports devices such as smartphones, electronic instruction, etc., Windows CE is designed to run on multiple hardware platforms and instruction set architectures 100

101. Windows CE Architecture Win32 API manage access to the operation system 101

102. Windows CE Architecture OEM Adaption Layer (OAL) provides an interface to the hardware ( OEM  Original Equipment Manufacturer ) 102

103. Windows CE memory space Windows CE provides support for virtual memory with a flat 32 bit virtual address space Memory space is divided into kernel and user space 103

104. Windows CE memory space User space is divided into System elements and User elements 104

105. Windows CE threads and drivers Windows CE supports two kernel-level units of execution Thread Threads are defined by executable files A process can run multiple threads All the threads of a process share the same execution environment Threads in different processes run in different execution environment Threads are scheduled directly by the OS Driver Drivers are defined by dynamically linked libraries (DLL) A driver may be loaded in to the OS or a process Drivers can create threads to handle interrupts 105

106. Windows CE Scheduling Each thread is assigned an integer priority Lower valued priorities have highest priority is the highest priority and 255 is the lowest Task may be scheduled using either of two policies A thread can run until the end of its quantum (or) A thread can run until a higher priority thread is ready to run 106

107. Windows CE Interrupts The Interrupt Service Handler (ISH) is a kernel service that provides the first response to the interrupt The ISH selects an Interrupt Service Routine (ISR) to handle the interrupt The ISH runs in the kernel with interrupts turned off The ISR in turn calls An Interrupt Service Thread (IST) which perform most of the work required to handle the interrupt 107