Process Concept - UPTU Khabar



Process ConceptAn operating system executes a variety of programs:Batch system – jobsTime-shared systems – user programs or tasksTextbook uses the terms job and process almost interchangeablyProcess – a program in execution; process execution must progress in sequential fashion29718008826500A process includes:program counter stackdata sectionProcess in MemoryProcess StateAs a process executes, it changes statenew: The process is being createdrunning: Instructions are being executedwaiting: The process is waiting for some event to occurready: The process is waiting to be assigned to a processorterminated: The process has finished executionDiagram of Process State685800106680003657600-11430000Process Control Block (PCB)Information associated with each processProcess stateProgram counterCPU registersCPU scheduling informationMemory-management informationAccounting informationI/O status informationCPU Switch From Process to Process12573004826000Process Scheduling QueuesJob queue – set of all processes in the systemReady queue – set of all processes residing in main memory, ready and waiting to executeDevice queues – set of processes waiting for an I/O deviceProcesses migrate among the various queuesReady Queue And Various I/O Device Queues8001004826000Representation of Process Scheduling8001008445500SchedulersLong-term scheduler (or job scheduler) – selects which processes should be brought into the ready queueShort-term scheduler (or CPU scheduler) – selects which process should be executed next and allocates CPUAddition of Medium Term Scheduling68580010922000Short-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 multiprogrammingProcesses can be described as either:I/O-bound process – spends more time doing I/O than computations, many short CPU burstsCPU-bound process – spends more time doing computations; few very long CPU burstsContext SwitchWhen 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 switchContext of a process represented in the PCBContext-switch time is overhead; the system does no useful work while switchingTime dependent on hardware supportProcess CreationParent process create children processes, which, in turn create other processes, forming a tree of processesGenerally, process identified and managed via a process identifier (pid)Resource sharingParent and children share all resourcesChildren share subset of parent’s resourcesParent and child share no resourcesExecutionParent and children execute concurrentlyParent waits until children terminateAddress spaceChild duplicate of parentChild has a program loaded into itUNIX examplesfork system call creates new processexec system call used after a fork to replace the process’ memory space with a new program57150040703500Process CreationC Program Forking Separate Processint main(){pid_t pid;/* fork another process */pid = fork();if (pid < 0) { /* error occurred */fprintf(stderr, "Fork Failed");exit(-1);}else if (pid == 0) { /* child process */execlp("/bin/ls", "ls", NULL);}else { /* parent process *//* parent will wait for the child to complete */wait (NULL);printf ("Child Complete");exit(0);}}137795026035000A tree of processes on a typical SolarisProcess TerminationProcess 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 systemParent may terminate execution of children processes (abort)Child has exceeded allocated resourcesTask assigned to child is no longer requiredIf parent is exiting?Some operating system do not allow child to continue if its parent terminatesAll children terminated - cascading terminationInterprocess CommunicationProcesses within a system may be independent or cooperatingCooperating process can affect or be affected by other processes, including sharing dataReasons for cooperating processes:Information sharingComputation speedupModularityConvenienceCooperating processes need interprocess communication (IPC)Two models of IPCShared memoryMessage passingCommunications Models 160020018669000Cooperating ProcessesIndependent process cannot affect or be affected by the execution of another processCooperating process can affect or be affected by the execution of another processAdvantages of process cooperationInformation sharing Computation speed-upModularityConvenienceProducer-Consumer ProblemParadigm for cooperating processes, producer process produces information that is consumed by a consumer processunbounded-buffer places no practical limit on the size of the bufferbounded-buffer assumes that there is a fixed buffer sizeBounded-Buffer – Shared-Memory SolutionShared data#define BUFFER_SIZE 10typedef struct {. . .} item;item buffer[BUFFER_SIZE];int in = 0;int out = 0;Solution is correct, but can only use BUFFER_SIZE-1 elementsBounded-Buffer – Producerwhile (true) { /* Produce an item */ while (((in = (in + 1) % BUFFER SIZE count) == out) ; /* do nothing -- no free buffers */ buffer[in] = item; in = (in + 1) % BUFFER SIZE; }Bounded Buffer – Consumerwhile (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; }Interprocess Communication – Message PassingMechanism for processes to communicate and to synchronize their actionsMessage system – processes communicate with each other without resorting to shared variablesIPC 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 themexchange messages via send/receiveImplementation of communication linkphysical (e.g., shared memory, hardware bus)logical (e.g., logical properties)Direct CommunicationProcesses must name each other explicitly:send (P, message) – send a message to process Preceive(Q, message) – receive a message from process QProperties of communication linkLinks are established automaticallyA link is associated with exactly one pair of communicating processesBetween each pair there exists exactly one linkThe link may be unidirectional, but is usually bi-directionalIndirect CommunicationMessages are directed and received from mailboxes (also referred to as ports)Each mailbox has a unique idProcesses can communicate only if they share a mailboxProperties of communication linkLink established only if processes share a common mailboxA link may be associated with many processesEach pair of processes may share several communication linksLink may be unidirectional or bi-directionalOperationscreate a new mailboxsend and receive messages through mailboxdestroy a mailboxPrimitives are defined as:send(A, message) – send a message to mailbox Areceive(A, message) – receive a message from mailbox AMailbox sharingP1, P2, and P3 share mailbox AP1, sends; P2 and P3 receiveWho gets the message?SolutionsAllow a link to be associated with at most two processesAllow only one process at a time to execute a receive operationAllow the system to select arbitrarily the receiver. Sender is notified who the receiver was.SynchronizationMessage passing may be either blocking or non-blockingBlocking is considered synchronousBlocking send has the sender block until the message is receivedBlocking receive has the receiver block until a message is availableNon-blocking is considered asynchronousNon-blocking send has the sender send the message and continueNon-blocking receive has the receiver receive a valid message or nullBufferingQueue of messages attached to the link; implemented in one of three ways1.Zero capacity – 0 messagesSender must wait for receiver (rendezvous)2.Bounded capacity – finite length of n messagesSender must wait if link full3.Unbounded capacity – infinite length Sender never waitsExamples of IPC Systems - POSIXPOSIX Shared MemoryProcess first creates shared memory segmentsegment id = shmget(IPC PRIVATE, size, S IRUSR | S IWUSR);Process wanting access to that shared memory must attach to itshared memory = (char *) shmat(id, NULL, 0);Now the process could write to the shared memoryprintf(shared memory, "Writing to shared memory");When done a process can detach the shared memory from its address spaceshmdt(shared memory);Examples of IPC Systems - MachMach communication is message basedEven system calls are messagesEach task gets two mailboxes at creation- Kernel and NotifyOnly three system calls needed for message transfermsg_send(), msg_receive(), msg_rpc()Mailboxes needed for commuication, created viaport_allocate()Examples of IPC Systems – Windows XPMessage-passing centric via local procedure call (LPC) facilityOnly works between processes on the same systemUses ports (like mailboxes) to establish and maintain communication channelsCommunication 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 replies68580034290000Local Procedure Calls in Windows XPCommunications in Client-Server SystemsSocketsRemote Procedure CallsRemote Method Invocation (Java)SocketsA socket is defined as an endpoint for communicationConcatenation of IP address and portThe socket 161.25.19.8:1625 refers to port 1625 on host 161.25.19.8Communication consists between a pair of socketsSocket Communication9144008826500Remote Procedure CallsRemote procedure call (RPC) abstracts procedure calls between processes on networked systemsStubs – client-side proxy for the actual procedure on the serverThe client-side stub locates the server and marshalls the parametersThe server-side stub receives this message, unpacks the marshalled parameters, and peforms the procedure on the serverExecution of RPC16579851968500Remote Method InvocationRemote Method Invocation (RMI) is a Java mechanism similar to RPCsRMI allows a Java program on one machine to invoke a method on a remote object13716007937500Marshalling Parameters137160016256000ThreadsTo introduce the notion of a thread — a fundamental unit of CPU utilization that forms the basis of multithreaded computer systemsTo discuss the APIs for the Pthreads, Win32, and Java thread librariesTo examine issues related to multithreaded programming91440024955500Single and Multithreaded ProcessesBenefitsResponsivenessResource SharingEconomyScalabilityMulticore ProgrammingMulticore systems putting pressure on programmers, challenges includeDividing activitiesBalanceData splittingData dependencyTesting and debuggingMultithreaded Server Architecture228600-635000Concurrent Execution on a Single-core System5715004762500Parallel Execution on a Multicore System5715004127500User ThreadsThread management done by user-level threads librarynThree primary thread libraries:POSIX Pthreadsl Win32 threadsJava threadsKernel ThreadsSupported by the KernelExamplesWindows XP/2000SolarisLinuxTru64 UNIXMac OS XMultithreading ModelsMany-to-OneOne-to-One44577008318500Many-to-ManyMany-to-OneMany user-level threads mapped to single kernel threadExamples:Solaris Green ThreadsGNU Portable ThreadsOne-to-OneEach user-level thread maps to kernel threadExamplesWindows NT/XP/2000LinuxSolaris 9 and later228600-11430000Many-to-Many ModelAllows many user level threads to be mapped to many kernel threadsAllows the operating system to create a sufficient number of kernel threadsSolaris prior to version 9Windows NT/2000 with the ThreadFiber package91440021590000Two-level ModelSimilar to M:M, except that it allows a user thread to be bound to kernel thread27432007239000ExamplesIRIXHP-UXTru64 UNIXSolaris 8 and earlierThread LibrariesThread library provides programmer with API for creating and managing threadsTwo primary ways of implementingLibrary entirely in user spaceKernel-level library supported by the OSPthreadsMay be provided either as user-level or kernel-levelA POSIX standard (IEEE 1003.1c) API for thread creation and synchronizationAPI specifies behavior of the thread library, implementation is up to development of the libraryCommon in UNIX operating systems (Solaris, Linux, Mac OS X)Java ThreadsJava threads are managed by the JVMTypically implemented using the threads model provided by underlying OSJava threads may be created by:lExtending Thread classImplementing the Runnable interfaceThreading IssuesSemantics of fork() and exec() system callsThread cancellation of target threadAsynchronous or deferredSignal handlingThread poolsThread-specific dataScheduler activationsThread CancellationTerminating a thread before it has finishedTwo general approaches:Asynchronous cancellation terminates the target thread immediatelyDeferred cancellation allows the target thread to periodically check if it should be cancelledSignal HandlingSignals are used in UNIX systems to notify a process that a particular event has occurredA signal handler is used to process signals1.Signal is generated by particular event2.Signal is delivered to a process3.Signal is handledOptions:Deliver the signal to the thread to which the signal appliesDeliver the signal to every thread in the processDeliver the signal to certain threads in the processAssign a specific threa to receive all signals for the processThread PoolsCreate a number of threads in a pool where they await workAdvantages:Usually slightly faster to service a request with an existing thread than create a new threadAllows the number of threads in the application(s) to be bound to the size of the poolThread Specific DataAllows each thread to have its own copy of dataUseful when you do not have control over the thread creation process (i.e., when using a thread pool)Scheduler ActivationsBoth M:M and Two-level models require communication to maintain the appropriate number of kernel threads allocated to the applicationScheduler activations provide upcalls - a communication mechanism from the kernel to the thread libraryThis communication allows an application to maintain the correct number kernel threads34290043688000Windows XP ThreadsImplements the one-to-one mapping, kernel-levelEach thread containsA thread idRegister setSeparate user and kernel stacksPrivate data storage areaThe register set, stacks, and private storage area are known as the context of the threadsThe primary data structures of a thread include:ETHREAD (executive thread block)KTHREAD (kernel thread block)TEB (thread environment block)34290041719500Linux ThreadsLinux refers to them as tasks rather than threadsThread creation is done through clone() system callclone() allows a child task to share the address space of the parent task (process)CPU SchedulingTo introduce CPU scheduling, which is the basis for multiprogrammed operating systemsTo describe various CPU-scheduling algorithmsTo discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular systemMaximum CPU utilization obtained with multiprogrammingCPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O waitCPU burst distribution125730034353500Histogram of CPU-burst Times114300045339000Alternating Sequence of CPU And I/O BurstsCPU Scheduler Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of themCPU scheduling decisions may take place when a process:1.Switches from running to waiting state2.Switches from running to ready state3.Switches from waiting to ready4.TerminatesScheduling under 1 and 4 is nonpreemptiveAll other scheduling is preemptiveDispatcherDispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:switching contextswitching to user modejumping to the proper location in the user program to restart that programDispatch latency – time it takes for the dispatcher to stop one process and start another runningScheduling CriteriaCPU utilization – keep the CPU as busy as possibleThroughput – # of processes that complete their execution per time unitTurnaround time – amount of time to execute a particular processWaiting time – amount of time a process has been waiting in the ready queueResponse time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)Max CPU utilizationMax throughputMin turnaround time Min waiting time Min response timeFirst-Come, First-Served (FCFS) SchedulingProcessBurst TimeP124 P2 3 P3 3 Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:457200113030P1P2P3242730000P1P2P32427300Waiting time for P1 = 0; P2 = 24; P3 = 27Average waiting time: (0 + 24 + 27)/3 = 17Suppose that the processes arrive in the order P2 , P3 , P1 The Gantt chart for the schedule is:nnnnWaiting time for P1 = 6; P2 = 0; P3 = 3nAverage waiting time: (6 + 0 + 3)/3 = 3Much better than previous caseConvoy effect short process behind long process114300264795P1P3P26330000P1P3P263300Shortest-Job-First (SJF) SchedulingAssociate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest timeSJF is optimal – gives minimum average waiting time for a given set of processesThe difficulty is knowing ProcessArrival TimeBurst Time P10.06 P2 2.08 P34.07 P45.03SJF scheduling chartaverage waiting time = (3 + 16 + 9 + 0) / 4 = 7the length of the next CPU request57150010160P4P3P131609P22400P4P3P131609P224Determining Length of Next CPU BurstCan only estimate the lengthCan be done by using the length of previous CPU bursts, using exponential averaging45720027940000Prediction of the Length of the Next CPU BurstExamples of Exponential Averaging =0n+1 = nRecent history does not count =1 n+1 = tnOnly the actual last CPU burst countsIf we expand the formula, we get:n+1 = tn+(1 - ) tn -1 + … +(1 - )j tn -j + … +(1 - )n +1 0Since both and (1 - ) are less than or equal to 1, each successive term has less weight than its predecessorPriority SchedulingA priority number (integer) is associated with each processThe CPU is allocated to the process with the highest priority (smallest integer highest priority)PreemptivenonpreemptiveSJF is a priority scheduling where priority is the predicted next CPU burst timeProblem Starvation – low priority processes may never executeSolution Aging – as time progresses increase the priority of the processRound Robin (RR)Each process gets a small unit of CPU time (time quantum), usually 10-100 milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue.If there are n processes in the ready queue and the time quantum is q, then each process gets 1/n of the CPU time in chunks of at most q time units at once. No process waits more than (n-1)q time units.Performanceq large FIFOq small q must be large with respect to context switch, otherwise overhead is too highExample of RR with Time Quantum = 4ProcessBurst TimeP124 P2 3 P33685800341630P1P2P3P1P1P1P1P104710141822263000P1P2P3P1P1P1P1P1047101418222630The Gantt chart is: Typically, higher average turnaround than SJF, but better responseTime Quantum and Context Switch Time11430011430000Turnaround Time Varies With The Time Quantum80010010223500Multilevel QueueReady queue is partitioned into separate queues:foreground (interactive)background (batch)Each queue has its own scheduling algorithmforeground – RRbackground – FCFSScheduling must be done between the queuesFixed priority scheduling; (i.e., serve all from foreground then from background). Possibility of starvation.Time slice – each queue gets a certain amount of CPU time which it can schedule amongst its processes; i.e., 80% to foreground in RR20% to background in FCFS 80010034290000Multilevel Queue SchedulingMultilevel Feedback QueueA process can move between the various queues; aging can be implemented this wayMultilevel-feedback-queue scheduler defined by the following parameters:number of queuesscheduling algorithms for each queuemethod used to determine when to upgrade a processmethod used to determine when to demote a processmethod used to determine which queue a process will enter when that process needs serviceExample of Multilevel Feedback QueueThree queues: Q0 – RR with time quantum 8 millisecondsQ1 – RR time quantum 16 millisecondsQ2 – FCFSSchedulingA new job enters queue Q0 which is served FCFS. When it gains CPU, job receives 8 milliseconds. If it does not finish in 8 milliseconds, job is moved to queue Q1.At Q1 job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.Multilevel Feedback Queues160020012446000Thread SchedulingDistinction between user-level and kernel-level threadsMany-to-one and many-to-many models, thread library schedules user-level threads to run on LWPKnown as process-contention scope (PCS) since scheduling competition is within the processKernel thread scheduled onto available CPU is system-contention scope (SCS) – competition among all threads in systemPthread SchedulingAPI allows specifying either PCS or SCS during thread creationPTHREAD SCOPE PROCESS schedules threads using PCS schedulingPTHREAD SCOPE SYSTEM schedules threads using SCS scheduling.Pthread Scheduling API#include <pthread.h>#include <stdio.h>#define NUM THREADS 5int main(int argc, char *argv[]){ int i;pthread t tid[NUM THREADS];pthread attr t attr;/* get the default attributes */pthread attr init(&attr);/* set the scheduling algorithm to PROCESS or SYSTEM */pthread attr setscope(&attr, PTHREAD SCOPE SYSTEM);/* set the scheduling policy - FIFO, RT, or OTHER */pthread attr setschedpolicy(&attr, SCHED OTHER);/* create the threads */for (i = 0; i < NUM THREADS; i++)pthread create(&tid[i],&attr,runner,NULL);/* now join on each thread */for (i = 0; i < NUM THREADS; i++)pthread join(tid[i], NULL);} /* Each thread will begin control in this function */void *runner(void *param){ printf("I am a thread\n");pthread exit(0);}Multiple-Processor SchedulingCPU scheduling more complex when multiple CPUs are availableHomogeneous processors within a multiprocessorAsymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharingSymmetric multiprocessing (SMP) – each processor is self-scheduling, all processes in common ready queue, or each has its own private queue of ready processesProcessor affinity – process has affinity for processor on which it is currently runningsoft affinityhard affinityNUMA and CPU Scheduling13716008699500Multicore ProcessorsRecent trend to place multiple processor cores on same physical chipFaster and consume less powerMultiple threads per core also growingTakes advantage of memory stall to make progress on another thread while memory retrieve happens 80010030543500Multithreaded Multicore SystemOperating System ExamplesSolaris schedulingWindows XP schedulingLinux scheduling91440026670000Solaris Dispatch Table 1943100000Solaris Scheduling45720042989500Windows XP PrioritiesLinux SchedulingConstant order O(1) scheduling timeTwo priority ranges: time-sharing and real-timeReal-time range from 0 to 99 and nice value from 100 to 140Priorities and Time-slice length1143000241300068580033020000List of Tasks Indexed According to PrioritiesAlgorithm EvaluationDeterministic modeling – takes a particular predetermined workload and defines the performance of each algorithm for that workloadQueueing models262890012509500ImplementationEvaluation of CPU schedulers by Simulation ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download