Module 1: Operating-System Structures PDF

Module 1: Operating-System Structures Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Chapter 2: Operating-System Structures Operating System Services User Operating System Interface System Calls Types of System Calls System Programs Operating System Design and Implementation Operating System Structure Operating System Concepts – 8th Edition 2 Silberschatz, Galvin and Gagne ©2009 Objectives To describe the services an operating system provides to users, processes, and other systems To discuss the various ways of structuring an operating system To explain how operating systems are installed and customized and how they boot Operating System Concepts – 8th Edition 3 Silberschatz, Galvin and Gagne ©2009 Operating System Services Operating systems provide an environment for execution of programs and services to programs and users One set of operating-system services provides functions that are helpful to the user: User interface - Almost all operating systems have a user interface (UI).  Varies between Command-Line (CLI), Graphics User Interface (GUI), Batch Program execution - The system must be able to load a program into memory and to run that program, end execution, either normally or abnormally (indicating error) I/O operations - A running program may require I/O, which may involve a file or an I/O device File-system manipulation - The file system is of particular interest. Programs need to read and write files and directories, create and delete them, search them, list file Information, permission management. Operating System Concepts – 8th Edition 4 Silberschatz, Galvin and Gagne ©2009     Operating System Services (Cont.) Communications – Processes may exchange information, on the same computer or between computers over a network  Communications may be via shared memory or through message passing (packets moved by the OS) Error detection – OS needs to be constantly aware of possible errors  May occur in the CPU and memory hardware, in I/O devices, in user program  For each type of error, OS should take the appropriate action to ensure correct and consistent computing  Debugging facilities can greatly enhance the user’s and programmer’s abilities to efficiently use the system Operating System Concepts – 8th Edition 5 Silberschatz, Galvin and Gagne ©2009   Operating System Services (Cont.) Another set of OS functions exists for ensuring the efficient operation of the system itself via resource sharing Resource allocation - When multiple users or multiple jobs running concurrently, resources must be allocated to each of them  Many types of resources - Some (such as CPU cycles, main memory, and file storage) may have special allocation code, others (such as I/O devices) may have general request and release code Accounting - To keep track of which users use how much and what kinds of computer resources Protection and security - The owners of information stored in a multiuser or networked computer system may want to control use of that information, concurrent processes should not interfere with each other  Protection involves ensuring that all access to system resources is controlled  Security of the system from outsiders requires user authentication, extends to defending external I/O devices from invalid access attempts  If a system is to be protected and secure, precautions must be instituted throughout it. A chain is only as strong as its weakest link. Operating System Concepts – 8th Edition 6 Silberschatz, Galvin and Gagne ©2009    A View of Operating System Services Operating System Concepts – 8th Edition 7 Silberschatz, Galvin and Gagne ©2009 User Operating System Interface - CLI Command Line Interface (CLI) or command interpreter allows direct command entry  Sometimes implemented in kernel, sometimes by systems program  Sometimes multiple flavors implemented – shells  Primarily fetches a command from user and executes it Operating System Concepts – 8th Edition 8 Silberschatz, Galvin and Gagne ©2009 User Operating System Interface - GUI User-friendly desktop metaphor interface Usually mouse, keyboard, and monitor Icons represent files, programs, actions, etc Various mouse buttons over objects in the interface cause various actions (provide information, options, execute function, open directory (known as a folder) Invented at Xerox PARC Many systems now include both CLI and GUI interfaces Microsoft Windows is GUI with CLI “command” shell Apple Mac OS X as “Aqua” GUI interface with UNIX kernel underneath and shells available Solaris is CLI with optional GUI interfaces (Java Desktop, KDE) Operating System Concepts – 8th Edition 9 Silberschatz, Galvin and Gagne ©2009        System Calls Programming interface to the services provided by the OS Typically written in a high-level language (C or C++) Mostly accessed by programs via a high-level Application Program Interface (API) rather than direct system call use Three most common APIs are Win32 API for Windows, POSIX API for POSIX-based systems (including virtually all versions of UNIX, Linux, and Mac OS X), and Java API for the Java virtual machine (JVM) Why use APIs rather than system calls? (Note that the system-call names used throughout this text are generic) Operating System Concepts – 8th Edition 10 Silberschatz, Galvin and Gagne ©2009 Example of System Calls System call sequence to copy the contents of one file to another file Operating System Concepts – 8th Edition 11 Silberschatz, Galvin and Gagne ©2009 Example of Standard API Consider the ReadFile() function in the Win32 API—a function for reading from a file A description of the parameters passed to ReadFile() HANDLE file—the file to be read LPVOID buffer—a buffer where the data will be read into and written from DWORD bytesToRead—the number of bytes to be read into the buffer LPDWORD bytesRead—the number of bytes read during the last read LPOVERLAPPED ovl—indicates if overlapped I/O is being used Operating System Concepts – 8th Edition 12 Silberschatz, Galvin and Gagne ©2009      System Call Implementation Typically, a number associated with each system call System-call interface maintains a table indexed according to these numbers The system call interface invokes intended system call in OS kernel and returns status of the system call and any return values The caller need know nothing about how the system call is implemented Just needs to obey API and understand what OS will do as a result call Most details of OS interface hidden from programmer by API  Managed by run-time support library (set of functions built into libraries included with compiler) Operating System Concepts – 8th Edition 13 Silberschatz, Galvin and Gagne ©2009    API – System Call – OS Relationship Operating System Concepts – 8th Edition 14 Silberschatz, Galvin and Gagne ©2009 Standard C Library Example C program invoking printf() library call, which calls write() system call Operating System Concepts – 8th Edition 15 Silberschatz, Galvin and Gagne ©2009 System Call Parameter Passing Often, more information is required than simply identity of desired system call Exact type and amount of information vary according to OS and call Three general methods used to pass parameters to the OS Simplest: pass the parameters in registers  In some cases, may be more parameters than registers Parameters stored in a block, or table, in memory, and address of block passed as a parameter in a register  This approach taken by Linux and Solaris Parameters placed, or pushed, onto the stack by the program and popped off the stack by the operating system Block and stack methods do not limit the number or length of parameters being passed Operating System Concepts – 8th Edition 16 Silberschatz, Galvin and Gagne ©2009      Parameter Passing via Table Operating System Concepts – 8th Edition 17 Silberschatz, Galvin and Gagne ©2009 Types of System Calls Process control end, abort load, execute create process, terminate process get process attributes, set process attributes wait for time wait event, signal event allocate and free memory File management create file, delete file open, close file read, write, reposition get and set file attributes Operating System Concepts – 8th Edition 18 Silberschatz, Galvin and Gagne ©2009            Types of System Calls (Cont.) Device management request device, release device read, write, reposition get device attributes, set device attributes logically attach or detach devices Information maintenance get time or date, set time or date get system data, set system data get and set process, file, or device attributes Communications create, delete communication connection send, receive messages transfer status information attach and detach remote devices Operating System Concepts – 8th Edition 19 Silberschatz, Galvin and Gagne ©2009            Examples of Windows and Unix System Calls Operating System Concepts – 8th Edition 20 Silberschatz, Galvin and Gagne ©2009 Example: MS-DOS Single-tasking Shell invoked when system booted Simple method to run program No process created Single memory space Loads program into memory, overwriting all but the kernel Program exit -> shell reloaded Operating System Concepts – 8th Edition 21 Silberschatz, Galvin and Gagne ©2009  MS-DOS execution (a) At system startup (b) running a program Operating System Concepts – 8th Edition 22 Silberschatz, Galvin and Gagne ©2009 Example: FreeBSD Unix variant Multitasking User login -> invoke user’s choice of shell Shell executes fork() system call to create process Executes exec() to load program into process Shell waits for process to terminate or continues with user commands Process exits with code of 0 – no error or > 0 – error code Operating System Concepts – 8th Edition 23 Silberschatz, Galvin and Gagne ©2009   FreeBSD Running Multiple Programs Operating System Concepts – 8th Edition 24 Silberschatz, Galvin and Gagne ©2009 System Programs System programs provide a convenient environment for program development and execution. They can be divided into: File manipulation Status information File modification Programming language support Program loading and execution Communications Application programs Most users’ view of the operation system is defined by system programs, not the actual system calls Operating System Concepts – 8th Edition 25 Silberschatz, Galvin and Gagne ©2009        System Programs Provide a convenient environment for program development and execution Some of them are simply user interfaces to system calls; others are considerably more complex File management - Create, delete, copy, rename, print, dump, list, and generally manipulate files and directories Status information Some ask the system for info - date, time, amount of available memory, disk space, number of users Others provide detailed performance, logging, and debugging information Typically, these programs format and print the output to the terminal or other output devices Some systems implement a registry - used to store and retrieve configuration information Operating System Concepts – 8th Edition 26 Silberschatz, Galvin and Gagne ©2009      System Programs (Cont.) File modification Text editors to create and modify files Special commands to search contents of files or perform transformations of the text Programming-language support - Compilers, assemblers, debuggers and interpreters sometimes provided Program loading and execution- Absolute loaders, relocatable loaders, linkage editors, and overlay-loaders, debugging systems for higher-level and machine language Communications - Provide the mechanism for creating virtual connections among processes, users, and computer systems Allow users to send messages to one another’s screens, browse web pages, send electronic-mail messages, log in remotely, transfer files from one machine to another Operating System Concepts – 8th Edition 27 Silberschatz, Galvin and Gagne ©2009    Operating System Design and Implementation Design and Implementation of OS not “solvable”, but some approaches have proven successful Internal structure of different Operating Systems can vary widely Start by defining goals and specifications Affected by choice of hardware, type of system User goals and System goals User goals – operating system should be convenient to use, easy to learn, reliable, safe, and fast System goals – operating system should be easy to design, implement, and maintain, as well as flexible, reliable, error-free, and efficient Operating System Concepts – 8th Edition 28 Silberschatz, Galvin and Gagne ©2009   Operating System Design and Implementation (Cont.) Important principle to separate Policy: What will be done? Mechanism: How to do it? Mechanisms determine how to do something, policies decide what will be done The separation of policy from mechanism is a very important principle, it allows maximum flexibility if policy decisions are to be changed later Operating System Concepts – 8th Edition 29 Silberschatz, Galvin and Gagne ©2009  Simple Structure MS-DOS – written to provide the most functionality in the least space Not divided into modules Although MS-DOS has some structure, its interfaces and levels of functionality are not well separated Operating System Concepts – 8th Edition 30 Silberschatz, Galvin and Gagne ©2009   MS-DOS Layer Structure Operating System Concepts – 8th Edition 31 Silberschatz, Galvin and Gagne ©2009 Layered Approach The operating system is divided into a number of layers (levels), each built on top of lower layers. The bottom layer (layer 0), is the hardware; the highest (layer N) is the user interface. With modularity, layers are selected such that each uses functions (operations) and services of only lower-level layers Operating System Concepts – 8th Edition 32 Silberschatz, Galvin and Gagne ©2009 Traditional UNIX System Structure Operating System Concepts – 8th Edition 33 Silberschatz, Galvin and Gagne ©2009 UNIX UNIX – limited by hardware functionality, the original UNIX operating system had limited structuring. The UNIX OS consists of two separable parts Systems programs The kernel  Consists of everything below the system-call interface and above the physical hardware  Provides the file system, CPU scheduling, memory management, and other operating-system functions; a large number of functions for one level Operating System Concepts – 8th Edition 34 Silberschatz, Galvin and Gagne ©2009   Layered Operating System Operating System Concepts – 8th Edition 35 Silberschatz, Galvin and Gagne ©2009 Microkernel System Structure Moves as much from the kernel into “user” space Communication takes place between user modules using message passing Benefits: Easier to extend a microkernel Easier to port the operating system to new architectures More reliable (less code is running in kernel mode) More secure Detriments: Performance overhead of user space to kernel space communication Operating System Concepts – 8th Edition 36 Silberschatz, Galvin and Gagne ©2009      Mac OS X Structure Operating System Concepts – 8th Edition 37 Silberschatz, Galvin and Gagne ©2009 Modules Most modern operating systems implement kernel modules Uses object-oriented approach Each core component is separate Each talks to the others over known interfaces Each is loadable as needed within the kernel Overall, similar to layers but with more flexible Operating System Concepts – 8th Edition 38 Silberschatz, Galvin and Gagne ©2009     Solaris Modular Approach Operating System Concepts – 8th Edition 39 Silberschatz, Galvin and Gagne ©2009 Virtual Machines A virtual machine takes the layered approach to its logical conclusion. It treats hardware and the operating system kernel as though they were all hardware. A virtual machine provides an interface identical to the underlying bare hardware. The operating system host creates the illusion that a process has its own processor and (virtual memory). Each guest provided with a (virtual) copy of underlying computer. Operating System Concepts – 8th Edition 40 Silberschatz, Galvin and Gagne ©2009 Virtual Machines (Cont.) (a) Nonvirtual machine (b) virtual machine Operating System Concepts – 8th Edition 41 Silberschatz, Galvin and Gagne ©2009 VMware Architecture Operating System Concepts – 8th Edition 42 Silberschatz, Galvin and Gagne ©2009 The Java Virtual Machine Operating System Concepts – 8th Edition 43 Silberschatz, Galvin and Gagne ©2009 Operating System Generation Operating systems are designed to run on any of a class of machines; the system must be configured for each specific computer site SYSGEN program obtains information concerning the specific configuration of the hardware system Booting – starting a computer by loading the kernel Bootstrap program – code stored in ROM that is able to locate the kernel, load it into memory, and start its execution Operating System Concepts – 8th Edition 44 Silberschatz, Galvin and Gagne ©2009 System Boot Operating system must be made available to hardware so hardware can start it Small piece of code – bootstrap loader, locates the kernel, loads it into memory, and starts it Sometimes two-step process where boot block at fixed location loads bootstrap loader When power initialized on system, execution starts at a fixed memory location  Firmware used to hold initial boot code Operating System Concepts – 8th Edition 45 Silberschatz, Galvin and Gagne ©2009    End of Chapter 2 Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Module 2A: Processes Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Syllabus Introduction to Process – Scheduling – Operations- Interprocess Communication. Synchronization: Critical Section-Hardware- Mutex- Semaphore –Monitors. Threads: Multithreading Models- Thread Library- Issues Operating System Concepts – 8th Edition 2 Silberschatz, Galvin and Gagne ©2009 Outline Process Concept Process Scheduling Operations on Processes Interprocess Communication Examples of IPC Systems Communication in Client-Server Systems Operating System Concepts – 8th Edition 3 Silberschatz, Galvin and Gagne ©2009 Objectives 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 describe communication in client-server systems Operating System Concepts – 8th Edition 4 Silberschatz, Galvin and Gagne ©2009 Process Concept An operating system executes a variety of programs: Batch system – jobs Time-shared systems – user programs or tasks The terms job and process are almost interchangeably Process – a program in execution; process execution must progress in sequential fashion A process includes: program counter stack data section Operating System Concepts – 8th Edition 5 Silberschatz, Galvin and Gagne ©2009      The Process Multiple parts The program code, also called text section Current activity including program counter, processor registers 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, 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 Operating System Concepts – 8th Edition 6 Silberschatz, Galvin and Gagne ©2009        Process in Memory Operating System Concepts – 8th Edition 7 Silberschatz, Galvin and Gagne ©2009 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 Operating System Concepts – 8th Edition 8 Silberschatz, Galvin and Gagne ©2009      Diagram of Process State Operating System Concepts – 8th Edition 9 Silberschatz, Galvin and Gagne ©2009 Process Control Block (PCB) Information associated with each process Process state Program counter CPU registers CPU scheduling information Memory-management information Accounting information I/O status information Operating System Concepts – 8th Edition 10 Silberschatz, Galvin and Gagne ©2009 Process Control Block (PCB) Operating System Concepts – 8th Edition 11 Silberschatz, Galvin and Gagne ©2009 CPU Switch From Process to Process Operating System Concepts – 8th Edition 12 Silberschatz, Galvin and Gagne ©2009 Process Scheduling Maximize CPU use, quickly switch processes onto CPU for time sharing Process scheduler selects among available processes for next execution on CPU Maintains scheduling queues of processes Job queue – set of all processes in the system Ready queue – set of all processes residing in main memory, ready and waiting to execute Device queues – set of processes waiting for an I/O device Processes migrate among the various queues Operating System Concepts – 8th Edition 13 Silberschatz, Galvin and Gagne ©2009     Ready Queue And Various I/O Device Queues Operating System Concepts – 8th Edition 14 Silberschatz, Galvin and Gagne ©2009 Representation of Process Scheduling Operating System Concepts – 8th Edition 15 Silberschatz, Galvin and Gagne ©2009 Schedulers Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU Sometimes the only scheduler in a system Operating System Concepts – 8th Edition 16 Silberschatz, Galvin and Gagne ©2009  Schedulers (Cont.) Short-term scheduler is invoked very frequently (milliseconds) ⇒ (must be fast) Long-term scheduler is invoked very infrequently (seconds, minutes) ⇒ (may be slow) The long-term scheduler controls the degree of multiprogramming Processes can be described as either: I/O-bound process – spends more time doing I/O than computations, many short CPU bursts CPU-bound process – spends more time doing computations; few very long CPU bursts Operating System Concepts – 8th Edition 17 Silberschatz, Galvin and Gagne ©2009   Process Scheduling Diagram Operating System Concepts – 8th Edition 18 Silberschatz, Galvin and Gagne ©2009 Long Term Scheduler -Long-term scheduler controls the programs that are selected within the system for processing. In this, programs are found during a queue and therefore the best job is chosen as per the need it selects the processes from the job pool and these processes are loaded into memory so as to execute. - It provides restraint on the degree of multi-programming. * If the amount of memory is too limited, the degree of multiprogramming will be limited because fewer processes will t in memory. Advantages of Long-term Scheduler: Better system performance: Long-term scheduling allows the operating system to select the best process to be executed, which can improve overall system performance. Better resource utilisation: By selecting the most e cient processes, long-term scheduling can help maximize the use of system resources. Improved response time: Long-term scheduling can help reduce the response time of the system by selecting the best process to be executed. Disadvantages of Long-term Scheduler: Delayed execution: Long-term scheduling can delay the execution of a process, as it must wait until a suitable process is available. Increased overhead: The long-term scheduler can increase the overhead of the system, as it requires additional processing power and resources to select the best process. Operating System Concepts – 8th Edition 19 Silberschatz, Galvin and Gagne ©2009 fi ffi Medium-Term Scheduler A medium-term scheduler is called a process swapping scheduler as it is a part of swapping. Through this scheduler, processes are removed from memory. Medium-term schedulers cut down the degree of multi- programming. In this scheduler, if a process requests I/O, it can be suspended and it cannot make any progress toward the completion of the suspended process. During this condition, to get rid of the method from memory and make space for other processes, the suspended process is moved to the auxiliary storage. This process is named swapping, and therefore the process is claimed to be swapped out or unrolled. Swapping could also be necessary to enhance the process mix. Advantages of Medium-term Scheduler: Improved resource utilization: Medium-term scheduling can improve resource utilization by temporarily removing processes from memory when they are not needed. Better response time: Medium-term scheduling can improve response time by removing inactive or less critical processes from memory. Disadvantages of Medium-term Scheduler: Increased overhead: Medium-term scheduling can increase the overhead of the system, as it requires additional processing power and resources to manage the swapping of processes in and out of memory. Reduced system performance: Medium-term scheduling can temporarily reduce system performance during the swapping of processes in and out of memory Operating System Concepts – 8th Edition 20 Silberschatz, Galvin and Gagne ©2009 Short-Term Scheduling Short-term scheduler’s major objective is to make sure that the CPU is constantly utilized e ectively and e ciently. -The short-term scheduler operates by continuously keeping track of the status of all the system’s processes. The scheduler chooses a process from the ready queue when it is prepared to run and allows the CPU to do it. The process then continues to operate until it either completes its work or runs into an I/O activity that blocks it. The short-term scheduler can employ a variety of scheduling methods, each of which has advantages and disadvantages of its own. Several well-liked algorithms include: First-Come, First-Served (FCFS): This method simply carries out the operations in the order in which the system receives them. Shortest Job First (SJF): This algorithm chooses the process to run next based on its predicted runtime. Priority Scheduling: This algorithm gives each process a priority rating and chooses the process with the highest rating to run next. Round Robin: This algorithm cycles around the ready queue, giving each process a chance to run, allotting each process a xed time slice (referred to as a time quantum). Advantage of STS -Reduce process waiting time -Improve CPU utilisation and system performance with the right scheduling algorithm and suitable time quantum. Operating System Concepts – 8th Edition 21 Silberschatz, Galvin and Gagne ©2009 ffi fi ff Difference b/w Long-Term and Medium-Term Long-Term Scheduler Medium-Term Scheduler Whereas the medium-term scheduler is Long-term scheduler is called a job scheduler. called the process-swapping scheduler. In a long-term scheduler, the process are selected from the While in this, process can be revived in the job pool and these processes’ time-sharing are loaded into memory as well as process execution can memory in order to execute. also be carried out. Long-term scheduler is can be or can’t be a part of a time While the medium-term scheduler is sharing system. if it is then it is nominal in the time-sharing always in a time-sharing medium-term system. system. While the speed of medium -term The speed of long -term scheduler is less than medium-term scheduler is comparatively higher than scheduler. longer-term scheduler. While a medium-term scheduler cut down Long-term scheduler provides the restraint on the the degree of DOM(Degree of Multi- DOM(Degree of Multi-programming). programming). Operating System Concepts – 8th Edition 22 Silberschatz, Galvin and Gagne ©2009 Addition of Medium Term Scheduling Operating System Concepts – 8th Edition 23 Silberschatz, Galvin and Gagne ©2009 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 -> longer the context switch Time dependent on hardware support Some hardware provides multiple sets of registers per CPU -> multiple contexts loaded at once Operating System Concepts – 8th Edition 24 Silberschatz, Galvin and Gagne ©2009   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 Parent and children share all resources Children share subset of parent’s resources Parent and child share no resources Execution Parent and children execute concurrently Parent waits until children terminate Operating System Concepts – 8th Edition 25 Silberschatz, Galvin and Gagne ©2009      Process Creation (Cont.) Address space Child duplicate of parent Child has a program loaded into it UNIX examples fork system call creates new process exec system call used after a fork to replace the process’ memory space with a new program Operating System Concepts – 8th Edition 26 Silberschatz, Galvin and Gagne ©2009     Process Creation Operating System Concepts – 8th Edition 27 Silberschatz, Galvin and Gagne ©2009 C Program Forking Separate Process #include #include #include int main() { pid_t pid; pid = fork(); if (pid < 0) { fprintf(stderr, "Fork Failed"); return 1; } else if (pid == 0) { execlp("/bin/ls", "ls", NULL); } else { wait (NULL); printf ("Child Complete"); } return 0; } Operating System Concepts – 8th Edition 28 Silberschatz, Galvin and Gagne ©2009 A Tree of Processes on Solaris Operating System Concepts – 8th Edition 29 Silberschatz, Galvin and Gagne ©2009 Process Termination Process executes last statement and asks the operating system to delete it (exit) Output data from child to parent (via wait) Process’ resources are deallocated by operating system Parent may terminate execution of children processes (abort) Child has exceeded allocated resources Task assigned to child is no longer required If parent is exiting  Some operating systems do not allow child to continue if its parent terminates – All children terminated - cascading termination Operating System Concepts – 8th Edition 30 Silberschatz, Galvin and Gagne ©2009      Interprocess Communication Processes within a system may be independent or cooperating Cooperating process can affect or be affected by other processes, including sharing data Reasons for cooperating processes: Information sharing Computation speedup Modularity Convenience Cooperating processes need interprocess communication (IPC) Two models of IPC Shared memory Message passing Operating System Concepts – 8th Edition 31 Silberschatz, Galvin and Gagne ©2009       Communications Models Operating System Concepts – 8th Edition 32 Silberschatz, Galvin and Gagne ©2009 Cooperating Processes Independent process cannot affect or be affected by the execution of another process Cooperating process can affect or be affected by the execution of another process Advantages of process cooperation Information sharing Computation speed-up Modularity Convenience Operating System Concepts – 8th Edition 33 Silberschatz, Galvin and Gagne ©2009     Producer-Consumer Problem Paradigm for cooperating processes, producer process produces information that is consumed by a consumer process unbounded-buffer places no practical limit on the size of the buffer bounded-buffer assumes that there is a fixed buffer size Operating System Concepts – 8th Edition 34 Silberschatz, Galvin and Gagne ©2009   Bounded-Buffer – Shared-Memory Solution Shared data #define BUFFER_SIZE 10 typedef struct {... } item; item buffer[BUFFER_SIZE]; int in = 0; int out = 0; Solution is correct, but can only use BUFFER_SIZE-1 elements Operating System Concepts – 8th Edition 35 Silberschatz, Galvin and Gagne ©2009 Bounded-Buffer – Producer while (true) { while (((in = (in + 1) % BUFFER SIZE count) == out) ; buffer[in] = item; in = (in + 1) % BUFFER SIZE; } Operating System Concepts – 8th Edition 36 Silberschatz, Galvin and Gagne ©2009 Bounded Buffer – Consumer while (true) { while (in == out) ; // do nothing -- nothing to consume // remove an item from the buffer item = buffer[out]; out = (out + 1) % BUFFER SIZE; return item; } Operating System Concepts – 8th Edition 37 Silberschatz, Galvin and Gagne ©2009 Interprocess Communication – Message Passing Mechanism for processes to communicate and to synchronize their actions Message system – processes communicate with each other without resorting to shared variables IPC facility provides two operations: send(message) – message size fixed or variable receive(message) If P and Q wish to communicate, they need to: establish a communication link between them exchange messages via send/receive Implementation of communication link physical (e.g., shared memory, hardware bus) logical (e.g., logical properties) Operating System Concepts – 8th Edition 38 Silberschatz, Galvin and Gagne ©2009       Implementation Questions How are links established? Can a link be associated with more than two processes? How many links can there be between every pair of communicating processes? What is the capacity of a link? Is the size of a message that the link can accommodate fixed or variable? Is a link unidirectional or bi-directional? Operating System Concepts – 8th Edition 39 Silberschatz, Galvin and Gagne ©2009 Direct Communication Processes must name each other explicitly: send (P, message) – send a message to process P receive(Q, message) – receive a message from process Q Properties of communication link Links are established automatically A link is associated with exactly one pair of communicating processes Between each pair there exists exactly one link The link may be unidirectional, but is usually bi-directional Operating System Concepts – 8th Edition 40 Silberschatz, Galvin and Gagne ©2009       Indirect Communication Messages are directed and received from mailboxes (also referred to as ports) Each mailbox has a unique id Processes can communicate only if they share a mailbox Properties of communication link Link established only if processes share a common mailbox A link may be associated with many processes Each pair of processes may share several communication links Link may be unidirectional or bi-directional Operating System Concepts – 8th Edition 41 Silberschatz, Galvin and Gagne ©2009       Indirect Communication Operations create a new mailbox send and receive messages through mailbox destroy a mailbox Primitives are defined as: send(A, message) – send a message to mailbox A receive(A, message) – receive a message from mailbox A Operating System Concepts – 8th Edition 42 Silberschatz, Galvin and Gagne ©2009    Indirect Communication Mailbox sharing P1, P2, and P3 share mailbox A P1, sends; P2 and P3 receive Who gets the message? Solutions Allow a link to be associated with at most two processes Allow only one process at a time to execute a receive operation Allow the system to select arbitrarily the receiver. Sender is notified who the receiver was. Operating System Concepts – 8th Edition 43 Silberschatz, Galvin and Gagne ©2009       Thank you Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Module 2B: Process Synchronization Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Outline Introduction to Process – Scheduling – Operations-Interprocess Communication. Synchronization: Critical Section-Hardware- Mutex- Semaphore –Monitors. Threads: Multithreading Models- Thread Library- Issues Background The Critical-Section Problem Peterson’s Solution Synchronization Hardware Semaphores Classic Problems of Synchronization Monitors Operating System Concepts – 8th Edition 2 Silberschatz, Galvin and Gagne ©2009 Objectives To introduce the critical-section problem, whose solutions can be used to ensure the consistency of shared data To present both software and hardware solutions of the critical-section problem To introduce the concept of an atomic transaction and describe mechanisms to ensure atomicity Operating System Concepts – 8th Edition 3 Silberschatz, Galvin and Gagne ©2009 Background Concurrent access to shared data may result in data inconsistency Maintaining data consistency requires mechanisms to ensure the orderly execution of cooperating processes Suppose that we wanted to provide a solution to the consumer-producer problem that ﬁlls all the buﬀers. We can do so by having an integer count that keeps track of the number of full buﬀers. Initially, count is set to 0. It is incremented by the producer after it produces a new buﬀer and is decremented by the consumer after it consumes a buﬀer. Operating System Concepts – 8th Edition 4 Silberschatz, Galvin and Gagne ©2009 Producer while (true) { while (counter == BUFFER_SIZE) ; // do nothing buﬀer [in] = nextProduced; in = (in + 1) % BUFFER_SIZE; counter++; } Operating System Concepts – 8th Edition 5 Silberschatz, Galvin and Gagne ©2009 Consumer while (true) { while (counter == 0) ; // do nothing nextConsumed = buﬀer[out]; out = (out + 1) % BUFFER_SIZE; counter--; } Operating System Concepts – 8th Edition 6 Silberschatz, Galvin and Gagne ©2009 Race Condition Race Condition is a situation that occurs when two or more threads or processes access a shared resource, such as a file or a variable, at the same time. Ex counter++ could be implemented as register1 = counter register1 = register1 + 1 counter = register1 counter-- could be implemented as register2 = counter register2 = register2 - 1 count = register2 Consider this execution interleaving with “count = 5” initially: S0: producer execute register1 = counter {register1 = 5} S1: producer execute register1 = register1 + 1 {register1 = 6} S2: consumer execute register2 = counter {register2 = 5} S3: consumer execute register2 = register2 - 1 {register2 = 4} S4: producer execute counter = register1 {count = 6 } S5: consumer execute counter = register2 {count = 4} Operating System Concepts – 8th Edition 7 Silberschatz, Galvin and Gagne ©2009 Cont… The following race condition occurs: App A reads the current balance, which is ₹1000 App A adds ₹200 to ₹1000 and gets ₹1200 as the ﬁnal balance Meanwhile, app B fetches the current balance, which is still ₹1000, as app A has not executed step 3 App B adds ₹500 to ₹1000 and gets ₹1500 as the ﬁnal balance App B updates the account balance to ₹1500 App A updates the account balance to ₹1200 Thus the ﬁnal balance is ₹1200 instead of ₹1700 Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Critical Section Problem Consider system of n processes {p0, p1, … pn-1} Each process has critical section segment of code Process may be changing common variables, updating table, writing ﬁle, etc When one process in critical section, no other may be in its critical section Critical section problem is to design protocol to solve this Each process must ask permission to enter critical section in entry section, may follow critical section with exit section, then remainder section Especially challenging with preemptive kernels Operating System Concepts – 8th Edition 9 Silberschatz, Galvin and Gagne ©2009 Critical Section General structure of process pi is Operating System Concepts – 8th Edition 1 Silberschatz, Galvin and Gagne ©2009 Solution to Critical-Section Problem 1. Mutual Exclusion - If process Pi is executing in its critical section, then no other processes can be executing in their critical sections 2. 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 indeﬁnitely 3. 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. This should not lead to the problem of Starvation. Assume that each process executes at a nonzero speed No assumption concerning relative speed of the n processes 4. No assumption related to Hardware and Speed- Execute solution must be universal ie easily ﬂexible and portable. Operating System Concepts – 8th Edition 11 Silberschatz, Galvin and Gagne ©2009 Solution 1 to CS problem-Lock variable Initially lock=0 Entry Section → 1. While (lock! = 0); # 2. Lock = 1; 3. Critical Section Exit Section → 4. Lock =0; Every Synchronization mechanism is judged on the basis of four conditions. 1. Mutual Exclusion- Not Satisﬁed as instruction 1 and 2 can have preemption in between 2. Progress 3. Bounded Waiting 4. Portability Operating System Concepts – 8th Edition 12 Silberschatz, Galvin and Gagne ©2009 Solution 2 to CS problem-Test and set Test and Set Lock (TSL) is a synchronization mechanism. It uses a test and set instruction to provide the synchronization among the processes executing concurrently. Initially lock=False Entry Section → 1. While (test_and_set(&lock));#Instruction to avoid preemption 2. Critical Section Exit Section → 3. Lock = False; boolean test_and_set(boolean *target) { boolean r = *target; *target=True; return r; } Every Synchronization mechanism is judged on the basis of four conditions. 1. Mutual Exclusion- Satisﬁed 2. Progress- Satisﬁed 3. Bounded Waiting 4. Portability Operating System Concepts – 8th Edition 13 Silberschatz, Galvin and Gagne ©2009 Cont… It is an instruction that returns the old value of a memory location and sets the memory location value to 1 as a single atomic operation. If one process is currently executing a test-and-set, no other process is allowed to begin another test-and-set until the first process test-and-set is finished. Characteristics of this synchronization mechanism are- It ensures mutual exclusion. It is deadlock free, progress is achieved It does not guarantee bounded waiting and may cause starvation. It is not architectural neutral since it requires the operating system to support test-and-set instruction. Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Peterson’s Algorithm 1- Using Turn Variable Turn Variable/Strict Alteration/Two-process solution ○ Turn variable is a synchronization mechanism that provides synchronization among two processes. ○ It uses a turn variable to provide the synchronization. Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Cont.. Initially, turn value is set to 0. ○ Turn value = 0 means it is the turn of process P0 to enter the critical section. ○ Turn value = 1 means it is the turn of process P1 to enter the critical section. The characteristics of this synchronization mechanism are- ○ It ensures mutual exclusion. ○ It does not guarantee progress since it follows strict alternation approach. ○ It ensures bounded waiting since processes are executed turn wise one by one and each process is guaranteed to get a chance. ○ It ensures processes does not starve for the CPU. ○ It is architectural neutral since it does not require any support from the operating system * In strict alternation approach, ○ Processes have to compulsorily enter the critical section alternately whether they want it or not. ○ This is because if one process does not enter the critical section, then other process will never get a chance to execute again. Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Peterson’s Algorithm 2- Using Flag array var flag :array[0…..1] of boolean; Elements of array are initialized to False flag[i]=True indicates Process i is ready to enter critical section do { flag[i]= True; while (Flag[j]) do no op; // Critical section flag[i]= False; Remainder section; } while(True); Operating System Concepts – 8th Edition 17 Silberschatz, Galvin and Gagne ©2009 Peterson’s Solution 2- Using Flag array Every Synchronization mechanism is judged on the basis of four conditions. 1. Mutual Exclusion- Satisfied 2. Progress- Not Satisfied P0 sets Flag=True P1 sets Flag=True at same time Then both will loop in their respective while loop together 3. Bounded Waiting 4. Portability Algo is dependent on exact timing of two processes Operating System Concepts – 8th Edition 18 Silberschatz, Galvin and Gagne ©2009 Peterson’s or Deker’s Solution Two process solution- Combined Algorithm 1 and 2 Assume that the LOAD and STORE instructions are atomic; that is, cannot be interrupted The two processes share two variables: int turn; Boolean ﬂag Initially ﬂag=ﬂag= False The variable turn indicates whose turn it is to enter the critical section The ﬂag array is used to indicate if a process is ready to enter the critical section. ﬂag[i] = true implies that process Pi is ready! Operating System Concepts – 8th Edition 19 Silberschatz, Galvin and Gagne ©2009 Algorithm for Process Pi do { ﬂag[i] = TRUE; turn = j; while (ﬂag[j] && turn == j); critical section ﬂag[i] = FALSE; remainder section } while (TRUE); Provable that 1. Mutual exclusion is preserved 2. Progress requirement is satisﬁed 3. Bounded-waiting requirement is met Operating System Concepts – 8th Edition 20 Silberschatz, Galvin and Gagne ©2009 Multi-process Solution-Bakery Algorithm Algorithm to solve Critical Section for Multi-processes or N processes The Bakery algorithm is one of the simplest known solutions to the mutual exclusion problem for the general case of N process. The algorithm preserves the ﬁrst come ﬁrst serve property. How it works? In the Bakery Algorithm, each process is assigned a number (a ticket) in a lexicographical order. Before entering the critical section, a process receives a ticket number, and the process with the smallest ticket number enters the critical section. If two processes receive the same ticket number, the process with the lower process ID is given priority. ○ Before entering its critical section, the process receives a number. Holder of the smallest number enters the critical section. ○ If processes Pi and Pj receive the same number, then if i < j Pi is served ﬁrst; else Pj is served ﬁrst. Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Cont… Condition for lexicographical order (ticket #, process id #) -Firstly the ticket number is compared. If same then the process ID is compared next – (a, b) < (c, d) if a < c or if a = c and b < d – max(a ,..., a [n-1]) is a number, k, such that k >= a[i] for i = 0,..., n - 1 Shared data associated with a process– choosing is an array [0..n – 1] of boolean values; number is an array [0..n – 1] of integer values. Both are initialized to False & Zero respectively. Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Psuedocode do { choosing[i] := True; number[i] := max(number, number,..., number[n - 1])+1; choosing[i] := False; for j := 0 to n - 1 begin while choosing[j] do no-op; while number[j] != 0 and (number[j], j) < (number[i], i) do no-op; end; // Critical section number[i] := 0; remainder section } while(True); Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Cont.. Mutual Exclusion- Satisﬁed If P1 is in CS and P2 trying to enter, on the second while if condition become True, it loops until P1 leaves CS Progress is also there as Process enter in FCFS Bounded waiting is there as process before leaving sets number[i]=0 and choosing [i]=False No hardware dependency Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Semaphore Synchronization tool used to avoid race condition in concurrent processes It that does not require busy waiting Deals with n processes Critical Section problem where they share a common variable semaphore(mutex) Semaphore S – integer variable - used to achieve Mutual Exclusion in order to achieve synchronization among n cooperating processes Operating System Concepts – 8th Edition 25 Silberschatz, Galvin and Gagne ©2009 Semaphore Two standard operations modify S: wait() and signal() ○ Originally called P() and V() ○ Also known as Down() and Up() Less complicated Semaphore S – integer variable initialized to 1 Can only be accessed via two indivisible (atomic) operations wait (S) { while S value--; if (S->value < 0) { add this process to S->list; // Add process to suspended/block list block(); } } Implementation of signal: signal(semaphore *S) { S->value++; if (S->value list; wakeup(P); } } Operating System Concepts – 8th Edition 30 Silberschatz, Galvin and Gagne ©2009 Deadlock and Starvation Deadlock – two or more processes are waiting indeﬁnitely for an event that can be caused by only one of the waiting processes Let S and Q be two semaphores initialized to 1 P0 P1 wait (S); wait (Q); wait (Q); wait (S);...... signal (S); signal (Q); signal (Q); signal (S); Starvation – indeﬁnite blocking A process may never be removed from the semaphore queue in which it is suspended Priority Inversion – Scheduling problem when lower-priority process holds a lock needed by higher-priority process Solved via priority-inheritance protocol Operating System Concepts – 8th Edition 31 Silberschatz, Galvin and Gagne ©2009 Classical Problems of Synchronization Classical problems used to test newly-proposed synchronization schemes Bounded-Buﬀer Problem Readers and Writers Problem Dining-Philosophers Problem Operating System Concepts – 8th Edition 32 Silberschatz, Galvin and Gagne ©2009 Bounded-Buffer Problem N buﬀers, each can hold one item Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0 Semaphore empty initialized to the value N wait(S){ while(S 0) signal(next) else signal(mutex); Mutual exclusion within a monitor is ensured Operating System Concepts – 8th Edition 52 Silberschatz, Galvin and Gagne ©2009 Monitor Implementation – Condition Variables For each condition variable x, we have: semaphore x_sem; // (initially = 0) int x_count = 0; The operation x.wait can be implemented as: x-count++; if (next_count > 0) signal(next); else signal(mutex); wait(x_sem); x-count--; Operating System Concepts – 8th Edition 53 Silberschatz, Galvin and Gagne ©2009 Monitor Implementation (Cont.) The operation x.signal can be implemented as: if (x-count > 0) { next_count++; signal(x_sem); wait(next); next_count--; } Operating System Concepts – 8th Edition 54 Silberschatz, Galvin and Gagne ©2009 Resuming Processes within a Monitor If several processes queued on condition x, and x.signal() executed, which should be resumed? FCFS frequently not adequate conditional-wait construct of the form x.wait(c) Where c is priority number Process with lowest number (highest priority) is scheduled next Operating System Concepts – 8th Edition 55 Silberschatz, Galvin and Gagne ©2009 A Monitor to Allocate Single Resource monitor ResourceAllocator { boolean busy; condition x; void acquire(int time) { if (busy) x.wait(time); busy = TRUE; } void release() { busy = FALSE; x.signal(); } initialization code() { busy = FALSE; } } Operating System Concepts – 8th Edition 56 Silberschatz, Galvin and Gagne ©2009 Synchronization Examples Solaris Windows XP Linux Pthreads Operating System Concepts – 8th Edition 57 Silberschatz, Galvin and Gagne ©2009 Solaris Synchronization Implements a variety of locks to support multitasking, multithreading (including real-time threads), and multiprocessing Uses adaptive mutexes for eﬃciency when protecting data from short code segments Starts as a standard semaphore spin-lock If lock held, and by a thread running on another CPU, spins If lock held by non-run-state thread, block and sleep waiting for signal of lock being released Uses condition variables Uses readers-writers locks when longer sections of code need access to data Uses turnstiles to order the list of threads waiting to acquire either an adaptive mutex or reader-writer lock Turnstiles are per-lock-holding-thread, not per-object Priority-inheritance per-turnstile gives the running thread the highest of the priorities of the threads in its turnstile Operating System Concepts – 8th Edition 58 Silberschatz, Galvin and Gagne ©2009 Windows XP Synchronization Uses interrupt masks to protect access to global resources on uniprocessor systems Uses spinlocks on multiprocessor systems Spinlocking-thread will never be preempted Also provides dispatcher objects user-land which may act mutexes, semaphores, events, and timers Events An event acts much like a condition variable Timers notify one or more thread when time expired Dispatcher objects either signaled-state (object available) or non-signaled state (thread will block) Operating System Concepts – 8th Edition 59 Silberschatz, Galvin and Gagne ©2009 Linux Synchronization Linux: Prior to kernel Version 2.6, disables interrupts to implement short critical sections Version 2.6 and later, fully preemptive Linux provides: semaphores spinlocks reader-writer versions of both On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption Operating System Concepts – 8th Edition 60 Silberschatz, Galvin and Gagne ©2009 Pthreads Synchronization Pthreads API is OS-independent It provides: mutex locks condition variables Non-portable extensions include: read-write locks spinlocks Operating System Concepts – 8th Edition 61 Silberschatz, Galvin and Gagne ©2009 End of Module 2B Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Chapter 2C: Threads Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009 Outline Overview Multithreading Models Operating System Examples Windows XP Threads Linux Threads Operating System Concepts – 8th Edition 4.2 Silberschatz, Galvin and Gagne ©2009 Objectives To introduce the notion of a thread — a fundamental unit of CPU utilization that forms the basis of multithreaded computer systems To examine issues related to multithreaded programming Operating System Concepts – 8th Edition 4.3 Silberschatz, Galvin and Gagne ©2009 What are Threads? A thread refers to a single sequential flow of activities being executed in a process; it is also known as the thread of execution or the thread of control Multiple tasks with the application can be implemented by separate threads Update display Fetch data Spell checking Answer a network request Process creation is heavy-weight while thread creation is light-weight Each thread belongs to exactly one process. In an operating system that supports multithreading, the process can consist of many threads. But threads can be effective only if the CPU is more than 1 otherwise two threads have to context switch for that single CPU. Can simplify code, increase efficiency Kernels are generally multithreaded Operating System Concepts – 8th Edition 4.4 Silberschatz, Galvin and Gagne ©2009 Why threads are needed? Threads run in parallel improving the application performance. Each such thread has its own CPU state and stack, but they share the address space of the process and the environment. Threads can share common data so they do not need to use inter-process communication. Like the processes, threads also have states like ready, executing, blocked, etc. Priority can be assigned to the threads just like the process, and the highest priority thread is scheduled first. Each thread has its own Thread Control Block (TCB). Like the process, a context switch occurs for the thread, and register contents are saved in (TCB). As threads share the same address space and resources, synchronization is also required for the various activities of the thread. Operating System Concepts – 8th Edition 4.5 Silberschatz, Galvin and Gagne ©2009 Process Thread A process is an instance of a program that is being executed or Thread is a segment of a process or a lightweight process that is processed. managed by the scheduler independently. Processes are independent of each other and hence don't share a Threads are interdependent and share memory. memory or other resources. Each process is treated as a new process by the operating system. The operating system takes all the user-level threads as a single process. If one process gets blocked by the operating system, then the other If any user-level thread gets blocked, all of its peer threads also process can continue the execution. get blocked because OS takes all of them as a single process. Context switching between two processes takes much time as they Context switching between the threads is fast because they are are heavy compared to thread. very lightweight. The data segment and code segment of each process are Threads share data segment and code segment with their peer independent of the other. threads; hence are the same for other threads also. The operating system takes more time to terminate a process. Threads can be terminated in very little time. New process creation is more time taking as each new process A thread needs less time for creation. takes all the resources. Operating System Concepts – 8th Edition 4.6 Silberschatz, Galvin and Gagne ©2009 Single and Multithreaded Processes Operating System Concepts – 8th Edition 4.7 Silberschatz, Galvin and Gagne ©2009 Benefits Minimizes context switching time, better response time Resource Sharing Eﬃcient communication Economy Scalability Operating System Concepts – 8th Edition 4.8 Silberschatz, Galvin and Gagne ©2009 Multicore Programming Multicore systems putting pressure on programmers, challenges include: Dividing activities Balance Data splitting Data dependency Testing and debugging Operating System Concepts – 8th Edition 4.9 Silberschatz, Galvin and Gagne ©2009 Multithreaded Server Architecture Operating System Concepts – 8th Edition 4.10 Silberschatz, Galvin and Gagne ©2009 Concurrent Execution on a Single-core System Operating System Concepts – 8th Edition 4.11 Silberschatz, Galvin and Gagne ©2009 Parallel Execution on a Multicore System Operating System Concepts – 8th Edition 4.12 Silberschatz, Galvin and Gagne ©2009 User Threads As the name suggests, the user-level threads are only managed by users, and the kernel does not have its information. These are faster, easy to create and manage. The kernel takes all these threads as a single process and handles them as one process only. The user-level threads are implemented by user-level libraries, not by the system calls. Three primary thread libraries: POSIX Pthreads Win32 threads Java threads Operating System Concepts – 8th Edition 4.13 Silberschatz, Galvin and Gagne ©2009 Kernel Threads Supported by the Kernel The kernel-level threads are handled by the Operating system and managed by its kernel. These threads are slower than user-level threads because context information is managed by the kernel. To create and implement a kernel-level thread, we need to make a system call. Examples Windows XP/2000 Solaris Linux Tru64 UNIX Mac OS X Operating System Concepts – 8th Edition 4.14 Silberschatz, Galvin and Gagne ©2009 Multithreading Models Many-to-One One-to-One Many-to-Many Operating System Concepts – 8th Edition 4.15 Silberschatz, Galvin and Gagne ©2009 Many-to-One Many user-level threads mapped to single kernel thread Examples: Solaris Green Threads GNU Portable Threads Operating System Concepts – 8th Edition 4.16 Silberschatz, Galvin and Gagne ©2009 Many-to-One Model Operating System Concepts – 8th Edition 4.17 Silberschatz, Galvin and Gagne ©2009 One-to-One Each user-level thread maps to kernel thread Examples Windows NT/XP/2000 Linux Solaris 9 and later Operating System Concepts – 8th Edition 4.18 Silberschatz, Galvin and Gagne ©2009 One-to-one Model Operating System Concepts – 8th Edition 4.19 Silberschatz, Galvin and Gagne ©2009 Many-to-Many Model Allows many user level threads to be mapped to many kernel threads Allows the operating system to create a suﬃcient number of kernel threads Solaris prior to version 9 Windows NT/2000 with the ThreadFiber package Operating System Concepts – 8th Edition 4.20 Silberschatz, Galvin and Gagne ©2009 Many-to-Many Model Operating System Concepts – 8th Edition 4.21 Silberschatz, Galvin and Gagne ©2009 Operating System Examples Windows XP Threads Linux Thread Operating System Concepts – 8th Edition 4.22 Silberschatz, Galvin and Gagne ©2009 Windows XP Threads Data Structures Operating System Concepts – 8th Edition 4.23 Silberschatz, Galvin and Gagne ©2009 Windows XP Threads Implements the one-to-one mapping, kernel-level 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) Operating System Concepts – 8th Edition 4.24 Silberschatz, Galvin and Gagne ©2009 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) struct task_struct points to process data structures (shared or unique) Operating System Concepts – 8th Edition 4.25 Silberschatz, Galvin and Gagne ©2009 Linux Threads fork() and clone() system calls Doesn’t distinguish between process and thread Uses term task rather than thread clone() takes options to determine sharing on process create struct task_struct points to process data structures (shared or unique) Operating System Concepts – 8th Edition 4.26 Silberschatz, Galvin and Gagne ©2009 End of Chapter 2C Operating System Concepts – 8th Edition Silberschatz, Galvin and Gagne ©2009

Module 1: Operating-System Structures PDF

Document Details

Tags

Related

Summary

Full Transcript

Upgrade to continue