Hệ điều hành - Chapter 2: Processes and threads

Processes and ThreadsChapter 22.1 Processes2.2 Threads2.3 Interprocess communication2.4 Classical IPC problems2.5 Scheduling1ProcessesThe Process ModelMultiprogramming of four programsConceptual model of 4 independent, sequential processesOnly one program active at any instant2Process CreationPrincipal events that cause process creationSystem initializationExecution of a process creation system User request to create a new processInitiation of a batch job3Process TerminationConditions which terminate processesNormal exit (voluntary)Error exit (voluntary)Fatal error (involuntary)Killed by another process (involuntary)4Process HierarchiesParent creates a child process, child processes can create its own processForms a hierarchyUNIX calls this a "process group"Windows has no concept of process hierarchyall processes are created equal5Process States (1)Possible process statesrunningblockedreadyTransitions between states shown6Process States (2)Lowest layer of process-structured OShandles interrupts, schedulingAbove that layer are sequential processes7Implementation of Processes (1)Fields of a process table entry8Implementation of Processes (2)Skeleton of what lowest level of OS does when an interrupt occurs9ThreadsThe Thread Model (1)(a) Three processes each with one thread(b) One process with three threads10The Thread Model (2)Items shared by all threads in a processItems private to each thread11The Thread Model (3)Each thread has its own stack12Thread Usage (1)A word processor with three threads13Thread Usage (2)A multithreaded Web server14Thread Usage (3)Rough outline of code for previous slide(a) Dispatcher thread(b) Worker thread15Thread Usage (4)Three ways to construct a server16Implementing Threads in User SpaceA user-level threads package17Implementing Threads in the KernelA threads package managed by the kernel18Hybrid Implementations Multiplexing user-level threads onto kernel- level threads19Scheduler ActivationsGoal – mimic functionality of kernel threadsgain performance of user space threadsAvoids unnecessary user/kernel transitionsKernel assigns virtual processors to each processlets runtime system allocate threads to processorsProblem: Fundamental reliance on kernel (lower layer) calling procedures in user space (higher layer)20Pop-Up ThreadsCreation of a new thread when message arrives(a) before message arrives(b) after message arrives21Making Single-Threaded Code Multithreaded (1)Conflicts between threads over the use of a global variable22Making Single-Threaded Code Multithreaded (2)Threads can have private global variables23Interprocess CommunicationRace ConditionsTwo processes want to access shared memory at same time24Critical Regions (1) Four conditions to provide mutual exclusionNo two processes simultaneously in critical regionNo assumptions made about speeds or numbers of CPUsNo process running outside its critical region may block another processNo process must wait forever to enter its critical region25Critical Regions (2)Mutual exclusion using critical regions26Mutual Exclusion with Busy Waiting (1)Proposed solution to critical region problem(a) Process 0. (b) Process 1.27Mutual Exclusion with Busy Waiting (2)Peterson's solution for achieving mutual exclusion28Mutual Exclusion with Busy Waiting (3)Entering and leaving a critical region using the TSL instruction29Sleep and WakeupProducer-consumer problem with fatal race condition30SemaphoresThe producer-consumer problem using semaphores31MutexesImplementation of mutex_lock and mutex_unlock32Monitors (1)Example of a monitor33Monitors (2)Outline of producer-consumer problem with monitorsonly one monitor procedure active at one timebuffer has N slots34Monitors (3)Solution to producer-consumer problem in Java (part 1)35Monitors (4)Solution to producer-consumer problem in Java (part 2)36Message PassingThe producer-consumer problem with N messages37BarriersUse of a barrierprocesses approaching a barrierall processes but one blocked at barrierlast process arrives, all are let through38Dining Philosophers (1)Philosophers eat/thinkEating needs 2 forksPick one fork at a time How to prevent deadlock 39Dining Philosophers (2)A nonsolution to the dining philosophers problem40Dining Philosophers (3)Solution to dining philosophers problem (part 1)41Dining Philosophers (4)Solution to dining philosophers problem (part 2)42The Readers and Writers ProblemA solution to the readers and writers problem43The Sleeping Barber Problem (1)44The Sleeping Barber Problem (2)Solution to sleeping barber problem.45SchedulingIntroduction to Scheduling (1)Bursts of CPU usage alternate with periods of I/O waita CPU-bound processan I/O bound process46Introduction to Scheduling (2)Scheduling Algorithm Goals47Scheduling in Batch Systems (1)An example of shortest job first scheduling48Scheduling in Batch Systems (2)Three level scheduling49Scheduling in Interactive Systems (1)Round Robin Schedulinglist of runnable processeslist of runnable processes after B uses up its quantum50Scheduling in Interactive Systems (2)A scheduling algorithm with four priority classes51Scheduling in Real-Time SystemsSchedulable real-time systemGivenm periodic eventsevent i occurs within period Pi and requires Ci secondsThen the load can only be handled if52Policy versus MechanismSeparate what is allowed to be done with how it is donea process knows which of its children threads are important and need priorityScheduling algorithm parameterizedmechanism in the kernelParameters filled in by user processespolicy set by user process53Thread Scheduling (1)Possible scheduling of user-level threads50-msec process quantumthreads run 5 msec/CPU burst54Thread Scheduling (2)Possible scheduling of kernel-level threads50-msec process quantumthreads run 5 msec/CPU burst55