New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Computer System Concepts

by: Abe Jones

Computer System Concepts CS 350

Abe Jones
GPA 3.77

Donald Adjeroh

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Donald Adjeroh
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 46 page Class Notes was uploaded by Abe Jones on Saturday September 12, 2015. The Class Notes belongs to CS 350 at West Virginia University taught by Donald Adjeroh in Fall. Since its upload, it has received 64 views. For similar materials see /class/202757/cs-350-west-virginia-university in ComputerScienence at West Virginia University.

Similar to CS 350 at WVU

Popular in ComputerScienence


Reviews for Computer System Concepts


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/12/15
CS 350 Computer System Concepts Port ll C5350 Operating Systems Part Topics 0 Brief history of operoting systems Processes ond threods lnterprocess communicotion Deodlocks Files Memory Introduction CS 350 Port ll Operating Systems Services Introduction Whot is on Operoting System Softwore thot octs os on intermediory between the hordwore ond opplicotion progroms An operoting system hos two moin functions 1 A monoger for occess to hordwore re sources CPU memory spoce disk space lO devices Protection foirness ond effi ciency ore importont M To provide obstroctions of the hordwore of 0 much higher level thon the hordwore itself The file is 0 much more usoble stor oge obstroction thon the disk These obstroctions olso hide the peculiar ities of porticulor devices eg different size disks lhtrod uctlon 2 CS 350 ParT ll OperaTing SysTems Services Introduction coan Two general goals of an operaTing sysTem Convenience for The users 0 Efficiency and fairness in resource uTiliza Tion An operaTing sysTem provides a virfual machine 0 CS 350 emphasizes The absTracTions pro vided by an operaTing sysTem processes files special files communicaTion eTc 0 CS 450 CS 451 emphasize The resource managemenT Techniques required in an operaTing sysTem lhTroducTion 3 CS 350 ParT ll OperaTing SysTems Services Operating sysTem services The 08 provides services To boTh The users and The underlying sysTem User side 0 program execuTion a file manipulaTion lO operaTions o communicaTions 0 error deTecTion SysTem side resource allocaTion o accounTing proTecTion lhTroducTion 4 CS 350 Part II Operating SysTems Services Operating system boundaries Usually The OS is Taken To comprise all software ThaT runs in supervisor mode OTher pieces of sysTem soTTwa re shells file ma nipulaTion uTiliTies compilers eTc are noT con sidered parT of The operaTing sysTem Many recent 08 have moved many TradiTional 08 components such as significant parTs of The file and process subsystems inTo programs ThaT run in user mode These componenTs are sTill regarded as parT of The OS buT This Trend has blurred The boundary between The OS and oTher software Introduction 5 CS 350 Part II Operating SysTems Services History of operating systems Because of The close relaTionship between 08 and hardware 08 generations are closely re laTed To hardware generations 0 Babbage s analyTical engine design no 08 a 1st generation 1945 1955 Vacuum Tube based Plugboards and laTer card in puT No 08 a 2nd generation 1955 1965 Transistorbased BaTch operaTing systems Tapes cards and prinTers FMS IBSYS Introduction 6 CS 350 Par r Operaiing Sysiems Services CS 350 Par r Operaiing Sysiems Services The 4th Generation 19801990 The Third Generation 19651980 LSI VLSI personal oompuiers worksiaiions iVISDOS and Unix Small scale iniegraied oirouiis IBM 360 series and 08360 I I I I Cheap mioroprooessors muITiprooessor sysiems Baioh muITIprogrammIng OS muliiplejobs each loosely and gh yooupledI in a memory pariiiion Spooling Timesharing OS Terminals iVIULTICS influeniial Neiwork and disiribuied OS I I Over The decades The emphasis has Changed M39nquotC mpUTer5 PDP range from having The OS maximise use of very ex pensive hardware To having ii provide good Uhlx39 absiraoiions and rapid inieraoiive response Introduction 7 Iniroduciion 8 CS 350 PorT ll OperoTing SysTems Services Unix history UNICS Timeshdring OS Developed 69 73 on d PDP 7 0T ATampT Bell Lobs RewriTTen in C porTed To PDP ii Versions 6 76 end 7 78 widely dis TribuTed ATampT commercidl reledses SysTems Ill 82 and V 83 Berkeley BSD 78 VirTudl memory sockeTs dnd TOPIF vi csh improved file sysTem SunOS sTdrTed ds 0 BSD derivoTive Mdny neT working fedTures odded NFS consider cross ferTilisdTion wiTh oTher Unix voridnTs Linux sTdrTed 0s The personal projecT of Linus Torvalds in 1991 Through cooperdTive devel opmenT iT hos snowbdlled inTo d sophisTicoTed operoTing sysTem whose source code is free Highly portable many derivoTives STdnddrd isdTion efforTs POSIX XOpen lnTroducTion 9 CS 350 PorT ll OperoTing SysTems Services Processes A running program Hos Three mdin sTdTes run ning currenle using The CPU ready Tem pordrily suspended by The CPU To leT oThers run and blocked dlso coiled sleeping un dble To run woiTing for on eXTerndl evenT eg I 0 blocked Processes 10 CS 350 Port II Operating Systems Services CS 350 Port II Operating Systems Services Informotion obout or process in mointoined in o doto structure coiled process table Some of these ottributes con be seen by using the top onoI ps commonols Process Attributes and Process Tables Processes hove c or process ID pid 0 o porent process ID IDIOioI o or user ID uid o o progrom counter PC 0 or current size o o commond nome or current working directory cwd o on environment 0 other stuff Processes i i Processes 12 CS 350 PorT ll OperoTing SysTems Services Operations on a Process OperdTions Tth can be performed on 0 pro cess include credTe 0 process TermindTe 0 process suspend or process resume 0 process modify process s prioriTy block 0 process 0 wokeup or process dispchh 0 process Processes is CS 350 PorT ll OperoTing SysTems Services Process Trees A process can credTe 0 new process The cre dTing process is coiled d parenT process while The new process is coiled 0 child process The child can in Turn credTe new processes The re sulT is d hierarchy of process coiled 0 process Tree Creating a process The fork sysTem coll AfTer fork The new process is 0 copy of The porenT BoTh processes conTinue execuTion df Ter The fork The only difference is in The reTurn value of The fork sysTem coll Processes 14 CS 350 PorT OperoTihg SysTems Services include ltstdiohgt main int pid if pid fork 0 printfquotI amthe childnquot else printfquotI amthe parentnquot Processes 15 CS 350 PorT OperoTihg SysTems Services Executing other programs The members of The exec family of sysTem coils overloy The currenT process wiTh onoTher Six versions of exec They differ in wheTher The orgumenTs are supplied as on array or IisT wheTher The currenT environmenT is Transferred or noT onol wheTher The poTh is searched or noT execlp onol execvp ore mosT ofTen used BoTh pass The currenT environmenT To The new pro gram and ouTomoTiColly search The PATH en vironmenT vorioble Processes 16 CS 350 PorT ll OperoTing SysTems Services The exec CCIIIS execlp Tokes iTs orgumenT os 01 lisT iT is used when The number of orgumenTs is known be fore hond oT compile Time char anarg execlpquotbincatquot quotcatquot anarg char NULL execvp Tokes iTs orgumenT os on orroy iT is used when The number of orgumenTs is unkown oT compile Time char theargs execvptheargs 0 theargs Processes i 7 CS 350 PorT ll OperoTing SysTems Services WaiTing and ending A process con wait on iTs children Child pro cesses ThoT ore finished buT noT woiTed for be come zombies If 0 porenT TerminoTes wiTh ouT woiTing for 0 child The child becomes on orphon end is odopTed by The init process pid i init woiTs periodicolly for children so oprhon zombies ore evenTuolly removed Ending a process 1 return from The moin funcTion 2 Finishing The moin funcTion Folling off The end 3 Using The exit sysTem coil The inTeger orgumenT is The reTurn volue of The pro grom Processes 18 CS 350 Port ll Operating Systems Services Multitasking lVlultitosking is ollowing more then one process gt 0 time so that the system feels like there ore multiple CPUs Cooperative multitasking A process decides when it needs 0 breok ond lets the operoting system give control to onother process Preemptive multitasking Processes ore inter rupted periodicolly by the operoting system to ollow other processes to execute Typicolly 0 process will be interrupted ot leost every iOOms A process con olso be blocked if it is woiting for IO eg text input or 0 resource that is currently busy Processes 19 CS 350 Port ll Operating Systems Services The shell The operoting system is the code that corries out system coils The OS shell is the commond intepreter It provides on interfoce between the user end the OS The shell is storted up when ever 0 user logsin The shell is not port of the operoting system but mokes heovy use of its feotures There ore mony shells for Unix some of which ore shboshoshkshcshtcshzshtcshwish All of the obove shells hove the obility to run commonds ond write scripts lVlost hove the obility of file redirection ond pipes When 0 simple commond is typed in the shell eg date the shell forks then the child execs the dote commond end the porent waits for the child to finish When the child hos finished the shell prints out the prompt ond tries to reod more input Processes 20 CS 350 PorT ll OperoTing SysTems Services The shell coan RedirecTion To 0 file date gt my file is done by firsT opening my file Then using The dup2 sysTem coll To copy The file descripTor formy file To The file descripTor for stdout RedirecTion from 0 file sort lt myfile is done simliorly WiTh stdin Pipes beTween programs ore ochieved by con necTing The oquuT of one progrom To The in puT of The oTher ExompleThe pipe ls sort is ocheived by connecTing The sTondord ouT puT of ls To The sTondord inpuT of sort This hos The some effecT os ls gt temp sort lt temp rm temp A process con be run in The bockground using The ompersond amp chorocTer morph3d amp In This cose The shell forks ond The child execs morph3d os usuol buT The porenT doesn T wait forThe child To finish lnsTeod iT prinTs The prompT immedioTely ond occest ony inpuT Processes 21 CS 350 PorT ll OperoTing SysTems Services OperaTing SysTem Calls OperoTing sysTem coils usuollyjusT coiled sys Tem coils ore The progrommer s inTerfoce To The operoTing sysTem UNIX Typicolly hos obouT 200 sysTem coils These ofTen look similor To librory coils which moy or moy noT moke sysTem coils Generolly if on error occurs while execuTing o sysTem coil The sysTem coll reTurns The volue 1ond seTs The globol vorioble errno To some opproprioTe volue There is o C librory funcTion in ltstdio hgt coiled perror which Tokes o sTring ond prinTs ouT ThoT sTring olong wiTh on opproprioTe messoge oc cording To errno Processes 22 CS 350 Part II Operating Systems Services System call errors There are about 120 possible values for errno These can be seen in the file usrincludesyserrnoh define define define define define define define define define define EPERM ENOENT ESRCH EINTR EIO ENXIO E2BIG ENOEXEC EBADF ECHILD l Not super user 2 No such file or directory 3 No such process 4 interrupted system call 5 IO error 6 No such device or address 7 Arg list too long 8 Exec format error 9 Bad file number 10 No children Moceses 23 CS 350 Part II Operating Systems Services Interprocess Communication Independent process one that cannot affect or be affected by other executing processes Cooperating process one that can affect or be affected by other executing processes Why process cooperation Need access to a shared resource printer 0 Share some workload between processes large parallelizable jobs 0 Give instructions to a process CTRLC 0 Pass information to a process window size has changed lnterprocess Communication 24 CS 350 Part II Operating Systems Services Cooperating processes contd Cooperating processes require c a mechanism for communication between them 0 synchronization between processes to ensure data consistency Interprocess Communication 25 CS 350 Part II Operating Systems Services Signals Signals can be received by a process They are generated when some unusual event re quires attention They can be generated from various sources Hardware such as divide by zero 0 Operating System such as notifying that file size limit is exceeded o Other Processes such as a child process notifying its parent that it has terminated User such as pressing CTRLZ or CTRLC or using the kill command Interprocess Communication 26 CS 350 ParT ll OperaTing SysTems Services Actions on Signals The receiving process can do one of Three Things upon receiving a signal 1 M A Default Do The defaulT acTion for The sig nal For mosT signals This causes The pro cess To TerminaTe Ignore Ignore The signal This can T be done forTwo of The signals SIGSTOP which sTops The process from execuTing and SIGKILL which kills The process Catch CaTch The signal This also can T be done for SIGSTOP and SIGKILL When a process caTches a signal iT execuTes a special signal handling rouTine lhTerprocess CommunicaTion CS 350 ParT ll OperaTing SysTems Services Signal numbers The number of signals is limiTed No informaTion can be senT wiTh a signal The lisT of signals can be shown by The command kill 1 1SIGHUP 2 SIGINT 3 SIGQUIT 4 SIGILL 5 SIGTRAP 6 SIGIOT 7 SIGEMT 8 SIGFPE 9 SIGKILL 10 SIGBUS 11 SIGSEGV 12 SIGSYS 13 SIGPIPE 14 SIGALRM 15 SIGTERM 16 SIGUSRi 17 SIGUSR2 18 SIGCHLD 19 SIGPWR 20 SIGWINCH 21 SIGURG 22 SIGIO 23 SIGSTOP 24 SIGTSTP 25 SIGCONT 26 SIGTTIN 27 SIGTTOU 28 SIGVTALRM 29 SIGPROF 30 SIGXCPU 31 SIGXFS 28 lhTerprocess CommunicaTion CS 350 Porf Operofing Sysfems Services Sending signals Wifhin o progrom fhe raise sysfem coil is used To send signols fo yourself The kill sysfem coil is used To send signols fo 0 specified process The alarm sysfem coll sends fhe SIGALRM sys fem coll fo ifself offer 0 specified number of reol seconds Inferprocess Communicaiion 29 CS 350 Porf Operofing Sysfems Services signal example include ltsystypeshgt include ltunistdhgt include ltsignalhgt include ltstringhgt include ltstdiohgt char handmng quotI found Acnquot void catchctrlcint signo writeSTDERRFILENO handmsg strlenhandmsg void main void struct sigaction act act sahandler catchctrlc sigemptysetampact samask actsaflags 0 if sigactionSIGINT ampact NULL lt 0 perrorquotError setting signal handlerquot sleep1000 sleep1000 sleep1000 Inferprocess Communicaiion 30 CS 350 PorT ll OperoTihg SysTems Services CS 350 PorT ll OperoTihg SysTems Services Signal Summary Signals provide a basic communicaTion Technique They do noT carry any informaTion ParTicipaTing processes musT know each oThers process IDs The number of signals is limiTed CooperaTing processes musT agree on The meaning of each signal No easy way for The sending process To know if iTs signal was received Signal manipulaTion can be Tricky IhTerprocess CommunicaTion Semaphores and Shared Memory shared int account deposit with race condition void depositint money int balance account account balance money Don T wanT To be inTerrupTed Need muTuaI exclusion for criTicaI secTion IhTerprocess CommunicaTion 32 CS 350 PorT ll OperoTing SysTems Services More race conditions shared int lock 0 shared int account non solution for race condition void depositint money int balance while lock 1 busy wait lock 1 balance account account balance money lock 0 lnTerprocess Communication 33 CS 350 PorT ll OperoTing SysTems Services criticalsecTion problem SoluTions To The criTicorlsecTion problem musT soTisfy The following a Mutual exclusion AT mosT one process in The criTicol secTion oT ony Time 0 Progress If no process is execuTing iTs criT icol secTion 0 process ThoT wishes To en Ter con geT in Bounded waiting No process is posTponed indefiniTely There musT be 0 limiT To The number of Times 0 process may enTer o criTicol secTion if onoTher process is woiT ing To geT in lnTerprocess CommunicoTion 34 CS 350 Pari ll Operaiing Sysiems Services Methods for mutual exclusion with busy waiting 0 Disabling inierupis 0 Look variables 0 Sirioi aliernaiion roundrobin o TSL insiruoiion hardware Problems 0 Busy wailing wasies CPU Time 0 Prioriiy inversion problem Inlerprocess Communicalion 35 CS 350 Pari ll Operaiing Sysiems Services Semaphores Semaphores can be used To proieoi oriiioal seoiions Down operation oleoremenis semaphore or puis process To sleep if The semaphore is zero Up operation inoremenis semaphore Wakes up a process if ii is sleeping on ii The semaphore operaiions are aiomic mean ing They can i be inierrupieol Inlerprocess Communicalion so CS 350 Part II Operating Systems Services Semaphore example shared binary semaphore mutex l semaphore solves race condition void depositint money int balance down ampmutex int balance account account balance money up ampmutex Interprocess Communication 37 CS 350 Part II Operating Systems Services Semaphores for synchronization Can also use semaphores for synchronization eg producer consumer INITIALIZATION shared binary semaphore mutex h shared counting semaphore empty MAX shared counting semaphore full 0 shared anytype bufferMAX shared int in 0 out 0 count O PRODUCER anytype item repeat produce something item produce wait for an empty space downempty store the item downmutex bufferin in in 1 mod MAX count count h upmutex report the new full slot upfull until done Interprocess Communication 38 CS 350 Par r Opera rihg Sys rems Services Semaphore example conld CONSUMER anytype repeat until item wait for a stored item downfull remove the item downmutex item bufferout out out 1 mod MAX count count 1 up mutex report the new empty slot up empty consume it consume item done lhlerprocess Communication 39 CS 350 Par r ll Opera rihg Sys rems Services Semaphores and UNIX There are Two main implemeniaiions of semaphores POSIX 10031b and Sysiem V POSIX implemen Taiion of boih is simpler bui Sysiem V is more widely used There are also Xehix semphores Problems wiih semaphores deadlock all The processes musi follow The rules lhlerprocess CommUhicaliOh 40 CS 350 ParT ll OperoTing SysTems Services Shared memory and UNIX There are Two main implemenTaTions of shared memory POSIX 10031b and SysTem V POSIX implemenTaTions are buT SysTem V is more widely used The child of a process will inheriT all The open files of The parenT aT The Time of The fork This can be used To share files beTween pro cesses Files can be memorymapped using mmap Thus creaTing shared memory beTween Two processes The map sysTem call has The advanTage ThaT The conTenTs resides in a file so iT can be used beTween processes ThaT exisT aT dinerenT Times Shared memory is very fasT BuT care musT be Taken wiTh synchronisaTion Using map is The way To go as iT is less complex and more porTable Than POSIX or SysTem V shared memory lnTerprocess CommunicaTion 41 CS 350 PorT ll OperoTing SysTems Services Message Passing Message passing consisTs of Two primiTives send or write and receive or read There are many variaTions o Buffered and unbquered Blocking and nonblocking Message boundary preserving and mes sage boundary ignoring half duplex reading or wriTing buT noT boTh and full duplex reading and wriT ing a Reliable and unreliable lnTerprocess CommunicaTion 42 CS 350 PorT ll OperoTihg SysTems Services Some issues in Message Passing Message passing can be used for 0 process synchronizaTion and inTerprocess communicaTion However The use of message passing calls for consideraTion of cerTain issues such as AcknowledgemenTs and reTronsmissions o Naming and adressing AuTheTincaTion 0 Performance lhTerprocess CommunicaTlon 43 CS 350 PorT ll OperoTihg SysTems Services Pipes in UNIX Buffered FIFO Message boundaries are noT pre served Can be blocking or nonblocking Usu ally fullduplex Can be named or unnamed Unnamed pipes can only be used beTween Two relaTed processes eg childparenT or child child They disappear when The processes have finished An unnamed pipe is consTrucTed wiTh The pipe sysTem call The synTaX is int pipe int fdes 2 The Two file descrip Tors fdes 0 and fdes 1 refer To each end of The pipe One is used for wriTing and The oTher is used for reading lhTerprocess CommunicaTlon 44 CS 350 PorT ll OperoTing SysTems Services Named Pipes Nomed pipes hove on enTry in The filesysTem They persisT ofTer processes hove used Them They con be used beTween unreloTed processes providing The permissions ore seT correchy A nomed pipe con be generoTed from The shell wiTh The mknod commond For exomple mknod aPipe p creoTes 01 pipe nomed aPipe in The currenT di recTory This con be wriTTen To ls gt aPipe amp ond reod from Too cat lt aPipe Nomed pipes con olso be creoTed wiTh The mknod sysTem coll lnTerprocess CommunicoTion 45 CS 350 PorT ll OperoTing SysTems Services popen and pclose The process of generoTing 01 pipe spowning 0 child process orgonising The file descripTors ond possing commond execuTion informoTion from one process To onoTher vio The pipe is quiTe common The sTondord lO librory provides popen ond pclose TO do This lnTerprocess CommunicoTion 46 CS 350 Part II Operating Systems Services uses popen to execute a command and display the output of that command include ltstdiohgt include ltunistdhgt include ltlimitshgt int mainint argc char argV FILE fin int n char bufferPIPEBUF fin popenargvl quotrquot printfquotOutput from snquotargvl fflushstdout while n readfilenofin buffer PIPEBU39E gt 0 writel buffer n pclosefin return 0 CS 350 Part II Operating Systems Services Problems with Pipes No easy way to determine who the writing pro cess was Can t communicate between processes on dif ferent machines Can get deadlock Interprocess Communication 47 Interprocess Communication 48 CS 350 PorT OperoTing SysTems Services deadlock example with pipes include ltstdiohgt include ltunistdhgt include ltstdlibhgt include ltstringhgt int main int fdes2 static char sBUFSIZ if pipefdes 1 perrorquotPipequot exit2 switch fork case 1 perrorquotForkquot exit3 case 0 writefdesl s sizeofs fprintfstderrquotChild herenquot break default writefdesl s sizeofs fprintfstderrquotParent herenquot InTerprocess Communication 49 CS 350 PorT OperoTing SysTems Services Sockets in UNIX SockeTs provide on inTerfdce To The communi coTion neTwork Bufferd FIFO Can be beTween unreldTed pro cesses Can be beTween differenT machines on d neTwork Cdn hdve differenT domains of communica Tion a UNIX domdin SockeTs hdve OCTUOI file homes They can only be used wiTh processes Tth reside on The same hosT InTerneT domdin Allows unreldTed processes on differenT hosTs To communicoTe via The InTerneT InTerprocess CommunicaTion 50 CS 350 Part II Operating Systems Services Socket types Two basic types STREAM sockets TCPIP 0 connection oriented o reliable 0 communication is with a byte stream message boundaries are not preserved CS 350 Part II Operating Systems Services lnterprocess Communication 5 Socket types contd DATAGRAM sockets UDPIP connectionless unreliable message boundaries are preserved packets are normally small and fixed in size lnterprocess Communication 52 CS 350 Par r Opera ring Sys rems Services Clientserver in UNIX SockeTbased communicaTion is of reh used for cliehTserver appicaTions The server provides some service To cliehT programs Thai connec r To ii via The sockei ihierface Web server and web browser cliehT The cliehT server model is used ofTeh There is a file etcservices on mosi UNIX sysTems Thai COhTOihS a Iisi of services offered by server programs via The sockei ihierface The num bers are khWOh as pori s Interprocess Communication 53 CS 350 Par r Opera ring Sys rems Services etcservices ftp 2 l tcp telnet 2 3 tcp smtp 2 5 tcp mail time 37tcp timserver time 37udp timserver name 42 udp nameserver whois 43 tcp nicname ii usually to sri nic domain 53 tcp domain 53 udp bootps 67udp ii bootp server bootpc 68udp ii bootp client tftp 69udp gopher 70tcp ii gopher server finger 7 9 tcp ht tp 8 0 tcp PorTs under 1024 are reserved Normal user processes musi use poris above 1023 Interprocess Communication 54 CS 350 PorT ll OperoTing SysTems Services Sockets from a server39s view The Typicol sequence for seTTing up on lnTerneT domdin TCPIP connecTionorienTed sockeT for 0 server is M l A 5 CredTe The sockeT wiTh socket sysTem coll Assign on dddressporT pdir To The sockeT wiTh bind sysTem coll In The UNIX do mdin d Tilendme is used CredTe d queue for incoming connecTion requesTs wiTh listen The server is now ready To dccepT 0 con necTion from d clienT process wiTh The accept sysTem coll By defdulT accept will block if There is no requesT for connecTion lnTerprocess CommunicoTion CS 350 PorT ll OperoTing SysTems Services 5 Once d connecTion hos been mode from d clienT wiTh accept The server con read and write To The sockeT By defdulT read and write block if They connoT compleTe Their dcTion OfTen once 0 connecTion hos been accepted The server will fork and The child server will deal exclusively wiTh The clienT Tth hos con necTed This seTup simplifies Things somewth The por enT only needs To dccepT connecTions and fork children The children only need To re spond To requesTs lnTerprocess CommunicoTion 56 CS 350 ParT ll OperaTihg SysTems Services Sockets from a client39s view The cliehT s job is somewhaT easier Than The server 1 CreaTe The sockeT wiTh socket sysTem call 2 lhiTiaTe a connecTion wiTh The server wiTh The connect sysTem call 3 Use read and write as usual Resolving hosThames ie TrahsIaTihg mymachihecseewvuedu To 15718219488 is done using The gethostbyname sysTem call lhTerprocess CommunicaTTOh 57 CS 350 ParT ll OperaTihg SysTems Services Classical IPC problems These are basically problems in process coor dinaTion ahol synchronizaTion There are sev eral variaTions Producerconsumer problem someTimes called The boundedbuffer problem ReaderswriTers problem for daTa base ac cess Diningphilosophers problem for resource conTenTion Sleepingbarber problem CigareTTe smokers problem ObserversreporTers problem IPC problems 58 CS 350 ParT ll OperaTing SysTems Services Readerswriters problem A daTa objecT is shared among several con currenT processes Readers Processes ThaT only wanT To read The shared objecT Writers Processes ThaT wanT To updaTe read and wriTe The shared objecT Any number of readers may access The daTa aT one Time buT wriTers musT have exclusive access How do we program The reader and wriTer IPC problems 59 CS 350 ParT ll OperaTing SysTems Services Approaches To The ReadersWriters problem A soluTion To This problem depends on whaT prioriTies are required 1 No reader will be kepT waiTing unless a wriTer is already updaTing The daTa some Times called firsTreader wriTer problem M If a wriTer is waiTing To access The daTa no new readers may sTarT reading some Times called second readerwriTer prob lem BoTh of These approaches may lead To sTarva Tion IPC problems 60 CS 350 PorT ll OperoTing SysTems Services ReadersWriters solution for case 1 shared binary semaphore mutex 1 shared binary semaphore db 1 int readcount O READER downmutex readcount if readcount 2 1 then downdb upmutex CRITICAL REGION where we read downmutex readcount if readcount 2 then updb upmutex WRITER downdb CRITICAL REGION where we write updb IPC problems lt51 CS 350 PorT ll OperoTing SysTems Services Dining Philosophers Five philosophers ore sedTed Ground 0 Circular Tobie There is one fork beTween edoh philospher and d pldTe of slippery spdgheTTi in fronT of each philosopher A philosopher needs To grdb The Two ddjdoenT forks in order To edT buT can only grab one 0T 0 Time Philosophers dITerndTe beTween edTing and Think ing They only edT for TiniTe periods of Time IPC problems 62 CS 350 Part II Operating Systems Services CS 350 Part II Operating Systems Services Dining Philosophers poor solution shared binary semaphore fork5 l Philosopheri whileTRUE think downforki downforkil5 eat upforki upforkil5 IPC problems Dining Philosophers better solution Proposed solution We could modify the algo rithm so that after taking the left fork the pro gram checks to see if the right fork is available If it is not the philosopher puts down the left fork waits for a while then tries the whole pro cess again What if all philosophers start at the same time The programs continue to run but never make progress starvation Why not have each process wait a random amount of time Want a solution that always works and can t fail due to an unlikely series of random num bers IPC problems 64 CS 350 Por r Opero rihg Sys rems Services Dining Philosophers solution 1 shared binary semaphore fork5 1 shared binary semaphore mutex l Philosopheri whileTRUE think downampmutex downforki downforkil5 eat upforki upforkil5 upampmutex Only one philosopher con eo r oi 0 Time WhoT if we had 100 philosophers Up To 50 should be able To eo r oi once IPC probierhs 65 CS 350 Por r Opero rihg Sys rems Services D1n1ng ph1losophers solut1on 2 1nt staten shared b1nary semaphore mutex shared b1nary semaphore sN Vo1d ph1losopher 1nt m wh1le TRUE 1 th1nk takeiforks1 eat putiforks1 Vo1d takeiforks1nt 1 Vo1d test 1nt 1 downampmutex state1 Hungry test1 upampmutex down amps1 Vo1d putiforks1nt 1 downampmutex state1 Th1nk1ng testLEFT testRIGHT upampmutex 1f state1 Hungry ampamp stateLEFT Eat1ng ampamp stateRIGHT Eat1ng state1 Eat1ng upimim IPC probierhs 66 CS 350 ParT ll OperaTing SysTems Services Equivalence of IPC Primitives Under cerTain condiTions for insTance on a machine wiTh a single CPU The differenT inTer process communicaTion primiTives are seman Tically equivalenT ThaT is for each or The Three basic primiTives semaphores message passing or moniTors we can use one To implemenT The oTher This fur Ther implies ThaT The synchronizaTion problems solved using one primiTive can also be solved using any of The oThers CS 350 ParT ll OperaTing SysTems Services IPC problems 67 Deadlocks Resources These are generally objecTs could be hardware eg prinTer or sofTware eg daTa records To which processes can be given exclusive righTs PreempTabIe resource a resource which can be Taken away from The currenT process hold ing iT wiThouT causing The compuTaTion To fail eg CPU and memory NonpreemTable resource a resource which cannoT be Taken away from iTs currenT owner wiThouT adverse effecTs on The resulTs exam ple prinTer Deadlocks usually involve nonpreemTable resources EvenT Sequence for resources 1 RequesT re source 2 Use resource 3 Release resource Deadlock A sysTem is in a deadlock if for some seT of processes in The sysTem each process in The seT is waiTing for an evenT ThaT can only be caused To occur by anoTher process in The seT Deadlocks 68 CS 350 ParT ll OperaTing SysTems Services Conditions for deadlock A deadlock condiTion can arise if The following four condiTions hold simulTaneously 1 Mutual Exclusion AT leasT one resource musT be nonsharable Only one process aT a Time can use iT M Hold and waiT Processes currenle hold ing resources granTed earlier can requesT new resources A No preemption Resources given To a pro cess can noT be forcibly Taken away from The process A process musT give Them up volunTarily b Circular waiT There musT be a circular chain of processes each of which is waiTing for a resource held by The neXT member of The chain Deadlocks 69 CS 350 ParT ll OperaTing SysTems Services Handling deadlocks The osTrich algorithm All four condiTions musT be presenT for a dead lock To occur If one is absenT no deadlock is possible WhaT should be done if deadlock occurs Can use The osTrich algoriThm This is The mosT common meThod of dealing wiTh deadlocks sTick your head in The sand and preTend There is no problem aT all Works quiTe well if deadlocks occur infrequenle PrevenTing deadlocks can be quiTe complicaTed To do well The dining philosophers problem Allowing deadlocks To occur and Then recov ering from Them is also an opTion Deadlocks 70 CS 350 Part II Operating SysTems Services Resource Allocation Graph The resource allocation graph RAGis a direcTed graph ThaT shows The relationship between The processes and resources in The sysTem An edge from a process To a resource indicates ThaT The process is making a request for The resource and ThaT The resource has noT yeT been allo caTed To The process For a resource ThaT has successfully been claimed by a process The edge is from The resource To The process Process P requests for resource R P e R Resource R is allocaTed To P R gt P A Typical RAG can Thus be represenTed by a seT of edges EPi gtRiP2 gtR3Ri gtP2R2 gtP2R2 gt PiR3eP3 Deadiocks 7i CS 350 Part II Operating SysTems Services Deadlock Detection Single Instance of The Resources When There are single insTances of each re source Type iT is easy To deTecT deadlocks us ing The RAG This is done by deTecTing cycles in The graph If a cycle exisTs There is a deadlock in The sysTem otherwise There is no deadlock Multiple Instances of Each Resource When There are possible multiple instances of each resources The existence of cycles in The resource allocation graph may noT necessarily mean ThaT deadlock exists A cycle is a neces sary buT noT sufficient condition for deadlocks in such cases Thus new conditions may need To be meT To deTecT deadlocks Typically a matrix based meThod is used which makes use of different information such as The existing resource and available resource vec Tors and The currenT allocation and request matrices Deadiocks 72 CS 350 PorT ll OperoTing SysTems Services Deadlock Detection wiTh Multiple Resources using RAGs In The case of mulTiple insTonces of or resource The following sTroTegy con be used To deTecT deodlock using The resource ollocoTion groph There musT exisT some cycle in The sysTem LeT Rm number of resource Rk ovoiloble Then for There To be or deodlock involving resource Rk Rk musT be involved in oT leosT Rm cycles Thus in The case of mulTiple insTonces The fol lowing should be done i DeTecT ALL The cycles in The graph 2 For each resource in The sysTem or 0 cy cle check how many cycles ThoT involve ThoT resource Deodiocks 73 CS 350 PorT ll OperoTing SysTems Services 3 If or resource wiTh soy Rm insTonces is in volved in lt Rm number of cycles Then ThoT resource is noT involved in o deod lock 4 If 3 above holds for oil The resources in The sysTem or The cycle Then There is no deodlock Deodiocks 74 CS 350 PorT ll OperoTing SysTems Services CS 350 PorT ll OperoTing SysTems Services prior knowledge of moximum resource needs a fixed number of processes Deadlock Aviodqnce 0 fixed number of resources WiTh some odvonce informoTion obouT processes resource need deodlock con be ovoided Avioding deodlock requires The sysTem To know if ollocoTing o requesTed resource will resulT inTo o sofe or on unsofe sToTe Safe STaTe There exisTs oT leosT one woy in which The sysTem con soTisfy oil resouce requesTs ThoT is The sysTem con guoronTee ThoT oil pro cesses will finish Unsafe STaTe There is no guoronTee ThoT oil requesT will be soTisifed The sysTem is noT yeT in o deodlock buT could geT inTo one The generol meThod used To deTermine if d sysTem will be in o sofe or unsofe sToTe is The Bonker s olgoriThm This is however noT olwoys opplicoble becouse iT requires Deodlocks 75 Deodlocks 7o CS 350 Part II Operating Systems Services Deadlock Prevention Generally deadlocks can be prevented by deny ing at least one of the conditions for deadlock Denying Mutual Exclusion Condition Depends on the particular resource involved Could be quite difficult and expensive But mutual ex clusion may be necessary for certain opera tions Denying Hold and Wait Condition Processes reqest all the required resources at once Re source allocation is done on an allornone ba sis Problems here include need for advance information on resource needs and resource underutilization Denying the No Preemtion Condition If a pro cess holding a certain resourse is denied fur ther resources the process must relinquish the already held resources Applicability depends on the type of resource Results in waste of re sources Could also lead to starvation Deadlocks 77 CS 350 Part II Operating Systems Services Denying Circular Wait Condition Order the resources numerically Request for resources are made in numerical order Eg If process A holds resurce Bi and process B holds resource R and fRj gt fRwhere f is an ordering function then process B cannot request for re source R To obtain R B must first relinquish Rj As the number of resources increase finding the appropriate ordering function could be come a problem We can see that each method for deadlock prevention has its own problems Deadlocks 78 CS 350 ParT ll OperaTihg SysTems Services Deadlock Recovery From The above problems iT may be good To sTill prepare for deadlock There are some meTh ods for deadlock recovery YeT non is parTicu larly aTTracTive Preemption Take away some resources from some processes and allocaTe Them To some oTher processes unTil The deadlock is broken There are some issues To consider here 0 Which VicTim how do we choose The process andor resources To preempT Deadlocks 79 CS 350 ParT ll OperaTihg SysTems Services o Rollback using process checkpoinTs For The process To be preempTed roll back To The checkpoinT jusT before The process acquired a resource in a deadlock If The process Tries To aquire The same resoure again iT musT waiT unTil iT becomes avail able STarvaTion how can we ensure ThaT The resources are noT always Ta ken away from The same process Termination kill one or more of The processes The processes chosen may or may noT be in volved in The deadlock Deadlocks 80 CS 350 ParT ll OperaTing SysTems Services CS 350 ParT ll OperaTing SysTems Services SingleThreaded process Process one execuTes The sTaTemenTs 245 246 and 247 in a loop Threads lTs Thread of execuTion can be represenTed by The sequence A process has an address space In iTs address 24512461724712451724612471245124612471 Sleeee O IOTOCeSS hes The eede H is exeCUTihg The subscrist idenTify The Thread of execuTion The TeXT and various pieces of daTa Process Two execuTes The sTaTemenTs 101 102 When a program execuTes The CPU uses The 103 104 I I I I process program counTer value To deTermine which insTrucTion from The address space To The CPU mighT exeCUTe ihSTrUCTiOhS ih The OT execuTe neXT def 245124617247124511012102210327104210527246172471H The resulTing sTream of insTrucTions is called The program39s Thread of execu onI ConTeXT swiTches occur beTween 2451 and 1012 and beTween 1052 and 2461 The processor sees The Threads of execuTion in Terleaved buT The processes see conTinuous sequences Threads 81 Threads 82 CS 350 ParT ll OperaTing SysTems Services MulTiThreaded process We can eXTend The process model To allow mulTiple Threads of execuTion wiThin a process The sequence of insTrucions execuTed in a pro cess wiTh Two Threads mighT be 5721 5731 5741 5751a 4121 4131 4141b Threads wiThin a process share everyThing open files variables memory eTc excepT The cur renT poinT of execuTion and The conTenTs of The regisTers Threads are someTimes called lighTweigthro cesses A Thread can belong To only one given pro cess Thus while processes can be creaTed by differenT users Threads belong To only one user Threads 83 CS 350 ParT ll OperaTing SysTems Services Why Threads Why use Threads if we can use fork To cre aTe a new process and use shared memory or some oTher form of IPC Speed The conTeXT swiTch beTween Two processes is expensive IT has To replace The conTeXT of The currenT process wiTh anoTher This includes 0 The sTack o RegisTers Program counTer ExecuTable code and memory used for variables Threads 84 CS 350 ParT ll OperaTing SysTems Services CS 350 ParT ll OperaTing SysTems Services SwiTching beTween Threads of a process only requires a change of The program counTer reg isTer Process sTaTe lO sTaTus User ID Process ID Any special priveledges Scheduling informaTion AccounTing informaTion Memory managemenT informaTion Heaps of oTher sTqu seT execuTion sTack anol sTaTe Threads More about threads On a mulTiprocessor machine Threads can run simulTaneously usually Parallelism can be acheived wiTh low overhead BuT They complicaTe programming All global variables are shared so synchronisa Tion can be a problem SysTem calls may or may noT be Threadsafe if The kernel is noT mulTiThreaded The Two basic Types of Threads are user level Threads and kernellevel Threads Threads 86 CS 350 ParT ll OperaTing SysTems Services User level threads Userlevel Threads are implemenTed in a library The kernel doesn T know abouT Them They are independenT of The kernel The Thread library adds some eXTra code To each sysTem call A wrapper or jackeT The eXTra code does Thread managemenT anol Takes care of sysTem calls ThaT mighT block such as read or sleep oTherwise The calls mighT block The whole process raTher Than jusT The Thread ThaT called Them Threads 87 CS 350 ParT ll OperaTing SysTems Services More on user level Threads AdvanTage Low overhead swiTching beTween Threads is quick Problems A greedy Thread ThaT does no sys Tem calls or library calls won T leT The Thread managemenT code schedule anoTher Thread The programmer may have To explicile yeild conTrol aT appropriaTe poinTs Can only share resources allocaTed To Their as sociaTed process This effecTively limiTs Threads To a single processor negaTing one of The prime moTivaTions To use Threads Threads 88 CS 350 ParT ll OperaTihg SysTems Services Kernel level threads Kernel is aware of all Threads Each Thread is separaTely schedulable Each Thread compeTes for resources on a sysTem wide basis Scheduling kernellevel Threads is almosT as ex pensive as processes buT kernellevel Threads can use mulTiple processors A kernellevel Thread Takes abouT seven Times longer To creaTe Than a userlevel Thread A fork Takes abouT 30 Times longer To creaTe Than a userlevel Thread Threads 89 CS 350 ParT ll OperaTihg SysTems Services Userkernel hybrid Threads Solaris uses a hybrid aproach To Threads The user wriTes The program in Terms of user level Threads buT specifies how many kernel schedulable enTiTies are associaTed wiTh The process The userlevel Threads are mapped To The kernel schedulable enTiTies as The process is running In Solaris 0 userlevel Thread is called a Thread Each is supporTed by a kernelschedulable en TiTy called a lighTweighT process LWP Each LWP is mapped To only one kernellevel Thread Threads 90 CS 350 ParT ll OperaTihg SysTems Services Using POSIX threads pthreadcreate creaTes a Thread To execuTe a specified funcTion pthreadexit causes The calling Thread To Ter mihaTe wiThouT The whole process TermihaTihg pthreadkill sends a signal To a specified Thread pthreadjoir1 causes The calling Thread To waiT for The specified Thread To eXiT This is similar To waitpid for processes pthreadself reTurhs The callers idehTiTy The Thread ID Threads 91


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.