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


by: Miss Willie Koch

ComputerSystemsII CSC2405

Miss Willie Koch
GPA 3.54


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

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 114 page Class Notes was uploaded by Miss Willie Koch on Wednesday October 28, 2015. The Class Notes belongs to CSC2405 at Villanova University taught by Damian-Iordache in Fall. Since its upload, it has received 14 views. For similar materials see /class/230573/csc2405-villanova-university in ComputerScienence at Villanova University.


Reviews for ComputerSystemsII


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: 10/28/15
Computer Systems Threads Process Address Space Revisited OS OS a Process with 13 Process With Single Thread Two Threads What are Threads Thread Independent stream of instructions I Basic unit of CPU utilization A thread contains A thread ID A register set including the Program Counter PC An execution stack A thread shares with its sibling threads I The code data and heap section Other 08 resources such as open files and signals Single and MultiThreaded Processes stack mead thread gt g Singlevlhreaded mullllhleaded MultiThreaded Processes 2 Each thread has a private stack But threads share the process address space There s no memory protection Threads could potentially write into each other s stack Why use Threads A specific example a Web server do get web page request from client check if page exists and client has permissions transmit web page backto client while1 If transmission takes very long time server is unable to answer other client s requests Solution do get web page request from client check if page exists and client has permissions create a thread to transmit web page back to client while1 Benefits of Threads Responsiveness Program continues even one part is blocked Resource Sharing Point to the same process memory and resources are shared Economy Memory allocation for process is costly Context switching for process is costly Utilization of Multiprocessor Architectures a Each thread is assigned one unique processor Threading Issues A badlybehaved thread can damage other threads Threads share the data of the master process 7 Threads have readwrite access to other threads memory Semantics of fork and exec system calls change 7 Duplicate all threads or only duplicate only one thread a Implementationdependent User and Kernel Threads KernelLevel Threads KLT lightweight processes 7 Directly supported by the OS 7 Thread is the basic scheduling entity 7 Thread management done by the kernel Examples Windows 9598NT2000 Solaris True64 Unix UserLevel Threads ULT Implemented as a thread library which contains the code for thread creation termination scheduling and switching Kernel is unaware of thread activity Examples Posix pthreads Solaris threads pthreads 54 Refers to the POSIX standard IEEE 10031c API for thread creation and synchronization Common in UNIX operating systems Java Threads 58 Java threads may be created by Extending Thread class Implementing the Runnable interface JVM manages Java threads Creation Execution Etc Principles of Concurrency Concurrent Threads Concurrent threads come into conflict with each other when they come to use shared resources Atomic actions are indivisible In hardware loads and stores are indivisible On a processor a thread switch can occur between any two atomic actions thus the atomic actions of concurrent threads may be interleaved in any possible order Result of concurrent execution should not depend on the order in which atomic instructions are interleaved 13 badcnt c An Incorrect Program J st 5 n mul 6936 t M Ama 34 mi K901293351 at linuxgt badcnt BOOM cnt198841183 linuxgt badcnt BOOM cnt198251801 cam 92th 3373 llnuxgt badcnt 39 BOOM cnt198259572 cnt should be equal to 200000000 What went wrong Vitae Wm iam mr any Critical Sections Critical sections are blocks of code that access shared data thread routine void countvoid arg for iO39 iltNITERS i The objective is to make critical sections behave as if they are atomic operations if one process uses a shared piece of data other processes can t access it The CriticalSection Problem A race occurs when the correctness ofthe program depends on one thread reaching point X before anotherthread reaches point y To prevent races concurrent processes must be synchronized General structure ofa process P While 1 Critical Section CS exit section Remainder Section RS Critical section problem design mechanisms that allow a single process to be in its critical section at one time Solving the CS Problem Semaphores 1 A semaphore is a synchronization tool provided by the operating system A semaphore S can be viewed as an integer variable that can be accessed through 2 atomic operations DOWNS also called waits UPS also called signalS Atomic means indivisible When a process has to wait put it in a queue of blocked processes waiting on the semaphore Semaphores 2 In fact a semaphore is a structure struct Semaphore int count Process queue blocked processes struct Semaphore S s count must be initialized to a nonnegative value depending on application OS Semaphores DOWNS or waitS When a process must wait for a semaphore 8 it is blocked and put on the semaphore s queue semiquot S DOWNS Ali ltdisab1e interruptsgt S count if i W place this process in Squeue ltenab1e interruptsgt Processes waiting on a semaphore S m OS Semaphores UPS or signaS The UP or signal operation removes one process from the queue and puts it in the list of ready processes UPS pi ltdisab1e interruptsgt scount if Scount How L muss Lemme W place this process P on Ready list ltenab1e interruptsgt OS Semaphores Observations VVhen Scount gt 0 the number of processes that can execute waits without being blocked is equal to Scount VVhen Scount lt 0 the number of processes waiting on S is equal to IScount Atomicity and mutual exclusion no 2 process can be in waitS and signal s on the same 5 at the same time hence the blocks of code defining waitS and signal s are in fact critical sections Using Semaphores to Solve CS Problems Process Pi ltcritical section CSgt UEJS ltremaining section RSgt To allow only one recess in the CS mutual exclusion a initializels count to 1 E What should be the value of s to allow k processes in the CS initialize S count to k Using 08 Semaphores Semaphores have two uses Mutual exclusion making sure that only one process is in a critical section at one time Synchronization making sure thatT l completes execution before T2 starts Using Semaphores to Synchronize Processes Suppose that we have 2 processes P1 and P2 How can we ensure that a statement S1 in P1 executes before statement S2 in P2 Semaphore sync El 51 DOWNsync Process P0 Process P1 UPsync 2 Exercise Consider two concurrent threads T1 and T2 T1 executes statements 81 and S3 and T2 executes state mu 1 215 52 53 T1 HE T2 bowuumi 52 UPs m 7L M g z is o bawutm 39l Use semaphores to ensure that 81 always gets executed before 82 and 82 always gets executed before 83 Review Mutual Exclusion Semaphore mu tex 1 DOWN mutex critical section UP mutex DOWN mutex critical section UP mutex Review Synchronization P2 cannot begin execution until P1 has finished Semaphore mu tex E Code for P1 UP mutex DOWN mutex Code for P2 Concurrency Control Problems Critical Section mutual exclusion only one process can be in its CS at a time Deadlock each process in a set of processes is holding a resource and waiting to acquire a resource held by another process Starvation a process is repeatedly denied access to some resource protected by mutual exclusion even though the resource periodically becomes available Classical Synchronization Problem The ProducerConsumer Problem The Producer Consumer Problem Common synchronization pattern Producer waits for slot inserts item in buffer and signals consumer Consumerwaits for item removes it from buffer and signals producer Examples Multimedia processing Producer creates MPEG video frames consumer renders the frames Eventdriven graphical user interfaces Producer detects mouse clicks mouse movements and keyboard hits and inserts corresponding events in buffer Consumer retrieves events from buffer and paints the display 30 Example Buffer that holds one item 1 Eicli W5 7 Example Buffer that holds one item 2 Initially empty 1 full 0 General Buffer that holds multiple items A circular buffer buf holds items that are produced and eventually consumed buf 0 lilll Iran IE4 I 1 out in 4 me e twin w General Buffer that holds multiple items Initially empty MAX full 0 General Buffer that holds multiple items B mun19 Atomic Operations The statement in gtmaChme R in level RR1 must be performed atomically in is shared An atomic operation is an operation that completes in its entirety without interruption Race Conditions One possible interleaving of statements is R1 in R1 R1 1 Race condition lttimer interrupt gt The situation where several R2 in processes access shared data R2 R2 1 concurrently The nal value of in R2 the shared data may vary from lttimer interrupt gt one execution to the next inR1 Then in ends up incremented once only Threads ovenNrite each other s data Reentrant Functions A function is reentrant iff it accesses NO shared variables when called from multiple threads Reentrant functions are a proper subset ofthe set of threadsafe functions All functions 39d 39 39f Threadunsafe functions Reentrant I functions 39 Tread carefully with threads CAPTCHA Completely Automated Public Turing test to tell Computers and Humans Apart The Problem A mechanism of preventing automated systems from infiltrating human systems These automatic scripts and programs are known as bots and everyone here since the proxy project now has the skill to Write these b OS The information is trivial to an advanced computer programmer The Motivation In 1997 Alta Vista did not use a bot instead relying on user submitted URLs Bots did the work anyway and when Alta Vista added a very primitive CAPTCHA submissions dropped by 95 In 1999 Slashdot ran a poll asking what school was the best for Computer Science ors Carnegie Mellon students wrote a script MIT students retaliated At the end each school had 20000 votes other schools had only 3 digit scores Slashdot still has open voting because they39re simply fun polls Few people have motivation to rock the vote there Time39s people of the year The Approach The very first of the CAPTCHAs were D J E N srmp e By rendering the text in the image the bots were unable to read them This was broken pretty quick so extra graphics were introduced into the image It turned out to be simple fast and effective Only the most advanced bow could pass through this detection and it took them a while to do so The History Developed by CMU in 2000 by studenm and professors Trademark and patent applications were dropped in April 2008 The particular technology of CAPTCHA is no longer in use these days a system called reCAPTCHA is in place However the generic term CAPTCHA is still applied Version counting is extremely hard mostly because version numbers were never kept Many changes were simply modification to variables that control obscuring Some were modifications to the original some were total rewrites that merged back into the development tree Often they were developed by third parties The extreme variety helped ensure security however within a particular site only a single style was used More History reCAPTCHA is the currently recommended technology The new technology is run on Twitter Facebook and TicketMaster It hosm 30 million images per day Authorization is handled offsite with the reCAPTCHA program and is used for more than simple botcontrol The Assumptions The underlying assumptions are pretty clear The developer assumes that the bots cannot decode the images as easily as cleartexg and must return a cleartext The stated mission on recaptchacom is to keep the technology a few generations ahead of the bot writers They know that the enemy will always given enough time defeat their mechanisms and must escalate l quotI rquot r Also some technologies rely on the fact L X Ll that the human mind can extrapolate information while the machiens cannot by eliminating some information and adding extra The Strengths The more advanced the Brute force password breaks and protection the harder it dictionary attacks trigger lockoum of an CAP is to write the bow account CHAS Prevent a malicious script from locking people out More technical of accounm at wi knOWIedge is required To COMPLETE Y0 R WEB REGISTRATION PLEASE PROVE U and more overhead Tm WWE HUMAN required for eaCh WHEN LTl39LEFOOT5 M0 HER DIED N NE OKGNAL 39 39 39 T I I I attempted infiltration LAND BEFORE ME DID You FEEL SAD Upgraded technology C 3509 is not a major change for the average user It 50751 N0 LYING may even be seamless Recycled Manpower The current technology of reCAPTCHA solves two problems at once user proofof39 T39 39 n 39 39 391 of digitized books Technology used to break the original CAPTCHAs are used currently in the digitizing of existing print books Each scan passes through a series of decipher tools and when disagreemenm or ambiguities are discovered they are converted to a CAPTCHA and passed to a user When a sufficient number of humans have reach a concesious the word is considered solved and used a bias for future deciphering The Weaknesses Takes more time for the user Once defeated a new technology needs to be rolled out Nonenglish keyboards may have a problem People who don39t read the Latin alphabet may have issues translating the characters If the custom authorization requires a database like with reCAPTCHA SQL Injection could occur reCAPTCHA itself if properly controlled but this requires more overhead for reCAPTCHA Bandwidth problems Cached images The Tactics An early GIMP CAPTCHA after basic systems had been cracket in an attempt to S 1 2 E distOIt the letters An attempt to make segmentation difficult MOSH11g mg by running a line through them Heavy waIping hides the characters and slh makes differentiation more difficult h The Future Graphic recognition of rotated 3D objects 7 An archive of objects is stored and M 1 J rendered as needed K3 Animation The movies are revolutionary Animals I Pick the kittens Extended Projects MailHide the organization reponsible for developing reCAPTCHA is developing MailHide in an effort to hide email addresses from harvesters Book Scanning The so ware used to crack captchas has been accessable to the general public lately and taken by the same people who attempt to scan books and newspapers into digital records Tandem operation The strongest forms one could implement are hybridizations using multi fonts in a single image to confuse bots character obstruction extra information and missing characters Two CAPTCHAs in the same page allow for two completely different rendering systems at once By have four or five that the site can rotate through it can confuse how even more However this is twice as annoying Lots can go wrong mu m pr mman please fa mgmal allenge Awful schemes Probably should never use anything with variables 5mm rmiy Your Rggmrawn My mum wva enter the characters fur me symnuls snuwn in the box halow Too slow Too obscured Please entenhe code you see below Too vague r The Conclusion CAPTCHA technology is not here to stay The technology is also used to slow SQL injection attacks bom attempting to discover vulnerabilities are inhibited by the CAPTCHA Extra overhead required to run bots requires bot operators to have more hardware at their disposal in order to perform even basic tasks Image authorization must be ensured completely indepentently and securely Credim httpwww inhnmwilli http imlzn hlno pnt onm 700712 1 1quot A 1 Managing the Implementation of C Projects Goals for Today s Class Compiling multiple files modules Scope and extent of variables in C global static Using the preprocessor Multiple Files Why multiple files Modularity Execution of a program begins in the main function The main function can call other functions Functions de ned in the same le Function defined in other les or libraries A module is a collection of related functions Review Function Prototypes Header Files Function Prototypes Declarations Informs compiler about a function39s return type name and parameters Used to check whether function is called correctly Should be placed before main or before first function is defined Example of Function Prototype int doNothingint y int mainvoid printfquotdquot doNothing10 int doNothingint y return y Header Files Typically contain Function prototypes forthe module Constants de ne Structures and external variables Not mandatory but useful for information hiding Users of module should only need to examine header le Avoids code duplication collects declarations together makes changes easy Example of a Header File ifndef THISH define THISH typedef struct const char name int num data void startvoid void reportconst charint endif THISH Using Conditionals in Header Files Example ifndef SOMEH define SOMEH Insert header file info endif Prevents multiple inclusions of header files which causes compilation problems Things to Know A C program can have only one main module or file with its main function Reference function prototypes for submodules using include quotsubModuleh 39 include is a preprocessor command to import text from another file Example ifndef CALCH define CALCH include quot calc hquot Xiildgb int squareint x int squareint x return xx endif CALCH include ltstdiohgt include quotcalchquot int main int x 5 printfquotnSquare of d is return 0 dnquot x squarex More on include include ltsomehgt searches the system include path ie the directory or directories where stdioh stringh etc are located for someh include quotsomehquot searches current directory dir in the compile command appends dir to list of directories searched for header files and libraries for both quot quot and lt gt Files hcoexe com ilesto mainMeuIe39 p contains prototypes for Incremental Compilation Run gcc c on submodules to generate object files Run gcc mainModuIeo subModuleo to build final executable Advantages of using Modules Modules can be written and tested separately Large projects can be developed in parallel Reduces length of program making it more readable Promotes the concept of abstraction Scope and Extent Execution Model for C Stack pointer SP Activation Record AR for a function PC Program Counter points to execution code Scope and Extent Scope the range of visibility of a variable Extent the length of time a variable stays in memory Note a variable can be out of scope and still be in memory Example int x 0 void aFunctionvoid int mainvoid int y 1 Scope and extent ofy in main void aFunctionvoid static int y 0 int 2 5 Scope and extent of z in aFunction Memory Diagram z stored here y in main stored here y in aFunction stored here X stored here Global Variables in C Any variable defined outside a function Also called an external variable Scope From point of definition to the end ofthe source file apart from name clash Extent From beginning to the end ofthe program To see a global in a different file extern int x BUT 10 Declaration vs Definition Declaration stating that the name exists Definition allocating memory to the variable Example int x Declaration and definition extern int x Declaration only Example ifndef PRINTH include print hquot define PRINTH int value 10 extern int value void printValue void printValue printf d value endif PRINT include ltstdiohgt ii ifi e je include printh int main printValue return 0 ll Global Variables vs Modularity Avoid globals if possible Globals violate modular independence A global can be modi ed from any external le Static Variables Declared in a function Scope The function Extent From the rst call to the function to the end of the program Example static int x Static globals Declared outside functions Scope Only in le where it is de ned Extent Beginning to end of program 12 Example int mainvoid int i fori 0 i lt 5 i Printfquotdnquot Increment int Increment static int x 0 1 x re urn x 4 5 25 Memory Diagrams First call to increment First call to X AR for increment AR for increment AR for main AR for main Static storage Static storage l3 Memory Diagrams After return from increment i E AR for main Static storage Statiefstora39ge is still maintained While AR for increment isigpne Using the PreProcessor Preprocessing define include Conditionals if else elif endif 39 Example define DEBUG 1 if DEBUG initDebug else initNormal endif l4 Computer Systems Topics I lObound vs CPUbound Processes I Scheduling Algorithms The Context One CPU multiple processes Processes can be in one ofthe following states w How does the OS keep track of process states I OS maintains a queue of processes ready to run I OS maintains queues of processes waiting for an event one queue per event Page 1 OS Queuing Model Enter Ready queue Network Queue Semaphore Q Processes enter and leave the system Exit CPU Scheduling Question Any process in the pool of ready processes is ready to run Which one to pick to run next CPU scheduling I Selecting a new process to run from among the pool of Ready processes competing for the CPU I Basis of multiprogrammed OS Preemptive scheduling I running process may be interrupted and moved to Ready queue Nonpreemptive scheduling I once a process is in Running state it continues to execute until it terminates or blocks for O or system service Page 2 When Does a Scheduler Take Decisions 1 Running Waiting 2 Running Done 3 Waiting Ready 4 Running Ready Scheduling under 1 and 4 I nonpreemptive scheduling Scheduling under 2 and 3 I premeptive scheduling What Are We Trying to Optimize Systemoriented metrics I CPU utilization percentage oftime the processor is busy I Throughput number of processes completed per unit of time Useroriented metrics I Turnaround time interval oftime between submission and termination including any waiting time Appropriate for background jobs I Response time39 for interactive jobs time from the submission of a request until the response begins to be received I Waiting time sum of the periods spent in the Ready queue Page 3 Scheduling Criteria Maximize I CPU utilization I Throughput Minimize I Turnaround time I Wailingtime I Response time Problem mutually exclusive objectives I No one best way I Wailing response time vs throughput con icts Alternating CPU and HG Bursts lmui mm cPu must mm store and ham le lyo M m m l I in mm Add Store lead quotout lile m mm he must Page 4 Process Behavior Observed property of processes I alternate between CPU execution and lO wait CPUbound job little lO long CPU bursts I Matrix multiplication I lObound job lots of lO short CPU bursts l l l pico l l l l Problem don t know the bound type before running An underlying assumption I response time most important for lO bound processes Scheduling Algorithms Next we take a look at four scheduling algorithms and their amusing behavior 1 First Come First Served FCFS 2 Round Robin RR 3 Shortest Job First SJF 4 Priority Scheduling Scheduling very ad hoc Try and See 10 Page 5 First Come First Served FCFS or FIFO Simplest scheduling algorithm I Run jobs in order that they arrive I Uniprogramming run until done nonpreemptive I Multiprogramming put job at back ofqueue when blocks on lO we ll assume this Advantage simple Disadvantages 11 FCFS Scheduling Example 1 Example Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes get created in the order P1 F 2 P3 The chart for the schedule is p1 lpzlpal l l l l o 24 27 30 Waiting time for P1 0 P2 24 P3 27 Average waiting time 0 24 273 17 Average turnaround time 2427303 27 12 Page 6 FCFS Scheduling Example 2 Suppose that the processes arrive in the order P2 P3 P1 The chart for the schedule is lF le al P1 o 3 6 30 Waiting time for P1 6 P2 0133 3 Average waiting time 6 0 33 3 Average turnaround time 30363 13 Much better than previous case 13 FCFS Disadvantages Performance depends on arrival time of processes Convoy effect short process behind long process Example one CPU bound process many lO bound I CPU bound runs lO devices idle I CPU bound blocks I O bound processes run quickly block on O I CPU bound runs again I O completes I CPU bound still runs while O devices idle continues Result I long periods where no O requests issued and CPU held I poor O device utilization 14 Page 7 Round Robin RR Solution to job monopolizing CPU Interrupt it I Run process for some time quantum time slice I When time is up or process blocks move it to the back ofthe ready queue I Most systems do some flavor of this Advantages I Fair allocation of CPU acrossjobs I Low average waiting time when job lengths vary I Assume 3 processes P1100 P22 P31 and time quantum 1 1 2 3 4 5 103 CPUPlFgt2 PJ P1 P2 P1 I What is the average waiting time and completion time 15 RR Example Time Quantum 20 Process Burst Time P1 53 P2 17 P3 68 P4 24 Thechartis p1 pz 33 p4 F1 F1 PG PA PS P3 0 20 37 57 77 97 117 121 134 154162 Average waiting time 2 Average completion time 2 16 Page 8 Round Robin s BIG Disadvantage Varying sized jobs are good but what about samesized jobs Assume 2 processes of time about 100 units each 199 200 12345 I What is the average waiting time I What is the average completion time I How does it compare to FCFS for the same two processes Main interesting thing is the length of the time slice 17 RR Time Slice Tradeoffs 1 Performance depends on the length ofthe timeslice men mom a mes um m Quumum Context switching is not a 39ee operation I If 39 39 39g attempting W switch cost you get FCFS that is processes will nish or block before their slice is up anyway I If it is set too low all time is spent doing context switching between processes 45 Page 9 RR Time Slice Tradeoffs 2 Timeslice frequently set to 100 milliseconds Context switches typically cost lt 1 millisecond I context switching is usually negligible lt 1 per timeslice in above example unless you context switch too frequently and lose all productivity 19 ShortestJobFirst SJF Associate with each process the length of its next CPU burst Use these lengths to schedule the process with the shortest time Nonpreemptive I Once CPU given to the process it cannot be preempted until completes its CPU burst Preemptive I If a new process arrives with CPU burst length less than remaining time of current executing process preempt This scheme is know as the ShortestRemainingTimeFirst SRTF 20 Page 10 Example of NonPreemptive SJF 1 3 processes P1100 P22 P31 1 3 103 CPU P3 P2 P1 I Average completion 13103 3 35 vs 101 for FCFS Provably optimal I Moving shorter process before longer process improves waiting time of short process more than harms waiting time for long process 21 Example of NonPreemptive SJF 2 Process Arrival Time Burst Time P1 0 7 P2 2 4 P3 4 1 P4 5 4 STOP nonpreemptive P1 P3 P2 I PA I l l l l l l l l l l l l I l l l l l l I I l l l I l l l I 0 3 7 8 12 16 Average waiting time 0 6 3 74 4 Average completion time 2 22 Page 11 Example of Preemptive SJF Process Arrival Time Burst Time P1 0 P2 2 4 P3 4 1 P4 5 4 STCF preemptive I P1 P2 P3 P2 I PA I P1 I l l l l l l l l l I l I l I I I I l l l I l l l l I 0 2 4 5 7 11 16 Average waiting time 9 1 0 24 3 Average completion time 2 23 STCF is Optimal but Unfair Gives minimum average waiting time Longrunning jobs may starve iftoo many short jobs Difficult to implement I how do you know how long a process takes 2 Option1 I have the user tell us ifthey lie kill the process I not so useful in practice Option 2 I use the past to predict the future 24 Page 12 Use the Past to Predict the Future Use the past to predict the future 1 I Long running job will probably take a long time more I gcc sample Use the past to predict the future 2 I View job as sequence of alternating CPU and lO jobs I If previous CPU pieces in the sequence have run quickly future pico I I ones will too usually 25 Use the Past to Predict the Future Example Predict length of current CPU burst using length of previous burst I Record length of previous burst 0 when just created I At scheduling event unblock block exit pick the smallest past run length off of Ready queue n In a Elfk ill 100ms awn Pick a In a ma 39139 12ms P39k ls In IE rm 39f I 26 Page 13 Approximate STCF Exp Average STCF exponential averaging 1 2 actual length of IV CPU burst 2 21predicted value for the next CPU burst 3 060 0431 4 Define 1W at 1 a 1quot 0c 0 39 Tn1 In I Recent history does not count at 1 39 Tn1 tn I Only the actual last CPU burst counts 27 Exponential Average 2 Tn1 2061 quot 40 06 lfwe expand the formula we get tn10ctn1 ococtn11 oczoctnz 1 ocjoctnj 1 oc quot110 Since both at and 1 0c are less than or equal to 1 each successive term has less weight than its predecessor recent past counts more 28 Page 14 Priority Scheduling SJF SRTF are special cases of a more general priority scheduling algorithm Each process has a priority I Run highest priority ready process in system I Round robin among processes of equal priority I Convention small integer high priority Most systems use some variant of this Common use couple priority to process characteristic I Fight starvation Increase priority of processes waiting in the system for a long time I Keep O busy Increase priority of processes that often block on O Multilevel Queue Ready queue is partitioned into separate queues Each queue has its own scheduling algorithm highesl morin Example 2 3 is lawasl plmvily Page 15 Multilevel Feedback Queue Allows a process to move between the various queues Look at STCF I Faster for a longer time slice I So grow the time slice for a CPU bound process but decrease its priority to prevent starvation of others Idea Separate processes with different CPU bursts Multilevel Feedback Queue Ex 1 Process created I Give high priority and short time slice If process uses up the time slice without blocking I priority priority 1 lower its priority I timesice timesice 2 Three queues Q0 time quantum 8 ms Q1 time quantum 16 ms Q2 FCFS Page 16 Multilevel Feedback Queue Ex 2 Three queues Q0 8 ms Q1 16 ms Q2 FCFS Schedang I A new process enters queue Q0 which is served FCFS When it gains CPU the process receives 8 milliseconds If it does not finish in 8 milliseconds the process is moved to queue Q I A Q1 process is again served FCFS and receives 16 additional milliseconds If it still does not complete it is preempted and moved to queue Q2 I A Q2 process is served FCFS Attacks both ef ciency and response time problems I Efficiency long time quanta low switching overhead I Response time quickly run after becoming unblocked 33 Some problems A user can insert lO just to keep priority high Can t low priority processes starve I ad hoc when skipped over increase priority What about when past doesn t predict future I For instance a CPU bound process switches to O bound I want past predictions to age and count less towards current view of the w r Windows 2000 I 32 priority levels I If a running process receives an interrupt priority is lowered I If a process unblocks from a waiting queue priority increases 34 Page 17 Multilevel Feedback Queue Scheduler de ned by the following parameters I number of queues I scheduling algorithms for each queue I method used to determine when to upgrade a process I method used to determine when to demote a process I method used to determine which queue a process will enter when that process needs service 35 Traditional UNIX scheduling 1 Uses multilevel feedback queues 128 priorities possible 0127 1 Round Robin queue per priority Every scheduling event the scheduler I picks the nonempty queue of highest priority I runs proceses in roundrobin Scheduling events I Clock interrupt I Process does a system call I Process gives up CPUeg to do O 36 Page 18 Traditional UNIX Scheduling 2 All processes assigned a baseline priority based on the type and current execution status I swapper 0 I waiting for disk 20 I waiting for lock 35 I usermode execution 50 At scheduling events priorities are adjusted based on the amount ofCPU used the current load and how long the process has been waiting Most processes are not running so lots of computing shortcuts are used when computing new priorities 37 Linux Lottery Scheduling Problem this whole priority thing is really adhoc I how to ensure that jobs will be equally penalized under load Lottery scheduling I give each process some number of tickets I at each scheduling event randomly pick a ticket I run winning process I to give a process n of CPU give it totatickets n How to use I approximate priority low priority give few tickets high priority give many I approximates STCF give short processes more tickets long jobs fewer lfjob has at least 1 won t starve Linux uses lottery scheduling 38 Page 19 Summary FIFO simple short jobs can get stuck behind long ones poor lO RR better for short jobs poor when jobs are the same length SJF optimal hard to predict the future unfair to long running jobs Multilevel queues Priority RR approximate STCF still unfair to long running jobs 39 Page 20 James Farwell 40809 System Security Topic There are many types of security threats a person has to worry about Viruses hackers phishing are common But one type of virus plagues millions of people each year and the sad thing is they do not even realize they have it Adware spyware and malware are some of the most commonly reported problems that America has without them even knowing they have it I plan to investigate what each of them are how they differ and what similarities they have in common I also want to look into how they get on to your system and the most effective way to remove them and clean your system Right before Christmas break Villanova University s UNIT team sent us a mass email claiming that many computers has been infected by malware They also sent a link to a malware removal tool called Malwarebytes lam not the perfect person and I do get malware spyware and every other lware you can think of I tried running this program and it worked miraculously It worked so well that I even recommended it to a friend of mine who was having similar problems It worked for her too so I figured this program must be doing something right I want to investigate to the best of my ability how these programs work and what they do to scan and quarantine this vicious annoying inconvenience I intend to do my report as a research paper I cannot remember how long it has to be but either way I have full confidence that this topic has a lot to write about Topks I Unix NO I Robust reading and writing I Sharing files I No redirection I Standard No A FYWQQIIJ Hardware 39 CPU chip register le ALU system bus memory bus I quot0 bus Expansion slots for other devices such USB graphics disk as network adapters controller adapter controller mouse keyboard monitor Page1 Reading a Equot CPU chip CPU initiates a disk read by writing a command logical block number and destination memory address to a port address associated with disk controller register le ALU b I t f 39 main us In er ace memory IIO bus lt1 41 gt USB graphics controller adapter controller mouse keyboard monitor W t reading a CPU chip Disk controller reads the sector and performs a direct memory access DMA transfer into main memory register le ALU b t f A b main us er ace W memory F IIO bus gt di k cont oller USB controller graphics adapter 1 l l mousekeyboard monitor i W Page 2 When the DMA transfer completes the disk controller notifies the CPU with an interrupt ie asserts a special interrupt pin on the CPU CPU chip register le ALU IIO bus lib disk controller controller m a m 399 m a mouse keyboard monitor A Unix le is a sequence of m bytes Bquot B1 Bk BM All IIO devices are represented as files I devsda2 usr disk partition I devtty2 terminal Even the kernel is represented as a file I devkmem kernel memoryimage I proc kernel data structures Page 3 Fillies Regular file I Binary or text file I Unix does not know the difference Directory file I A file that contains the names and locations of other files Character special and block special files I Terminals character special and disks block special FIFO named pipe I A file type used for interprocess comunication Socket I A file type used for network communication between processes The elegant mapping of files to devices allows kernel to export simple interface called Unix lO Key Unix idea All input and output is handled in a consistent and uniform way Basic Unix lO operations system calls I Opening and closing files 0 open and close I Changing the current le position seek o lseek not discussed I Reading and writing a file 0 read and write Page 4 Opening Files Opening a file informs the kernel that you are getting ready to access that file ME Eek Name quot W 35 came imamng gamrb or g mrmem P realism a ll Returns a small identifying integer le descriptor I fd 1 indicates that an error occurred Each process created by a Unix shell begins life with three open files associated with a terminal I 0 standard input I 1 standard output 9 I 2 standard error Closing Files Closing a file informs the kernel that you are finished accessing that file gm mgaitg Magma fa ltlt 493 nm atfe se warm I Closing an already closed file is a recipe for disaster in threaded programs more on this later Moral Always check return codes even for seemingly benign functions such as close 10 Page 5 Reading Fiies Reading a file copies bytes from the current file position to memory and then updates file position be 39 3911 W Ewe mews 91 7quot amigo Et eee W ale 735 43 Miami Returns number of bytes read from file fd into buf I nbytes lt 0 indicates that an error occurred I short counts nbytes lt sizeofbuf are possible and are not errors 11 Writing Fites Writing a le copies bytes from memory to the current file a u Jw sale werqu J m manager r2 wri re I nes so fa n E FM Jab113 Cw I 5933 time we vat7 Farm x Returns number of bytes written from buf to file fd I nbytes lt 0 indicates that an error occurred I As with reads short counts are possible and are not errors Transfers up to 512 bytes from address buf to file fd 12 Page 6 Q Copying standard input to standard output one byte at a time ihclude quotts39a39p mquot iht ma in Zoi d that b awhuejae aaSTDINJiIzLENOJ ampc l 0 Wm te39STDOUTF I IENO 54 1 iexi t o Note the use of error handling wrappers for read and write Appendix B 13 P eke e RIO is a set of wrappers that provide efficient and robust NO in applications such as network programs that are subject to short RIO provides two different kinds of functions I Unbuffered input and output of binary data 0 rioreadn and riowri ten l Buffered input of binary data and text lines 0 rioreadlineb and rioreadnb o Cleans up some problems with Stevens s readline and readn functions 0 Unlike the Stevens routines the buffered RIO routines are threadsafe and can be interleaved arbitrarily on the same descriptor Download from csapp cs cmu edupublicicscodesrccsapp c csapp cs cmu edupublicicscodeincludecsapp h 14 Page 7 Unbuttered RIJO Input and Output Same interface as Unix read and write Especially useful for transferring data on network sockets include csapph ssizet rioreadnint fd void usrbuf sizet n ssizet riowritennt fd void usrbuf sizet n Return num bytes transferred if OK 0 on EOF rioreadn only 1 on error I rioreadn returns short count only if it encounters EOF I riowriten never returns a short count I Calls to rioreadn and riowriten can be interleaved arbitrarily on the same descriptor 15 implementation of riQEmdn Page 8 Buffered Rio input Functions Efficiently read text lines and binary data from a file partially cached in an internal memory buffer include csapph void rioreadinitbriot rp int fd ssizet rioreadlinebriot rp void usrbuf sizet maxlen ssizet rioreadnbriot rp void usrbuf sizet n Return num bytes read if OK 0 on EOF 1 on error I rioreadlineb reads a text line of up to maxlen bytes from file Ed and stores the line in usrbuf 0 Especially useful for reading text lines from network sockets I rioreadnb reads up to 1 bytes from file fd Calls to rio readlineb and rio readnb can be interleaved arbitrarily othhe same descriptor 0 Warning Don t interleave with calls to rioreadn 17 Rio Example Copying the lines of a text file from standard input to standard output re Hm auger Mam w msmm almane iw mm mm 926 18 Page 9 Two descriptors referencing two distinct open disk files Descriptor 1 stdout points to terminal and descriptor 4 points to open disk file Descriptor tame Open le table ode table one tame per process shared by all processes shared by all processes File A terminal stdin fd 0 File access 22 3 gggquot rd 3 refcnt1 File type strum fd4 5 ie B disk File access File pus File sIze refcnt1 F39le type 19 e Shamquot Two distinct descriptors sharing the same disk file through two distinct open file table entries I Eg Calling open twice with the same filename argument Descriptor table Open file table vnode table one table shared by per process all processes all processes File A fd 0 fd1 fd 2 FIle pos rd 3 refcnt1 fd4 39 File B File pos refcnt1 20 39 Page 10 S are A child process inherits its parent s open files Here is the situation immediately after a fork Descriptor Open le table vnode table tables shared by shared by all processes all processes Parent39stable File A fd 0 File access h File P05 File size m2 I W 3 refcnt2 FIle type m4 T Child39s table File B I FIle access 3 M fd 3 refcnt2 le type m4 21 MQ Redirection Question How does a shell implement lO redirection unixgt 15 gt footxt Answer By calling the dup2 oldfd newfd function I Copies perprocess descriptor table entry oldfd to entry newfd Descriptor table Descriptor table before dup2 4 1 after dup2 4 1 m m m 39gt m 22 Page 11 on Ex IMO edlijre 39 imple Before calling dup2 4 1 stdout descriptor 1 points to a terminal and descriptor 4 points to an open disk file Descriptor table Open file table vnode table one table shared by shared by per process all processes all processes File A stdin fd 0 File access stdout rd1 f stdeu rd 2 Flu pus FIle size M 3 refcnt1 File type fd4 5 Flle B File access Fquote pus File size refcnt1 M 23 Red After calling dup2 4 1 stdout is now redirected to the disk file pointed at by descriptor 4 traction mm lie Descriptor table Open le table vnode table able shared by shared by per process all processes all processes gt FIle access 24 Page 12 Standard IMQ J The C standard library libc 3 contains a collection of higherlevel standard lO functions I Documented in Appendix B of KampR Examples of standard lO functions I Opening and closing files fopen and fclose I Reading and writing bytes fread and fwrite I Reading and writing text lines fgets and fputs I Formatted reading and writing fscanf and fprintf 25 Standard M0 Strea Standard lO models open files as streams I Abstraction for a file descriptor and a buffer in memory C programs begin life with three open streams defined in stdio h I stdin standard input I stdout standard output I stderr standard error 26 Page 13 dial 39d Standard IIO functions use buffered IIO fter rig in printf h printf e printf l printf l printf o buf printf n on fflushstdout writel buf 6 6 27 Standard Standard IIO and RIO are implemented using lowlevel Unix lO vs fopen fdopen fread fwrite fscanf fprintf C application program rio readn Standard IIO Rio r w t quot H t r10 readlnltb functions functions r10readllneb V uHct iu nr rioreadnb systemic ac39c39essed Which ones should you use in your programs 28 Page 14 ms and Cons of Unix MQ Pros I Unix NO is the most general and lowest overhead form of IIO o All other IIO packages are implemented using Unix IIO functions Cons I Dealing with short counts is tricky and error prone I Efficient reading of text lines requires some form of buffering also tricky and error prone I Both of these issues are addressed by the standard HO and RIO packages 29 Pros and Cons of Standard m Pros I Buffering increases efficiency by decreasing the number of read and write system calls I Short counts are handled automatically Cons I Standard NO is not appropriate for input and output on network sockets I There are poorly documented restrictions on streams that interact badly with restrictions on sockets 30 Page15 ms and of dam IMO learnt Restrictions on streams I Restriction 1 input function cannot follow output function without intervening call to fflush fseek fsetpos or rewind o Latter three functions all use lseek to change file position I Restriction 2 output function cannot follow an input function with intervening call to fseek fsetpos or rewind Restriction on sockets I You are not allowed to change the file position of a socket 31 Bras and of nldjardl llQ cont Workaround for restriction 1 I Flush stream after every output Workaround for restriction 2 I Open two streams on the same descriptor one for reading and one for writing I However this requires you to close the same descriptor ice 32 I Creates a deadly race in concurrent threaded programs Page 16 Chaosii 3 Function 91 I General rule Use the highestlevel lO functions you can I Many C programmers are able to do all of their work using the standard IIO functions When to use standard NO I When working with disk or terminal files When to use raw Unix lO I In rare cases when you need absolute highest performance When to use RIO I When you are reading and writing network sockets or pipes I Never use standard IIO or raw Unix IIO on sockets or pipes 33 For Ful llear Information The Unix Bible I W Richard Stevens Advanced Programming in the Unix Environment Addison Wesley 1993 I Somewhat dated but still useful Stevens is arguably the best technical writer ever I Produced authoritative works in 0 Unix programming 0 TCPIIP the protocol that makes the Internet work 0 Unix network programming 0 Unix IPC programming Tragically Stevens died Sept 1 1999 34 Page 17 Signals Topbs I Unix Process Control I Sending Signals I Receiving Signals I Blocking Signals Two Fundamental Questions Q1 How does the OS communicate to an application process Q2 How does an application process communicate to the OS Page1 Unix Process Control i command i command amp T Ctrlc T kill isIGINT pid Qunning Eo regrou 1390 Rbnnlng n I r l PK0 Q S 39 0 1 Process T kill l Cttflz SIG Red T g Eg arckgroiurid P rooess T g Unix Process Control Demo of unix process control on tanner Page 2 Exactly what happens when you Type Ctrlc I Keyboard sends hardware interrupt I Hardware interrupt is handled by OS I OS sends a 2SIGINT signal Type Ctrlz I Keyboard sends hardware interrupt I Hardware interrupt is handled by OS I OS sends a 20SIGTSTP signal Issue a kill sig pidquot command I OS sends a sig signal to the process whose id is pid Issue a fg or bg command I OS sends a 18SIGCONT signal Signals A signal is a software interrupt delivered to a process I Reports that an event of some type has occurred I Sent from the kernel sometimes at the request of another process to a process I Different signals are identified by small integer ID s I The only information in a signal is its ID Page 3 Signal Concepts 1 g man WI Sending a Signal 539 I Kernel sends delivers a signal to a destination process by updating some state in the context of the destination process in l stquot I Kernel sends a signal for one ofthe following reasons iii1397 o Kernel has detected a system event such as divideb zero xJ Sie orthe termination of a child process SI 0 Another process has invoked the kill system call to explicitly request the kernel to send a signal to the destination process Signal Concepts 2 Receiving a signal I A destination process receives a signal when it is forced by the kernel to react in some way to the delivery of the signal I Three possible ways to react 2 L m quot3 1 o Ignore the signal do nothing 5 l o Terminate the process 5 o thh the signal by executing a userlevel function called a signal handler Eleom k J in new Ll 39 5 ml Sloiu39l39 1616 bd ii1 lal SIGWT Mault 511ml 51 511 63610 5 Page 4 Si nal Conce ts 3 ll 1 g p rmw Inn A signal is pending if it has been sent but not yet received I There cm most one pending signal of any particular type I Important 0 If a process has a pending signal of type k then subsequent signals of type k that are sent to that process m are discarded cud A process ca bloc the receipt of certain signals I Blocked signa s can be delivered but will not be received until the signal is unblocked A pending signal is received at most once Signal Concepts 4 Kernel maintains pending and blocked bit vectors in the context of each process I pending represents the set of pending signals 0 Kernel sets bit k in pending when a signal of type k is delivered 0 Kernel clears bit k in pending when a signal of type k is received I blocked represents the set of blocked signals 0 Can be set and cleared by the application using the sigprocmask function 10 Page 5 Process Groups Every process belongs to exactly one process group pid10 pgid10 Backgrouriti Backgrou process group 32 process group 40 22 getpg39rp Return process p2 group of current process quotquotquotquotquotquotquotquotquotquotquotquotquot quot setpgido 7 Change process and Foregro process group 20 group of a process 11 Sending Signals 1 Using the kill program if 2 From the keyboard L32 m 3 Using the kill function F Fm with m Kill fall 5mm 12 Page 6 1 Sending Signals with kill Program kill program sends arbitrary signal to a process or process group Examples I kill 9 24818 0 Send SIGKILL to process 24818 I kill SIGKILL 2481397 0 Send SIGKILL to every process in group 24817 observe that PID is negative here I kill SIGIN 1 1234 0 Same as pressing Ctrlc if process 1234 is running in foreground No signal type name or number specified gt sends 15SIGTERM signal Comment Better command name would be sendsig 13 2 Sending Signals from the Keyboard Typing ctrlc ctrlz sends a SIGINTSGTSTP to every job in the foreground process group I SIGINT default action is to terminate each process I SIGTSTP default action is to stop suspend each process Backgroun B39 kb39r39 biid cess process group 32 group 40 Foregroun process group 20 14 Page 7 Example of ctrl c and ctrl z bash Child pid24868 pgrp24867 Parent pid24867 pgrp24867 Suspended bash ps PID TTY STAT TIME COMMAND 24788 pts2 S 000 bash 24867 pts2 T 001 forkex a 50 A 24868 pts2 I39Ol forke FP 24869 pts2 R 000 ps a bash fork lttyped ctrl cgt S G A T is Wk 394 bash ps a PID TTY STAT TIME COMMAND 24788 pts2 S 000 bash 24870 pts2 R 000 ps a 15 3 Sending Signals with kill Function kill int kill pidt pid int sig I Sends a sig signal to the process whose id is pid I Comment Better function name would be sendsig Example pidt pid getpid Process gets its id Process sends itself a SIGINT signal commits suicide 16 Page 8 kill Function Example void fork12 pidt pidun 1m 1 childstatus for o i I N fratms on Fund if pidli forkm o 54 fronts mu M whi1e1 Child infinite 100p R g k lwr Parent terminates the child processes for i o i lt n i quotM Mullahs 1 printfquotKilling process 96dnquot pidlil I ki11pidi 515nm zlquot Parent reaps terminated children for i 0 ilt ll i pidt wpid schi1dstatus if WIFEXITED c 11dstatus printfquotchild 95d terminated with exit status 96dnquot id WExITsTATuschi1dstatus else printfquotChild 96d terminated abnorma11ynquot wpid 17 Receiving Signals 1 Default Actions 2 Signal Handlers 18 Page 9 Receiving Signals ready to pass control to process p Kernel computes pnb pending amp blocked I The set of pending nonblocked signals for process p If pnb 0 Else I Pass control to next instruction in the logical flow for p I Choose least nonzero bit kin pnb and force process p to receive signal k I The receipt of the signal triggers some action by p I Repeat for all nonzero kin pnb I Pass control to next instruction in logical flow for p Suppose kernel is returning from exception handler and is 19 Default Actions Each signal type has a prede ned default action which is one of I The process terminates I The process terminates and dumps core I The process stops until restarted by a SIGCONT signal I The process ignores the signal 20 Page 10 Installing Signal Handlers The signal function modi es the default action associated with the receipt of signal signum I handlert signa1int signum handlert handler Different values for handler I SIGIGN ignore signals of type signum I SIGDFL revert to default action on receipt of signals of type Slgnum I Otherwise handler is the address of a signal handler o Called when process receives signal of type signum o Referred to as installing the handler o Executing handler is called catching or handling the signal 0 When the handler executes its return statement control passes backto instruction in the control flow ofthe process that was interrupted by receipt of the signal 21 Predefined Signal Handler SIGIGN Can install to ignore signals int mainvoid Signal SIGINT SIGIGN Subsequently process will ignore 2SIGINT signals 22 Page 11 Predefined Signal Handler SGDFL Can install to restore default signal handler int mainvoid Signal SIGINT SIGIGN signal SIGINT SIGDFL Subsequently process will handle 2SIGINT signals using the default handler for 2SIGINT signals 23 Signal Handling Exceptions A program cannot install its own handler for signals I 9SIGKILL a Default handler exits the process oCatchable termination signal is 15SIGTERM I 19SIGSTOP a Default handler suspends the process oCan resume the process with signal 18SIGCONT oCatchable suspension signal is 20SIGTSTP 24 Page 12 Signal Handling Example void inthandler int sig getpido sig exit0 void fork13 pidt pidN int 1 childstatus signalSIGINT inthandler same as before 24973 for 497 printfquotProcess 1d received signal dnquot 113 2 with exit signal 2 with exit si ha1 2 with exit signal 2 with exit signal 2 with exit status 0 status 0 status 0 status 0 3 r ter eceived minated status 0 25 Pending signals are not queued i t ccount 0 void childhand1erint sig I For each signai type i int childstatus JUSt have S39ngle b39t pidt pid wait schi1dstatus indicating whether or ccount P 39 39 39 printfquotReceived signal 96d from process 96dnquot not Slgnal IS pendlng Slgr Ind I Even if multiple processes have sent void fork14 this signal pidt pidln int i childstatus ccount II signa1SIGCHLD childhand1er for i 0 i lt ll i if pidli fork 0 Child Exit exit0 while Ccount gt 0 se 39 Suspend until signal occurs gt 26 Page 13 Living With Nonqueuing Signals Must check for all terminated jobs I Typically loop with wait void childhandler2int sig int childstatus pid t pid while Pid waitampchildstatus gt 0 n printfquotReceived signal ad from process dnquot sig pid void forle signal SIGCHLD childhandler2 27 Externally Generated Events ctrlc include ltstdlibhgt include ltstdiohgt include ltsignalhgt void handlerint Sig sleep2 printfquotWellquot fflushstdout sleepl printfquotOKnquot exit0 printfquotYou think hitting ctrl c will stop the bombnquot l mainO signalSIGINT handler installs ctl c handler whilel 28 Page 14 Internally Generated Events include ltstdio hgt include ltsignal hgt mainO signalSIGALRM handler alarml send SIGALRM in int beeps 0 1 second SIGALRM handler while 1 void handlerint Sig handler returns here printfquotBEEPnquot fflushstdout if beeps lt 5 bashs a ut alarml BEEP else BEEP printfquotBOOM nquot BEEP exit0 BEEP BEEP BOOM39 bash 29 Signal Blocking 1 Race Conditions 2 Blocking Signals 30 Page 15 Race Conditions in Signal Handlers A race condition is a aw in a program whereby the correctness ofthe program is critically dependent on the sequence or timing of other events We have seen that race conditions can occur in threads Race conditions can also occur in signal handlers 31 Race Condition Example void addsalary39l osavingsint sig int i39I39emp i39I39emp isavingsBalance i39I39emp iMonthlySalary isavingsBalance i39I39emp Handler for hypothetical update monthly salary signal 32 Page 16 Race Condition Example 1 1 Signal arrives handler begins executing void addsalary39l osavingsint iSig int i39I39emp i39l39emp isavingsBalance 2000 i39I39emp iMonthlySalary isavingsBalance i39I39emp 33 Race Condition Example 2 2 Another signal arrives rst instance of handler is interrupted second instance of handler begins executing void addsalary39l osavingsint iSig int i39I39emp i39I39emp isavingsBalance 2000 i39I39emp iMonthlySalary isavingsBalance i39I39emp A void addsalary39l osavings int iSig l int i39I39emp i39I39emp isavingsBalance 2000 i39I39emp iMonthlySalary isavingsBalance i39I39emp 34 Page 17 Race Condition Example 3 3 Second instance executes to completion void addsalary39l osavingsint iSig 5 int i39I39emp 3 i39I39emp isavingsBalance i39I39emp iMonthlySalary isavingsBalance i39I39emp 2000 int i39I39emp i39I39emp isavingsBalance i39I39emp iMonthlySalary isavingsBalance i39I39emp void addsalary39l osavingsint iSig 35 Race Condition Example 4 4 Control returns to rst instance which executes to completion void addsalary39l osavingsint iSig 5 int i39I39emp i39I39emp isavingsBalance i39l39emp iMonthlySalary isavingsBalance i39I39emp Lost 50 ll 36 Page 18 Blocking Signals in Handlers Blocking signals I To block a signal is to save it for delivery at a later time Why block signals when handler is executing I Avoid race conditions when another signal oftype X occurs while the handler for type X is executing How to block signals when handler is executing I Automatic during execution of signal handler I Previous sequence cannot happen I While executing a handler for a signal oftype x all signals of type x are blocked I Whenif signal handler returns block is removed 37 Blocking Signals in General Race conditions can occur elsewhere too int iE lag 0 void myHandlerint iSig iE lag 1 Problem my ag might becomel just int mainwoid after the39pbr nparison if iE lag 0 t Do something l Must make sure that critical sections of code are not interrupted 38 Page 19 Blocking Signals in General POSIX standard I De nes sigprocmasko and sigaction func I Provides mechanism to block signals in general Each process has a signal mask in the kernel I OS uses the mask to decide which signals to deliver I User program can modify mask with sigprocmask Functions for constructing signal sets I sigemptyset sigaddset 39 Blocking Signals sigprocmask sigprocmask int sigprocmask int iHow const sigsett psSet sigsett psoldSet I psSet Pointer to a signal set I psOldSet Irrelevant for our purposes I iHow How to modify the signal mask 0 SIGBLOCK Add psSet to the current mask 0 SIGUNBLOCK Remove psSet from the current mask 0 SIGSE39139MASK Install psSet as the signal mask I Returns 0 iff successful 40 Page 20 Blocking Signals Example sigsett sSet int mainvoid int iRet sigemptysetampsSet sigaddsetampsSet SIGINT iRet sig39procmaskSIGBLOCK ampsSet NULL assertiRet 0 if iE lag 0 l Do something iRet sig39procmaskSIGU39NBLOCK ampsSet NULL assertiRet 0 41 Blocking Signals in Handlers Signals of type X automatically are blocked when executing handler for signals of type X Additional signal types to be blocked can be defined at time of handler installation 42 Page 21 Installing a Signal Handler sigaction int sigactionint iSig const struct sigaction psAction struct sigaction psOldAction I isig The type of signal to be affected I psAction Pointer to a structure containing instructions on how to handle signals of type isig including signal handler name and which signal types should be blocked I psoldAction Irrelevant for our purposes I Installs an appropriate handler I Automatically blocks signals of type isig I Returns 0 iff successful 43 Installing a Handler Example Program testsigactionc include ltstdio hgt include ltstdlib hgt include ltsig39nal hgt void myILandlerint isig printfquot In myHandler with argument dnquot isig 44 Page 22 Installing a Handler Example contd Program testsigactionc contd int mainvoid int iRet struct sigaction sAction sActionsaflags 0 sAction sahandler myHandler sigemptysetampsAction samask iRet sigactionSIGINT ampsAction NULL assertiRet 0 printfquotEntering an infinite loopnquot while 1 return 0 45 Installing a Handler Example contd Demo oftestsigactionc 46 Page 23 Predefined Signals List ofthe predefined signals bash kill 1 1 SIGHUP 2 SIGINT 3 SIGQUIT 4 SIGILL 5 SIGTRAP 5 SIGIOT 7 SIGEMT 8 SIGE PE 9 SIGKILL 10 SIGBUS 11 SIGSEGV 12 smsvs 13 SIGPIPE 14 SIGALRM 15 SIGTERM 15 smusm 17 5160532 18 SIGCHLD 19 SIGP WR 20 SIGWINCH 21 SIGURG 22 SIGIO 23 SIGSTOP 24 SIGTSTP 25 SIGCONT 25 SIGTTIN 27 SIGTTOU 28 SIGVTALRM 29 SIGPROE 30 SIGXCPU 31 SIGXE SZ Applications can define their own signals I An application can de ne signals with unused values 47 Summary A signal is an asynchronous event mechanism I Can generate from user programs I Can de ne effect by de ning signal handler Signals don t have queues I Just one bit for each pending signal type Beware of race conditions I Signals of type X automatically are blocked while handler for type X signals is running I POSIX sigprocmask blocks signals in any critical section of code 48 Page 24


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

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

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!"

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."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.