UNIT 2 21.pptx.pdf

21CSC202J Operating Systems UNIT 2 – Process Management  Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication Examples of IPC Systems Communication in Client-Server Systems *...

21CSC202J Operating Systems UNIT 2 – Process Management  Processes Process Concept Process Scheduling Operations on Processes Interprocess Communication Examples of IPC Systems Communication in Client-Server Systems * 21CSC202J Operating Systems UNIT 2 2  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 explore interprocess communication using shared memory and message passing To describe communication in client-server systems * 21CSC202J Operating Systems UNIT 2 3  Process Concept An operating system executes a variety of programs: – Batch system – jobs – Time-shared systems – user programs or tasks Textbook uses the terms job and process almost interchangeably Process – a program in execution; process execution must progress in sequential fashion 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 * 21CSC202J Operating Systems UNIT 2 4  Process Concept (Cont.) 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 * 21CSC202J Operating Systems UNIT 2 5  Process in Memory * 21CSC202J Operating Systems UNIT 2 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 * 21CSC202J Operating Systems UNIT 2 7  Diagram of Process State * 21CSC202J Operating Systems UNIT 2 8  Process Control Block (PCB) Information associated with each process (also called task control block) Process state – running, waiting, etc Program counter – location of instruction to next execute CPU registers – contents of all process-centric registers CPU scheduling information- priorities, scheduling queue pointers Memory-management information – memory allocated to the process Accounting information – CPU used, clock time elapsed since start, time limits I/O status information – I/O devices allocated to process, list of open files * 21CSC202J Operating Systems UNIT 2 9  CPU Switch From Process to Process * 21CSC202J Operating Systems UNIT 2 10  Threads So far, process has a single thread of execution Consider having multiple program counters per process – Multiple locations can execute at once Multiple threads of control -> threads Must then have storage for thread details, multiple program counters in PCB See next chapter * 21CSC202J Operating Systems UNIT 2 11  Process Representation in Linux Represented by the C structure task_struct pid t_pid; long state; unsigned int time_slice struct task_struct *parent; struct list_head children; struct files_struct *files; struct mm_struct *mm; * 21CSC202J Operating Systems UNIT 2 12  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 * 21CSC202J Operating Systems UNIT 2 13  Ready Queue And Various I/O Device Queues * 21CSC202J Operating Systems UNIT 2 14  Representation of Process Scheduling Queueing diagram represents queues, resources, flows * 21CSC202J Operating Systems UNIT 2 15  Schedulers Short-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPU – Sometimes the only scheduler in a system – Short-term scheduler is invoked frequently (milliseconds) ⇒ (must be fast) Long-term scheduler (or job scheduler) – selects which processes should be brought into the ready queue – Long-term scheduler is invoked 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 Long-term scheduler strives for good process mix * 21CSC202J Operating Systems UNIT 2 16 Addition of Medium Term Scheduling Medium-term scheduler can be added if degree of multiple programming needs to decrease Remove process from memory, store on disk, bring back in from disk to continue execution: swapping * 21CSC202J Operating Systems UNIT 2 17  Multitasking in Mobile Systems Some mobile systems (e.g., early version of iOS) allow only one process to run, others suspended Due to screen real estate, user interface limits iOS provides for a – Single foreground process- controlled via user interface – Multiple background processes– in memory, running, but not on the display, and with limits – Limits include single, short task, receiving notification of events, specific long-running tasks like audio playback Android runs foreground and background, with fewer limits – Background process uses a service to perform tasks – Service can keep running even if background process is suspended – Service has no user interface, small memory use * 21CSC202J Operating Systems UNIT 2 18  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 * 21CSC202J Operating Systems UNIT 2 19  Operations on Processes System must provide mechanisms for: – process creation, – process termination, – and so on as detailed next * 21CSC202J Operating Systems UNIT 2 20  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 – Parent and child share no resources Execution options – Parent and children execute concurrently – Parent waits until children terminate * 21CSC202J Operating Systems UNIT 2 21  A Tree of Processes in Linux * 21CSC202J Operating Systems UNIT 2 22  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 * 21CSC202J Operating Systems UNIT 2 23  C Program Forking Separate Process * 21CSC202J Operating Systems UNIT 2 24  Creating a Separate Process via Windows API * 21CSC202J Operating Systems UNIT 2 25  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 Parent may terminate the execution of children processes using the abort() system call. Some reasons for doing so: – Child has exceeded allocated resources – Task assigned to child is no longer required – The parent is exiting and the operating systems does not allow a child to continue if its parent terminates * 21CSC202J Operating Systems UNIT 2 26  Process Termination 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 * 21CSC202J Operating Systems UNIT 2 27  Multiprocess Architecture – Chrome Browser Many web browsers ran as single process (some still do) – If one web site causes trouble, entire browser can hang or crash Google Chrome Browser is multiprocess with 3 different types of processes: – Browser process manages user interface, disk and network I/O – Renderer process renders web pages, deals with HTML, Javascript. A new renderer created for each website opened Runs in sandbox restricting disk and network I/O, minimizing effect of security exploits – Plug-in process for each type of plug-in * 21CSC202J Operating Systems UNIT 2 28  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 * 21CSC202J Operating Systems UNIT 2 29  Communications Models (a) Message passing. (b) shared memory. * 21CSC202J Operating Systems UNIT 2 30  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 * 21CSC202J Operating Systems UNIT 2 31  Interprocess Communication – Shared Memory An area of memory shared among the processes that wish to communicate The communication is under the control of the users processes not the operating system. Major issues is to provide mechanism that will allow the user processes to synchronize their actions when they access shared memory. * 21CSC202J Operating Systems UNIT 2 32  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) – receive(message) The message size is either fixed or variable * 21CSC202J Operating Systems UNIT 2 33  Message Passing (Cont.) If processes P and Q wish to communicate, they need to: – Establish a communication link between them – Exchange messages via send/receive Implementation issues: – 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? * 21CSC202J Operating Systems UNIT 2 34  Message Passing (Cont.) Implementation of communication link – Physical: Shared memory Hardware bus Network – Logical: Direct or indirect Synchronous or asynchronous Automatic or explicit buffering * 21CSC202J Operating Systems UNIT 2 35  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 * 21CSC202J Operating Systems UNIT 2 36  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 * 21CSC202J Operating Systems UNIT 2 37  Indirect Communication Operations – create a new mailbox (port) – 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 * 21CSC202J Operating Systems UNIT 2 38  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. * 21CSC202J Operating Systems UNIT 2 39  Synchronization Message passing may be either blocking or non-blocking Blocking is considered synchronous – Blocking send -- the sender is blocked until the message is received – Blocking receive -- the receiver is blocked until a message is available Non-blocking is considered asynchronous – Non-blocking send -- the sender sends the message and continue – Non-blocking receive -- the receiver receives: A valid message, or Null message Different combinations possible If both send and receive are blocking, we have a rendezvous * 21CSC202J Operating Systems UNIT 2 40  Synchronization (Cont.) Producer-consumer becomes trivial message next_produced; while (true) { send(next_produced); } message next_consumed; while (true) { receive(next_consumed); } * 21CSC202J Operating Systems UNIT 2 41  Buffering Queue of messages attached to the link. implemented in one of three ways 1. Zero capacity – no messages are queued on a link. Sender must wait for receiver (rendezvous) 2. Bounded capacity – finite length of n messages Sender must wait if link full 3. Unbounded capacity – infinite length Sender never waits * 21CSC202J Operating Systems UNIT 2 42  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 * 21CSC202J Operating Systems UNIT 2 43  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 * 21CSC202J Operating Systems UNIT 2 44  Bounded-Buffer – Producer item next_produced; while (true) { while (((in + 1) % BUFFER_SIZE) == out) ; buffer[in] = next_produced; in = (in + 1) % BUFFER_SIZE; } * 21CSC202J Operating Systems UNIT 2 45  Bounded Buffer – Consumer item next_consumed; while (true) { while (in == out) ; next_consumed = buffer[out]; out = (out + 1) % BUFFER_SIZE; } * 21CSC202J Operating Systems UNIT 2 46  Examples of IPC Systems - POSIX POSIX Shared Memory Process first creates shared memory segment shm_fd = shm_open(name, O CREAT | O RDWR, 0666); Also used to open an existing segment to share it Set the size of the object ftruncate(shm fd, 4096); Now the process could write to the shared memory sprintf(shared memory, "Writing to shared memory"); * 21CSC202J Operating Systems UNIT 2 47  IPC POSIX Producer * 21CSC202J Operating Systems UNIT 2 48  IPC POSIX Consumer * 21CSC202J Operating Systems UNIT 2 49  Examples of IPC Systems - Mach Mach communication is message based – Even system calls are messages – Each task gets two mailboxes at creation- Kernel and Notify – Only three system calls needed for message transfer msg_send(), msg_receive(), msg_rpc() – Mailboxes needed for commuication, created via port_allocate() – Send and receive are flexible, for example four options if mailbox full: Wait indefinitely Wait at most n milliseconds Return immediately Temporarily cache a message * 21CSC202J Operating Systems UNIT 2 50  Examples of IPC Systems – Windows Message-passing centric via advanced local procedure call (LPC) facility – Only works between processes on the same system – Uses ports (like mailboxes) to establish and maintain communication channels – Communication works as follows: The client opens a handle to the subsystem’s connection port object. The client sends a connection request. The server creates two private communication ports and returns the handle to one of them to the client. The client and server use the corresponding port handle to send messages or callbacks and to listen for replies. * 21CSC202J Operating Systems UNIT 2 51  Local Procedure Calls in Windows * 21CSC202J Operating Systems UNIT 2 52  Communications in Client-Server Systems Sockets Remote Procedure Calls Pipes Remote Method Invocation (Java) * 21CSC202J Operating Systems UNIT 2 53  Sockets A socket is defined as an endpoint for communication Concatenation of IP address and port – a number included at start of message packet to differentiate network services on a host The socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8 Communication consists between a pair of sockets All ports below 1024 are well known, used for standard services Special IP address 127.0.0.1 (loopback) to refer to system on which process is running * 21CSC202J Operating Systems UNIT 2 54  Socket Communication * 21CSC202J Operating Systems UNIT 2 55  Sockets in Java Three types of sockets – Connection-orient ed (TCP) – Connectionless (UDP) – MulticastSock et class– data can be sent to multiple recipients Consider this “Date” server: * 21CSC202J Operating Systems UNIT 2 56  Remote Procedure Calls Remote procedure call (RPC) abstracts procedure calls between processes on networked systems – Again uses ports for service differentiation Stubs – client-side proxy for the actual procedure on the server The client-side stub locates the server and marshalls the parameters The server-side stub receives this message, unpacks the marshalled parameters, and performs the procedure on the server On Windows, stub code compile from specification written in Microsoft Interface Definition Language (MIDL) * 21CSC202J Operating Systems UNIT 2 57  Remote Procedure Calls (Cont.) Data representation handled via External Data Representation (XDL) format to account for different architectures – Big-endian and little-endian Remote communication has more failure scenarios than local – Messages can be delivered exactly once rather than at most once OS typically provides a rendezvous (or matchmaker) service to connect client and server * 21CSC202J Operating Systems UNIT 2 58  Execution of RPC * 21CSC202J Operating Systems UNIT 2 59  Pipes Acts as a conduit allowing two processes to communicate Issues: – Is communication unidirectional or bidirectional? – In the case of two-way communication, is it half or full-duplex? – Must there exist a relationship (i.e., parent-child) between the communicating processes? – Can the pipes be used over a network? Ordinary pipes – cannot be accessed from outside the process that created it. Typically, a parent process creates a pipe and uses it to communicate with a child process that it created. Named pipes – can be accessed without a parent-child relationship. * 21CSC202J Operating Systems UNIT 2 60  Ordinary Pipes Ordinary Pipes allow communication in standard producer-consumer style Producer writes to one end (the write-end of the pipe) Consumer reads from the other end (the read-end of the pipe) Ordinary pipes are therefore unidirectional Require parent-child relationship between communicating processes Windows calls these anonymous pipes * 21CSC202J Operating Systems UNIT 2 61  Named Pipes Named Pipes are more powerful than ordinary pipes Communication is bidirectional No parent-child relationship is necessary between the communicating processes Several processes can use the named pipe for communication Provided on both UNIX and Windows systems * 21CSC202J Operating Systems UNIT 2 62 Threads  Threads Overview Multicore Programming Multithreading Models Thread Libraries Implicit Threading Threading Issues Operating System Examples * 21CSC202J Operating Systems UNIT 2 64  Objectives To introduce the notion of a thread—a fundamental unit of CPU utilization that forms the basis of multithreaded computer systems To discuss the APIs for the Pthreads, Windows, and Java thread libraries To explore several strategies that provide implicit threading To examine issues related to multithreaded programming To cover operating system support for threads in Windows and Linux * 21CSC202J Operating Systems UNIT 2 65  Motivation Most modern applications are multithreaded Threads run within application 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 Can simplify code, increase efficiency Kernels are generally multithreaded * 21CSC202J Operating Systems UNIT 2 66  Multithreaded Server Architecture * 21CSC202J Operating Systems UNIT 2 67  Benefits Responsiveness – may allow continued execution if part of process is blocked, especially important for user interfaces Resource Sharing – threads share resources of process, easier than shared memory or message passing Economy – cheaper than process creation, thread switching lower overhead than context switching Scalability – process can take advantage of multiprocessor architectures * 21CSC202J Operating Systems UNIT 2 68  Multicore Programming Multicore or multiprocessor systems putting pressure on programmers, challenges include: – Dividing activities – Balance – Data splitting – Data dependency – Testing and debugging Parallelism implies a system can perform more than one task simultaneously Concurrency supports more than one task making progress – Single processor / core, scheduler providing concurrency * 21CSC202J Operating Systems UNIT 2 69  Multicore Programming (Cont.) Types of parallelism – Data parallelism – distributes subsets of the same data across multiple cores, same operation on each – Task parallelism – distributing threads across cores, each thread performing unique operation As # of threads grows, so does architectural support for threading – CPUs have cores as well as hardware threads – Consider Oracle SPARC T4 with 8 cores, and 8 hardware threads per core * 21CSC202J Operating Systems UNIT 2 70  Concurrency vs. Parallelism Concurrent execution on single-core system: Parallelism on a multi-core system: * 21CSC202J Operating Systems UNIT 2 71  Single and Multithreaded Processes * 21CSC202J Operating Systems UNIT 2 72  Amdahl’s Law Identifies performance gains from adding additional cores to an application that has both serial and parallel components S is serial portion N processing cores That is, if application is 75% parallel / 25% serial, moving from 1 to 2 cores results in speedup of 1.6 times As N approaches infinity, speedup approaches 1 / S Serial portion of an application has disproportionate effect on performance gained by adding additional cores But does the law take into account contemporary multicore systems? * 21CSC202J Operating Systems UNIT 2 73  User Threads and Kernel Threads User threads - management done by user-level threads library Three primary thread libraries: – POSIX Pthreads – Windows threads – Java threads Kernel threads - Supported by the Kernel Examples – virtually all general purpose operating systems, including: – Windows – Solaris – Linux – Tru64 UNIX – Mac OS X * 21CSC202J Operating Systems UNIT 2 74  Multithreading Models Many-to-One One-to-One Many-to-Many * 21CSC202J Operating Systems UNIT 2 75  Many-to-One Many user-level threads mapped to single kernel thread One thread blocking causes all to block Multiple threads may not run in parallel on muticore system because only one may be in kernel at a time Few systems currently use this model Examples: – Solaris Green Threads – GNU Portable Threads * 21CSC202J Operating Systems UNIT 2 76  One-to-One Each user-level thread maps to kernel thread Creating a user-level thread creates a kernel thread More concurrency than many-to-one Number of threads per process sometimes restricted due to overhead Examples – Windows – Linux – Solaris 9 and later * 21CSC202J Operating Systems UNIT 2 77  Many-to-Many Model Allows many user level threads to be mapped to many kernel threads Allows the operating system to create a sufficient number of kernel threads Solaris prior to version 9 Windows with the ThreadFiber package * 21CSC202J Operating Systems UNIT 2 78  Two-level Model Similar to M:M, except that it allows a user thread to be bound to kernel thread Examples – IRIX – HP-UX – Tru64 UNIX – Solaris 8 and earlier * 21CSC202J Operating Systems UNIT 2 79  Thread Libraries Thread library provides programmer with API for creating and managing threads Two primary ways of implementing – Library entirely in user space – Kernel-level library supported by the OS * 21CSC202J Operating Systems UNIT 2 80  Pthreads May be provided either as user-level or kernel-level A POSIX standard (IEEE 1003.1c) API for thread creation and synchronization Specification, not implementation API specifies behavior of the thread library, implementation is up to development of the library Common in UNIX operating systems (Solaris, Linux, Mac OS X) * 21CSC202J Operating Systems UNIT 2 81  Pthreads Example * 21CSC202J Operating Systems UNIT 2 82  Pthreads Example (Cont.) * 21CSC202J Operating Systems UNIT 2 83  Pthreads Code for Joining 10 Threads * 21CSC202J Operating Systems UNIT 2 84  Windows Multithreaded C Program * 21CSC202J Operating Systems UNIT 2 85  Windows Multithreaded C Program (Cont.) * 21CSC202J Operating Systems UNIT 2 86  Java Threads Java threads are managed by the JVM Typically implemented using the threads model provided by underlying OS Java threads may be created by: – Extending Thread class – Implementing the Runnable interface * 21CSC202J Operating Systems UNIT 2 87  Java Multithreaded Program * 21CSC202J Operating Systems UNIT 2 88  Java Multithreaded Program (Cont.) * 21CSC202J Operating Systems UNIT 2 89  Implicit Threading Growing in popularity as numbers of threads increase, program correctness more difficult with explicit threads Creation and management of threads done by compilers and run-time libraries rather than programmers Three methods explored – Thread Pools – OpenMP – Grand Central Dispatch Other methods include Microsoft Threading Building Blocks (TBB), java.util.concurrent package * 21CSC202J Operating Systems UNIT 2 90  Thread Pools Create a number of threads in a pool where they await work Advantages: – Usually slightly faster to service a request with an existing thread than create a new thread – Allows the number of threads in the application(s) to be bound to the size of the pool – Separating task to be performed from mechanics of creating task allows different strategies for running task i.e.Tasks could be scheduled to run periodically Windows API supports thread pools: * 21CSC202J Operating Systems UNIT 2 91  OpenMP Set of compiler directives and an API for C, C++, FORTRAN Provides support for parallel programming in shared-memory environments Identifies parallel regions – blocks of code that can run in parallel #pragma omp parallel Create as many threads as there are cores #pragma omp parallel for for(i=0;ivalue < 0) { add this process to S->list; block(); } } signal(semaphore *S) { S->value++; if (S->value list; wakeup(P); } } * 21CSC202J Operating Systems UNIT 2 136  Deadlock and Starvation Deadlock – two or more processes are waiting indefinitely 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 – indefinite 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 * 21CSC202J Operating Systems UNIT 2 137  Classical Problems of Synchronization Classical problems used to test newly-proposed synchronization schemes – Bounded-Buffer Problem – Readers and Writers Problem – Dining-Philosophers Problem * 21CSC202J Operating Systems UNIT 2 138  Bounded-Buffer Problem n buffers, 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 * 21CSC202J Operating Systems UNIT 2 139  Bounded Buffer Problem (Cont.) The structure of the producer process do {...... wait(empty); wait(mutex);...... signal(mutex); signal(full); } while (true); * 21CSC202J Operating Systems UNIT 2 140  Bounded Buffer Problem (Cont.) The structure of the consumer process Do { wait(full); wait(mutex);...... signal(mutex); signal(empty);...... } while (true); * 21CSC202J Operating Systems UNIT 2 141  Readers-Writers Problem A data set is shared among a number of concurrent processes – Readers – only read the data set; they do not perform any updates – Writers – can both read and write Problem – allow multiple readers to read at the same time – Only one single writer can access the shared data at the same time Several variations of how readers and writers are considered – all involve some form of priorities Shared Data – Data set – Semaphore rw_mutex initialized to 1 – Semaphore mutex initialized to 1 – Integer read_count initialized to 0 * 21CSC202J Operating Systems UNIT 2 142  Readers-Writers Problem (Cont.) The structure of a writer process do { wait(rw_mutex);...... signal(rw_mutex); } while (true); * 21CSC202J Operating Systems UNIT 2 143  Readers-Writers Problem (Cont.) The structure of a reader process do { wait(mutex); read_count++; if (read_count == 1) wait(rw_mutex); signal(mutex);...... wait(mutex); read count--; if (read_count == 0) signal(rw_mutex); signal(mutex); } while (true); * 21CSC202J Operating Systems UNIT 2 144  Readers-Writers Problem Variations First variation – no reader kept waiting unless writer has permission to use shared object Second variation – once writer is ready, it performs the write ASAP Both may have starvation leading to even more variations Problem is solved on some systems by kernel providing reader-writer locks * 21CSC202J Operating Systems UNIT 2 145  Dining-Philosophers Problem Philosophers spend their lives alternating thinking and eating Don’t interact with their neighbors, occasionally try to pick up 2 chopsticks (one at a time) to eat from bowl – Need both to eat, then release both when done In the case of 5 philosophers – Shared data Bowl of rice (data set) Semaphore chopstick initialized to 1 * 21CSC202J Operating Systems UNIT 2 146  Dining-Philosophers Problem Algorithm The structure of Philosopher i: do { wait (chopstick[i] ); wait (chopStick[ (i + 1) % 5] ); // eat signal (chopstick[i] ); signal (chopstick[ (i + 1) % 5] ); // think } while (TRUE); What is the problem with this algorithm? * 21CSC202J Operating Systems UNIT 2 147  Dining-Philosophers Problem Algorithm (Cont.) Deadlock handling – Allow at most 4 philosophers to be sitting simultaneously at the table. – Allow a philosopher to pick up the forks only if both are available (picking must be done in a critical section. – Use an asymmetric solution -- an odd-numbered philosopher picks up first the left chopstick and then the right chopstick. Even-numbered philosopher picks up first the right chopstick and then the left chopstick. * 21CSC202J Operating Systems UNIT 2 148  Problems with Semaphores Incorrect use of semaphore operations: – signal (mutex) …. wait (mutex) – wait (mutex) … wait (mutex) – Omitting of wait (mutex) or signal (mutex) (or both) Deadlock and starvation are possible. * 21CSC202J Operating Systems UNIT 2 149  Monitors A high-level abstraction that provides a convenient and effective mechanism for process synchronization Abstract data type, internal variables only accessible by code within the procedure Only one process may be active within the monitor at a time But not powerful enough to model some synchronization schemes monitor monitor-name { // shared variable declarations procedure P1 (…) { …. } procedure Pn (…) {……} Initialization code (…) { … } } } * 21CSC202J Operating Systems UNIT 2 150  Schematic view of a Monitor * 21CSC202J Operating Systems UNIT 2 151  Condition Variables condition x, y; Two operations are allowed on a condition variable: – x.wait() – a process that invokes the operation is suspended until x.signal() – x.signal() – resumes one of processes (if any) that invoked x.wait() If no x.wait() on the variable, then it has no effect on the variable * 21CSC202J Operating Systems UNIT 2 152  Monitor with Condition Variables * 21CSC202J Operating Systems UNIT 2 153  Condition Variables Choices If process P invokes x.signal(), and process Q is suspended in x.wait(), what should happen next? – Both Q and P cannot execute in paralel. If Q is resumed, then P must wait Options include – Signal and wait – P waits until Q either leaves the monitor or it waits for another condition – Signal and continue – Q waits until P either leaves the monitor or it waits for another condition – Both have pros and cons – language implementer can decide – Monitors implemented in Concurrent Pascal compromise P executing signal immediately leaves the monitor, Q is resumed – Implemented in other languages including Mesa, C#, Java * 21CSC202J Operating Systems UNIT 2 154  Monitor Solution to Dining Philosophers monitor DiningPhilosophers { enum { THINKING; HUNGRY, EATING) state ; condition self ; void pickup (int i) { state[i] = HUNGRY; test(i); if (state[i] != EATING) self[i].wait; } void putdown (int i) { state[i] = THINKING; // test left and right neighbors test((i + 4) % 5); test((i + 1) % 5); } * 21CSC202J Operating Systems UNIT 2 155  Solution to Dining Philosophers (Cont.) void test (int i) { if ((state[(i + 4) % 5] != EATING) && (state[i] == HUNGRY) && (state[(i + 1) % 5] != EATING) ) { state[i] = EATING ; self[i].signal () ; } } initialization_code() { for (int i = 0; i < 5; i++) state[i] = THINKING; } } * 21CSC202J Operating Systems UNIT 2 156  Solution to Dining Philosophers (Cont.) Each philosopher i invokes the operations pickup() and putdown() in the following sequence: DiningPhilosophers.pickup(i); EAT DiningPhilosophers.putdown(i); No deadlock, but starvation is possible * 21CSC202J Operating Systems UNIT 2 157  Monitor Implementation Using Semaphores Variables semaphore mutex; // (initially = 1) semaphore next; // (initially = 0) int next_count = 0; Each procedure F will be replaced by wait(mutex); … body of F; … if (next_count > 0) signal(next) else signal(mutex); Mutual exclusion within a monitor is ensured * 21CSC202J Operating Systems UNIT 2 158  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--; * 21CSC202J Operating Systems UNIT 2 159  Monitor Implementation (Cont.) The operation x.signal can be implemented as: if (x_count > 0) { next_count++; signal(x_sem); wait(next); next_count--; } * 21CSC202J Operating Systems UNIT 2 160  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 * 21CSC202J Operating Systems UNIT 2 161  Single Resource allocation Allocate a single resource among competing processes using priority numbers that specify the maximum time a process plans to use the resource R.acquire(t);... access the resurce;... R.release; Where R is an instance of type ResourceAllocator * 21CSC202J Operating Systems UNIT 2 162  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; } } * 21CSC202J Operating Systems UNIT 2 163