OS UNIT-II-PPT.pptx-operating systems complete notes

Operating systems unit 2 notes

1. UNIT II SYLLABUS Process Concept : 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Process scheduling, Operations on processes, Inter-process communication, C o mm uni c a tion in cl i e n t server mo d els, systems. Multithreaded Programming: Multithreading Thread libraries, Threading issues, Examples. Process Scheduling: Basic concepts, Scheduling criteria, Scheduling algorithms, Multiple processor scheduling, Thread scheduling, Examples. Inter-process Communication: Race conditions, Critical Regions, Mutual exclusion with busy waiting, Sleep and wakeup, Semaphores, Monitors, Message pa s s i n g , Barriers, Cl a s s i c al IPC - Din i n g phil o s o phe r s p r ob l em, R ead e r s and w r i t e r s Mutexes, P r o blems problem

2. Processes Process Concept : Process scheduling, Operations on processes, Inter-process communication, Communication in client server systems. Multithreaded Programming: Multithreading models, Thread libraries, Threading issues, Examples. UNIT – 2 PART - 1 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

3. Obje c ti v es 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition To introduce the notion of a process -- a program in execution, which forms the basis of all computation To describe the various features of processes, including scheduling, creation and termination, and communication To explore inter-process communication using shared memory and message passing To describe communication in client-server systems

4. P r oce s s – a p r og r am i n e x ecutio n ; p r o c ess e x ecution mu s t p r og r e s s in sequential fashion Multiple parts The program code, also called text section Current activity including program counter , processor registers Process includes : Stack containing temporary data Function parameters, return addresses, local variables Data section containing global variables Heap containing memory dynamically allocated during run time Program is passive entity stored on disk (executable file), process is active Program becomes process when executable file loaded into memory Execution of program started via GUI mouse clicks, command line entry of its name, etc One program can be several processes Consider multiple users executing the same program 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition PROCESS CONCEPT

5. Process in Memory 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

6. Process State As a process executes, it changes state new : The process is being created running : Instructions are being executed waiting : The process is waiting for some event to occur ready : The process is waiting to be assigned to a processor terminated : The process has finished execution 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

7. Diagram of Process State Or Lifecycle of a Process 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

8. Process Control Block (PCB) A process control block (PCB) is a data structure used by computer operating systems to store all the information about a process. When a process is created (initialized or installed), the operating system creates a corresponding process control block. Process control block includes CPU scheduling, I/O resource management, file management information etc. If that process gets suspended, the contents of the registers are saved on a stack and the pointer to the particular stack frame is stored in the PCB. By this technique, the hardware state can be restored so that the process can be scheduled to run again. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

9. Process Control Block (PCB) Process control block includes CPU scheduling, I/O resource management, file management information etc. If that process gets suspended, the contents of the registers are saved on a stack and the pointer to the particular stack frame is stored in the PCB. By this technique, the hardware state can be restored so that the process can be scheduled to run again. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

10. Process Control Block (PCB) A Process Control Block is a data structure maintained by the Operating System for every process. The PCB is identified by an integer process ID (PID). A PCB keeps all the information needed to keep track of a process as listed below in the table − 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

11. CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition S.N. Information & Description 1 Process State The current state of the process i.e., whether it is ready, running, waiting, or whatever. 2 Process privileges This is required to allow/disallow access to system resources. 3 Process ID Unique identification for each of the process in the operating system. 4 Pointer A pointer to parent process. 5 Program Counter Program Counter is a pointer to the address of the next instruction to be executed for this process. 6 CPU registers Various CPU registers where process need to be stored for execution for running state. 7 CPU Scheduling Information Process priority and other scheduling information which is required to schedule the process. 8 Memory management information This includes the information of page table, memory limits, Segment table depending on memory used by the operating system. 9 Accounting information This includes the amount of CPU used for process execution, time limits, execution ID etc. 10 IO status information This includes a list of I/O devices allocated to the process.

12. CONTD.. The architecture of a PCB is completely dependent on Operating System and may contain different information in different operating systems. Here is a simplified diagram of a PCB − The PCB is maintained for a process throughout its lifetime, and is deleted once the process terminates. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

13. CPU Switch From Process to Process CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

14. Process Scheduling 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Definition Scheduling is a method that is used to distribute valuable computing resources, ususally process threads, data flows and applications that need them. Scheduling is done to balance the load on the system and ensure equal distribution of resources and give some set of rules.

15. Operating System - Process Scheduling 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Definition The process scheduling is the activity of the process manager that handles the removal of the running process from the CPU and the selection of another process on the basis of a particular strategy. Process scheduling is an essential part of a Multiprogramming operating systems. Such operating systems allow more than one process to be loaded into the executable memory at a time and the loaded process shares the CPU using time multiplexing.

16. Process Scheduling Queues The OS maintains all PCBs in Process Scheduling Queues. The OS maintains a separate queue for each of the process states and PCBs of all processes in the same execution state are placed in the same queue. When the state of a process is changed, its PCB is unlinked from its current queue and moved to its new state queue. The Operating System maintains the following important process scheduling queues − Job queue − This queue keeps all the processes in the system. Ready queue − This queue keeps a set of all processes residing in main memory, ready and waiting to execute. A new process is always put in this queue. D e vi c e que u e s − Th e p r ocesses which a r e bloc k ed du e to unavailability of an I/O device constitute this queue. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

17. CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

18. The OS can use different policies to manage each queue (FIFO, Round Robin, Priority, etc.). The OS scheduler determines how to move processes between the ready and run queues which can only have one entry per processor core on the system; in the above diagram, it has been merged with the CPU. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

19. Two-State Process Model Two-state process model refers to running and non- running states which are described below − 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD.. S.No. State & Description 1 Running: When a new process is created, it enters into the system as in the running state. 2 Not Running: Processes that are not running are kept in queue, waiting for their turn to execute. Each entry in the queue is a pointer to a particular process. Queue is implemented by using linked list. Use of dispatcher is as follows. When a process is interrupted, that process is transferred in the waiting queue. If the process has completed or aborted, the process is discarded. In either case, the dispatcher then selects a process from the queue to execute.

20. Schedulers Schedulers are special system software which handle process scheduling in various ways. Their main task is to select the jobs to be submitted into the system and to decide which process to run. Schedulers are of three types − Long-Term Scheduler Short-Term Scheduler Medium-Term Scheduler 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

21. Long Term Scheduler It is also called a job scheduler . A long-term scheduler determines which 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition p r og r ams a r e admitted to the system for processing. It selects processes from the queue and loads them into memory for execution. Process loads into the memory for CPU scheduling. The primary objective of the job scheduler is to provide a balanced mix of jobs, such as I/O bound and processor bound. It also controls the degree of multiprogramming. If the degree of multiprogramming is stable, then the average rate of process creation must be equal to the average departure rate of processes leaving the system. CONTD..

22. Short Term Scheduler It is also called as CPU scheduler . Its main objective is to increase system performance in accordance with the chosen set of criteria. It is the change of ready state to running state of the process. CPU scheduler selects a process among the processes that are ready to execute and allocates CPU to one of them. Short-term schedulers, also known as dispatchers, make the decision of which process to execute next. Short-term schedulers are faster than long-term schedulers. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

23. Medium Term Scheduler Medium-term scheduling is a part of swapping . It removes the processes from the memory. It reduces the degree of multiprogramming. The medium-term scheduler is in-charge of handling the swapped out-processes. A running process may become suspended if it makes an I/O request. A suspended processes cannot make any progress towards completion. In this condition, to remove the process from memory and make space for other processes, the suspended process is moved to the secondary storage. This process is called swapping , and the process is said to be swapped out or rolled out. Swapping may be necessary to improve the process mix. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

24. Process Representation in Linux Represented by the C structure 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition task_struct pid t_pid; /* process identifier */ long state; /* state of the process */ unsigned int time_slice /* scheduling information */ struct task_struct *parent; /* this process ’ s parent */ struct list_head children; /* this process ’ s children */ struct files_struct *files; /* list of open files */ struct mm_struct *mm; /* address space of this process */ CONTD..

25. Ready Queue And Various I/O Device Queues CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

26. Representation of Process Scheduling Queueing diagram represents queues, resources, flows CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

27. Context Switch When CPU switches to another process, the system must save the state of the old process and load the saved state for the new process via a context switch Context of a process represented in the PCB Context-switch time is overhead; the system does no useful work while switching The more complex the OS and the PCB  the longer the context switch Time dependent on hardware support Some hardware provides multiple sets of registers per CPU  multiple contexts loaded at once 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

28. OPERATIONS ON PROCESSES 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition System must provide mechanisms for: process creation, process termination,

29. Process Creation Parent process create children processes, which, in turn create other processes, forming a tree of processes Generally, process identified and managed via a process identifier ( pid ) Resource sharing options Parent and children share all resources Children share subset of parent ’ s resources Execution options Parent and children execute concurrently Parent waits until children terminate 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

30. A Tree of Processes in Linux init pi d = 1 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition sshd pi d = 3028 login pi d = 8415 kthreadd pi d = 2 sshd pi d = 3610 pdflush pi d = 200 khelper pi d = 6 tcsch pi d = 4005 emacs pi d = 9204 bash pi d = 8416 ps pi d = 9298 CONTD..

31. Address space Child duplicate of parent Child has a program loaded into it UNIX examples fork() system call creates new process exec( ) sys t em call use d after a fork ( ) t o r e plac e t h e p r oces s ’ memory space with a new program CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

32. C Program Forking Separate Process CONTD.. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

33. Process Termination Process executes last statement and then asks the operating system to delete it using the exit() system call. Returns status data from child to parent (via wait() ) Process ’ resources are deallocated by operating system 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Parent may terminate the execution of children processes abort() system call. Some reasons for doing so: Child has exceeded allocated resources Task assigned to child is no longer required using the Th e paren t i s ex i t ing and t h e o peratin g s y st e ms doe s n o t al l o w a child to continue if its parent terminates CONTD..

34. Some operating systems do not allow child to exists if its parent has terminated. If a process terminates, then all its children must also be terminated. cascading termination. All children, grandchildren, etc. are terminated. The termination is initiated by the operating system. The parent process may wait for termination of a child process by using the wait() system call . The call returns status information and the pid of the terminated process pid = wait(&status); If no parent waiting (did not invoke wait() ) process is a zombie If parent terminated without invoking wait , process is an orphan 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition CONTD..

35. Interprocess Communication 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Inter process communication (IPC) is a mechanism which allows processes to communicate with each other and synchronize their actions. Processes within a system may be: 1. Independent Process 2. Co-operating Process Reasons for cooperating processes: Information sharing Computation speedup Modularity Convenience Independent Process Co-operating Process 1. A process is independent if it cannot affect or be affected by the other processes executing in the system 1. A process is co-operating if it can affect or be affected by the other processes executing in the system. 2. Any process that does not share data with any other process is IP 2. Any process that share data with any other process is CP

36. Operating Systems Client/Server Communication 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Client/Server communication involves two components, namely a client and a server. They are usually multiple clients in communication with a single server. The clients send requests to the server and the server responds to the client requests. There are three main methods to client/server communication. These are given as follows − Sockets Remote Procedure Calls Pipes

37. Operating Systems Client/Server Communication SOCKET: Sockets facilitate communication between two processes on the same machine or different machines. They are used in a client/server framework and consist of the IP address and port number. Many application protocols use sockets for data connection and data transfer between a client and a server. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

38. Operating Systems Client/Server Communication Remote Procedure Calls These are interprocess communication techniques that are used for client- server based applications. A remote procedure call is also known as a subroutine call or a function call. A client has a request that the RPC translates and sends to the server. This request may be a procedure or a function call to a remote server. When the server receives the request, it sends the required response back to the client. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

39. Operating Systems Client/Server Communication Pipes These are interprocess communication methods that contain two end points. Data is entered from one end of the pipe by a process and consumed from the other end by the other process. The two different types of pipes are ordinary pipes and named pipes. Ordinary pipes only allow one way communication. For two way communication, two pipes are required. Ordinary pipes have a parent child relationship between the processes as the pipes can only be accessed by processes that created or inherited them 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

40. Operating Systems Client/Server Communication Client Server Computing: In client server computing, the clients requests a resource and the server provides that resource. A server may serve multiple clients at the same time while a client is in contact with only one server. Both the client and server usually communicate via a computer network but sometimes they may reside in the same system. An illustration of the client server system is given as follows − 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

41. Process Scheduling Algorithms 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. There are six popular process scheduling algorithms which we are going to discuss in this chapter − First-Come, First-Served (FCFS) Scheduling- In this Process which requests the cpu gets the cpu allocation first Shortest-Job-Next (SJN) Scheduling— Execution time should be selected for execution next Priority Scheduling- it selects the tasks to work as per the priority Shortest Remaining Time- The process will be allocated to the task, which is closest to its completion. Round Robin(RR) Scheduling- it works on principle, where each person gets an equal share of something in turn(change the position) Multiple-Level Queues Scheduling-i t separate the queues. In this method processes are assigned to a queue based on a specific properity

42. First Come First Serve (FCFS) 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition F C F S Jobs are executed on first come, first serve basis. It is a non-preemptive, pre-emptive scheduling algorithm. Easy to understand and implement. Its implementation is based on FIFO queue. Poor in performance as average wait time is high.

43. Wait time of each process is as follows − 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Average Wait Time: (0+4+6+13) / 4 = 5.75 Process Wait Time : Service Time - Arrival Time P0 - = P1 5 - 1 = 4 P2 8 - 2 = 6 P3 16 - 3 = 13

44. Shortest Job Next (SJF/SJN) 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition This is also known as shortest job first , or SJF This is a non-preemptive, pre-emptive scheduling algorithm. Best approach to minimize waiting time. E a s y t o impl e me n t in Ba t ch s y st e ms whe r e r equi r ed C P U time is known in advance. Impossible to implement in interactive systems where required CPU time is not known. The processer should know in advance how much time process will take.

45. S J F 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Given: Table of processes, and their Arrival time, Execution time Shortest Job First Scheduling Algorithm Process Arrival Time Execution Time Service Time P0 5 P1 1 3 5 P2 2 8 14 P3 3 6 8

46. Waiting time of each process is as follows − 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Average Wait Time: (0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25 Process W aiting T ime= S E R V I CE T I ME - A R R I V AL T I ME P0 - = P1 5 - 1 = 4 P2 14 - 2 = 12 P3 8 - 3 = 5

47. Priority Based Scheduling 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition 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.

48. Priority Scheduling Algorithm 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Given: Table of processes, and their Arrival time, Execution time, and priority. Here we are considering 1 is the lowest priority. Priority Scheduling Algorithm Process Arrival Time Execution Time Priority Service Time P0 5 1 P1 1 3 2 11 P2 2 8 1 14 P3 3 6 3 5

49. Priority Scheduling Algorithm 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Waiting time of each process is as follows − Waiting time=service time-arrival time Average Wait Time: (0 + 10 + 12 + 2)/4 = 24 / 4 = 6 Process Waiting Time=service time-arriaval time P0 - = P1 11 - 1 = 10 P2 14 - 2 = 12 P3 5 - 3 = 2

50. Shortest Remaining Time 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Shortest remaining time (SRT) is the preemptive version of the SJN algorithm. The processor is allocated to the job closest to completion but it can be preempted by a newer ready job with shorter time to completion. Impossible to implement in interactive systems where required CPU time is not known. It is often used in batch environments where short jobs need to give preference.

51. Round Robin Scheduling Round Robin is the preemptive process scheduling algorithm. E ach p r oc e s s is p r o vi d ed a fi x t i me t o e x ec u t e, it is c alled a quantum . Onc e a p r oces s is e x e c u t ed f o r a gi v en t i me pe riod, it is preempted and other process executes for a given time period. Context switching is used to save states of preempted process. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

52. Round Robin Scheduling 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Wait time of each process is as follows − Average Wait Time: (9+2+12+11) / 4 = 8.5 Process Wait Time : Service Time - Arrival Time P0 (0 - 0) + (12 - 3) = 9 P1 (3 - 1) = 2 P2 (6 - 2) + (14 - 9) + (20 - 17) = 12 P3 (9 - 3) + (17 - 12) = 11

53. Multiple-Level Queues Scheduling Multiple-level queues are not an independent scheduling algorithm. They make use of other existing algorithms to group and schedule jobs with common characteristics. Multiple queues are maintained for processes with common characteristics. Each queue can have its own scheduling algorithms. Priorities are assigned to each queue. For example, CPU-bound jobs can be scheduled in one queue and all I/O- bound jobs in another queue. The Process Scheduler then alternately selects jobs from each queue and assigns them to the CPU based on the algorithm assigned to the queue. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

54. THREADS A Thread is a flow of execution through the process code, with its own program counter that keeps track of which instruction to execute next, system registers . It is also called as light weight process A thread is a basic unit of CPU utilization; it comprises a thread ID, a program counter, a register set, and a stack. It shares with other threads belonging to the same process its code section, data section, and other operating-system resources, such as open files and signals. THREADS Overview A word processor may have a thread for displaying graphics, another thread for responding to keystrokes from the user, and a third thread for performing spelling and grammar checking in the background. 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

55. Thre a d 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

56. Thre a d 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition In certain situations, a single application may be required to perform several similar tasks. For example, a web server accepts client requests for web pages, images, sound, and so forth. A busy web server may have several (perhaps thousands) of clients concurrently accessing it. If the web server ran as a traditional single-threaded process, it would be able to service only one client at a time. The amount of time that a client might have to wait for its request to be serviced could be enormous.

57. Multithreading Models Single & Multithreaded Processes 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

58. Difference between process and thread 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Process Process is heavy weight It needs interaction with OS It creates own memory of files Multiple processes without using Threads use more resources It is an independent Thread Light weight Does not required with OS 3 . it sha r e s am e se t o f o pen files,diff processes multiple threaded processes are fewer resoruces one thread having read, write or change another thread

59. Benefits Responsiveness Resource Sharing Economy Utilization of MP Architectures User Threads Libraries Thread management done by user-level threads library Three primary thread libraries: POSIX Pthreads Win32 threads Java threads 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

60. Multithreading Models Multithreading Models Many-to-One One-to-One Many-to-Many 1. Many-to-One 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

61. Multithreading models One- t o - One 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

62. Multithreading models Many to Many Model 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

63. Issues of Thread 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Threading Issues: Semantics of fork() and exec() system calls Thread cancellation Signal handling Thread pools Thread specific data Scheduler activations

64. Threading Issues in the Different Environment 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Windows XP Threads Each thread contains A thread id Register set Separate user and kernel stacks Private data storage area The register set, stacks, and private storage area are known as the context of the threads The primary data structures of a thread include: ETHREAD (executive thread block) KTHREAD (kernel thread block) TEB (thread environment block)

65. Threading Issues in the Different Environment 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Linux Threads Linux refers to them as tasks rather than threads Thread creation is done through clone() system call clone() allows a child task to share the address space of the parent task (process) Java Threads Java threads are managed by the JVM Java threads may be created by: Extending Thread class Implementing the Runnable interface

66. Process Synchronization 1.1 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Concu r r e n t access t o sha r ed d at a m a y inconsistency (change in behavior) result in data Mai nt aining d at a c o n si s t en c y r e q ui r es mechanisms to ensure the orderly execution of cooperating processes Suppos e th a t w e w a n t ed t o p r o vide a so l utio n t o the “producer-consumer” problem that fills all the buffers. W e c an d o s o b y h a v i n g an i nt e g er v aria bl e “ c ou n t ” th a t keeps track of the number of full buffers. Initially, count is set to 0. It is incremented by the producer after it produces a new buffer. I t is de c r eme nt ed b y the c on s um er a f t er i t c on s um es a buffer.

67. Producer consumer problem 1.68 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition } Producer while (true) { /* produce an item and put in nextProduced */ while (count == BUFFER_SIZE); // do nothing buffer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; count++; } Consumer while (true) { while (count == 0); // do nothing nextConsumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; count--; /* consume the item in nextConsumed

68. Critical section problem: 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition A section of code which reads or writes shared data. Race Condition The situation where two or more processes try to access and manipulate the same data and output of the process depends on the orderly execution of those processes is called as Race Condition . count++ could be implemented as register1 = count register1 = register1 + 1 count = register1 count-- could be implemented as register2 = count register2 = register2 - 1 count = register2

69. Race Condition 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = count {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = count {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute count = register1 {count = 6 } S5: consumer execute count = register2 {count = 4}

70. Requirements for the Solution to Critical-Section Problem Mutual Exclusion : - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections Progress: - If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. Bounded Waiting: - A bound must exist on the number of times that other processes are allowed to enter their critical sections after a process has made a request to enter its critical section and before that request is granted. To general approaches are used to handle critical sections in operating systems: (1) Preemptive Kernel (2) Non Preemptive Kernel Preemptive Kernel allows a process to be preempted while it is running in kernel mode. Non Preemptive Kernel does not allow a process running in kernel mode to be preempted. (these are free from race conditions) 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

71. Se m aphores A semaphore is a synchronization tool which is an integer value that, apart from initialization, is accessed only through two standard atomic operations; wait and signal. Semaphores can be used to deal with the n-process critical section problem. It can be also used to solve various Synchronization problems. As it is difficult for the application programmer to use these hardware instructions, to overcome this difficulty we use the synchronization tool called as Semaphore (that does not require busy waiting) Semaphore S – integer variable, apart from this initialization we can access this only through two standard atomic operations called as wait() and signal(). Originally the wait() and signal() operations are termed as P() and V() respectively. Which are termed from the Dutch words “proberen” and “verhogen”. 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

72. The definition for wait() is as follows : wait (S) { while S <= ; // no-op S--; } The definition for signal() is as follows : signal (S) { S++; } 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

73. Classical Problems of Synchronization Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

74. Bounded-Buffer Problem 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition Let us assume N buffers, each can hold only one item. Semaphore mutex initialized to the value 1 which is used to provide mutual exclusion. Semaphore full initialized to the value Semaphore empty initialized to the value N. Semaphore full and empty are used to count the number of buffers.

75. Bounded-Buffer Problem 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition The structure of the producer process while (true) { // produce an item wait (empty); wait (mutex); // add the item to the buffer signal (mutex); signal (full); } The structure of the consumer process while (true) { wait (full); wait (mutex); // remove an item from buffer signal (mutex); signal (empty); // consume the removed item }

76. Readers-Writers Problem 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition A data set is shared among a number of concurrent processes Readers – only read the data set, do not perform any updates Writers – can both read and write the data set (perform the updates). If two readers read the shared data simultaneously, there will be no problem. If both a reader(s) and writer share the same data simultaneously then there will be aproblem. In the solution of reader-writer problem, the reader process share the following data structures: Semaphore Mutex, wrt; int readcount; Where Semaphore mutex is initialized to 1. Semaphore wrt is initialized to 1. Integer readcount is initialized to 0.

77. Structure of reader and writer process 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition The structure of a writer process while (true) { wait (wrt) ; // writing is performed signal (wrt) ; } The structure of a reader process while (true) { wait (mutex) ; readcount ++ ; if (readcount == 1) wait (wrt) ; signal (mutex) // reading is performed wait (mutex) ; readcount - - ; if (readcount == 0) signal (wrt) ; signal (mutex) ; }

78. Dining-Philosophers Problem Shared data Bowl of rice (data set) Semaphore chopstick [5] initialized to 1 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition

79. Monitors A high-level abstraction that provides a convenient and effective mechanism forprocess synchronization. A procedure can access only those variables that are declared in a monitor andformal parameters . Only one process may be active within the monitor at a time Syntax of the monitor :- monitor monitor-name 1.69 Silberschatz, Galvin and Gagne ©2011 Operating System Concepts Essentials – 8 th Edition { // shared variabledeclarations procedure P1 (…) { …. } … procedure Pn (…) {……} Initialization code ( ….) { … } … }