Process Slides - UMD PDF Free Download

2y ago

49 Views

1 Downloads

2.46 MB

40 Pages

Report/dmca

Download PDF

Transcription

Operating Systems:Processes and ThreadsShankarFebruary 10, 2022

Outline1. Overview2. Process State3. Process Creation4. Process Termination5. User-Threads Management6. Booting the OS7. Inter-Process Communication: Pipes8. Inter-Process Communication: Signals9. Inter-Process Communication: Internet Sockets10. SchedulersOverview

User PerspectiveProcess: executing instance of a programThreads: active agents of a processAddress spacetext segment: codedata segment: global and staticstack segment, one per threadResources: open les and socketsCode: non-privileged instructionsincluding syscalls to access OS servicesAll threads execute concurrentlyOverview

OS KernelOverviewData structure: state of processes, user threads, kernel threadsProcess: address space, resources, user threadsuser thread: user-stack, kernel-stack, processor statemapping of content to hardware location (eg, memory, disk)memory vs disk (swapped out)user thread status: running, ready, waiting, modeKernel thread: kernel-stack, processor stateSchedulers:short-term:io device:readywaitingmedium-term:long-term: runningstart ready swapped-outio serviceready/waitingreadye cency and responsiveness

Single-Threaded ProcessProcess statePCB (process control block): one per processholds enough state to resume the processprocess id (pid)processor state: gpr, ip, ps, sp, .address-space: text, data, user-stack, kernel-stackmapping to memory/diskio state: open les/sockets, current positions, access, .accounting info: processor time, memory limits, .Statusrunning: executing on a processorready (aka runnable): waiting for a processorwaiting: for a non-processor resource (eg, memory, io, .)swapped-out: holds no memory

Multi-Threaded ProcessProcess statePCB (process control block): one per processaddress-space: text, dataio stateaccounting infoTCBs (thread control block): one per thread// userprocessor stateuser-stack, kernel-stackstatus: running, ready, waiting, .Process swapped-out all threads swapped outUser thread:user-mode: executing user code, using user-stackkernel-mode: executing kernel code, using kernel-stackthread

Kernel threadsProcess stateThreads belonging to the kernelasynchronous services: io, reaper, .always in kernel-modeTCB (thread control block): one per kernel threadholds enough state to resume the threadprocessor state: gpr, ip, ps, sp, .kernel-stackstatus: running, ready, waiting// nouser-stack

Process queuesProcess stateKernel keeps PCBs/TCBs in queuesnew queue: processes to be startedrun queueready (aka runnable) queueio queue(s)swapped-out queueterminated queue: processes to be cleaned upTransitions between queuesio completion / wakeupnewadmitreadytimerrunningdispatchio req / waitmedium term schedulerswapped outwaitingterminatedkill

User-level ThreadsProcess stateThreads implemented entirely in user processKernel is not aware of themkernel sees only one user threadUser code maintainsTCBssignal handlers (for timer/io/etc interrupts)dispatcher, schedulerOS provides low-level functions via which user process canget processor statedispatch processor stateto/from environment variablesUser-level vs kernel-levelPro: application-speci c schedulingCon: cannot exploit additional processors

Approach 1: Create Process from ScratchCreateProcess(path,read le from lecontext):system's pathacquire memory segmentsProcess creation// GeekOS Spawn// executable le// code, data, stack(s), .unpack le into its segmentscreate PCBupdate PCB with// pid, .context// user, directory, .add PCB to ready queueDrawback:contexthas a lot of parameters to set

Approach 2: Fork-ExecProcess creationFork(): creates a copy of the caller process// returns 0 to child, and child's pid to parentcreate a duplicate PCBexcept for pid, accounting, pending signals, timers,outstanding io operations, memory locks, .only one thread (the one that called fork)allocate memory and copy parent's segmentsminimize overhead: copy-on-write; memory-map hardwareadd PCB to the ready queueExec(path, .): replaces all segments of executing processexec[elpv] variants: di erent ways to pass args, .open les are inheritednot inherited: pending signals, signal handlers, timers, memorylocks, .environment variables are inherited except with exec[lv]e

ZombieProcessAProcess terminationAbecomes a zombie whenexecutes relevant OS code (intentionally or o/w)exit syscallillegal opexceeds resource limits.AAgets kill signal from a (ancestor) processis moved to terminated queueWhat happens toA'schild process (if any)becomes a root process's child (orphan)// Unixis terminated// VMS

ReapProcess terminationProcessAin the termination queue is eventually reapedits memory is freedits parent is signalled (SIGCHILD)it waits for parent to do wait syscallparent gets exit status, accounting info, .

POSIX threadsthread create(thrd, func, arg)create a new user thread executing func(arg)return pointer to thread info in thrdthread yield():calling thread goes from running to readyscheduler will resume it laterthread join(thrd):wait for thread thrd to nishreturn its exit codethread exit(rval):terminate caller thread, set caller's exit code to rvalif a thread is waiting to join, resume that threaduser threads

OS initializationBootPower-up:BIOS: disk boot sector RAM reset addressprocessor starts executing contentsBoot-sector code:load kernel code from disk sectors to RAM, start executingKernel initialization:identify hardware: memory size, io adaptors, .partition memory: kernel, free, .initialize structures: vm/mmap/io tables, pcb queues, .start daemons: OS processes that run in the backgroundidleio-serverslogin/shell process bound to consolemount lesystem(s) in io device(s)

PipesKernel file data structures Inode table: has a copy of the inode of every openvertex (file or directory)– may differ from the inode in the disk Open-file table: has an entry for every open call notyet succeeded by a close call (across all processes)Each entry holds:– current file position, reference count (how many filedescriptors point to the entry), inode pointer, etc.– Entry is removed when the reference count is 0 For each process: a file descriptor table, mappingintegers to open-file table entries 2016 L. Herman & A. U. Shankar398

PipesOpening the same file twicefd1 open("file.txt", O RDONLY);fd2 open("file.txt", O RDONLY);read(fd2, buffer, 1024);file descriptortable(per process)open-file entry 1position0FDref. count 10inode1234 2016 L. Herman & A. U. Shankarinode tableinode table entryopen file tablepermissions 0666sizetypeopen-file entry 2position.regular fileinode table entry1024ref. count 150238. inode399

PipesAfter a fork()fd1 open("file.txt", O RDONLY);fd2 open("file.txt", O RDONLY);read(fd2, buffer, 1024);fork();parentFD.34childFDopen file tableopen file 1position0ref. count2inodeopen file 2sizeposition10243ref. count24inode. 2016 L. Herman & A. U. Shankarinode table entrypermissions 066650238typeregular file.400

PipesOpening a pipeint pfd[2];pipe(pfd);open file tableFD01234open file (read)positionn/aref. count 1inodeopen file (write)positionn/ainode table entrypermissions 0666size0typepipe.ref. count 1inode 2016 L. Herman & A. U. Shankar406

Pipesint pfd[2];pipe(pfd);fork();parentFD.After a fork()open file tableopen file (read)positionn/a3ref. count 24inodechildFD.34 2016 L. Herman & A. U. Shankaropen file (write)positionn/aref. count 2inode table entrypermissions 0666size0typepipe.inodeExample pipe-example.c407

Example: data transfer on pipe from parent to childProcess, sayAABA,Pipescreates pipeforks, creating child process, sayBcloses its read-end of pipe, writes to pipecloses its write-end of pipe, reads from pipebyte stream: in-chunks need not equal out-chunksABblocks if bu er is full andBblocks if bu er is empty andhas not closed read-endAhas not closed write-endread when no data and no writers (write-end has zero ref count):read returns 0write when no readers (read-end has zero ref count):writer process receives SIGPIPE signalwrite returns EPIPE

Signals: user perspectiveSignalsProcess-level interrupt with a small integer argumentn(0.255)SIGKILL, SIGCHILD, SIGSTOP, SIGSEGV, SIGILL, SIGPIPE, .Who can send a signal to a processP:// syscallanother process (same user/ admin)kill(pid, n )kernelPitselfWhenPsignalgets a signalnfor eachPnit executes a signal handler , sayis pending untiln,Pstarts executingat most one signalat any time,Eachn,Pnshcan be pending atPcan be executing at most one signal handlerhas a default handler: ignore signal, terminatecan register handlers for some signalsif so,Psh// syscallalso registers a trampoline function,which issues syscall complete handlerP,.signal(sh, n )

Signals: implementationP 's pcb haspending bitongoing bitSignalsn// true// truefor eachi signalnpendingi any signal handler is being executedP gets a signal n, kernel sets pending n.Causes sh to execute at some point when P is notWhenrunningpending n and not ongoing :kernel sets ongoing , clears pending n , starts executingwhen sh ends, kernel unsets ongoing .When kernel-handledpending n, not ongoing,ongoing , clears pending n,When user-handledkernel setssavesPPP 'sshwith argumentwill return fromPPshnand enter trampolinereturns to kernel (via complete handler),kernel clearsongoingand restoresP 'sstack(s)shin user mode:stack(s) somewhere and modi es them so thatwill enterwhenandits

Stacks when handling user-level signal (x86 style)user stackkernel stackprior to resumingustack0Signalsistate0usp0--in user mode, signalistate0: interrupt stateusp0: top of user stackprior to usp2ustack0istate0usp0Pistate1: istate0 with eip shusp1: usp0 sizeof(n, &trampoline)just prior to resuming-pendingin user modejust after executing syscallustack0nof processnistate0andPusp0atcomplete handleristate0restored

Internet Streaming SocketsSocketsTwo-way data path: client process server processServer:ss socket(INET,STREAMING)// get a socketbind(ss, server port)client addr:port accept(ss)send(ss, data)data // byte streamrecv(ss)close(ss)// byte stream// returns when remote also closesClientsc statussocket(INET, send(sc, data)data recv(sc)close(sc)STREAMING)// get a socketconnect(sc, server addr:port) // returns sucess or fail// byte stream// byte stream

Socketsclient tcp socketAx1tcp socket server[ip addr, tcp port]x2Bbind(x2)accept( )connect(x2)opentcp opening handshakesend(data)recv( )dataopen to x1send(data)tcp data transferrecv( )dataclose( )tcp closing handshakeclose( )

SchedulersSchedulerio completion / wakeupnewadmitreadytimerrunningdispatchio req / waitwaitingterminatedkillmedium term schedulerswapped outShort-term (milliseconds) : ready runninghigh utilization: fraction of time processor doing useful worklow wait-time: time spent in ready queue per processfairness / responsiveness: wait-time vs processor timeMedium-term (seconds): ready/waiting swapped-outavoid bottleneck processor/device (eg, thrashing)ensure fairnessnot relevant for single-user systems (eg, laptops, workstations)

Short-term: Non-PreemptiveNon-preemptive:running /SchedulerreadyWait-time of a process: time it spends in ready queueFIFOarrival joins at tail// from waiting, new or suspendeddeparture leaves from head// to runningfavors long processes over short onesfavors processor-bound over io-boundhigh wait-time: short process stuck behind long processShortest-Job-First (SJF)assumes processor times of ready PCBs are knowndeparture is one with smallest processor timeminimizes wait-timeFixed-priority for processes: eg: system, foreground, background

Short-term: Preemptive 1Preemptive:running SchedulerreadyWait-time of a process: total time it spends in ready queueRound-RobinFIFO with time-slice preemption of running processarrival from running, waiting, new or suspendedall processes get same rate of serviceoverhead increases with decreasing timesliceideal: timeslice slightly greater than typical cpu burst

Short-term: Preemptive 2SchedulerMulti-level Feedback Queuepriority of a process depends on its historydecreases with accumulated processor timequeue 1, 2,···,queueN// decreasing prioritydeparture comes from highest-priority non-empty queuearrival coming not from running:joins queue 1arrival coming from runningjoins queuemin(i 1, N)//iwas arrival's previous levelTo avoid starvation of long processeslonger timeslice for lower-priority queuesafter a process spends a speci ed time in low-priority queuemove it to a higher-priority queue.

Multiprocessor SchedulingSchedulerSet of ready processes is sharedSo scheduling involvesget lock on ready queueensure it is not in a remote processor's cachechoose a process (based on its usage of processor, resources, .)Process may acquire a nity to a processor (ie, to its cache)makes sense to respect this a nity when schedulingPer-processor ready queues simpli es scheduling, ensures a nitybut risk of unfairness and load imbalanceCould dedicate some processors to long-running processesand others to short/interactive processes

2. Process State 3. Process Creation 4. Process erminationT 5. User-Threads Management 6. Booting the OS 7. Inter-Process Communication: Pipes 8. Inter-Process Communication: Signals 9. Inter-Proces