Computer Systems and Programm
Computer Systems and Programm CS 367
Popular in Course
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
verified elite notetaker
Popular in ComputerScienence
This 139 page Class Notes was uploaded by Leland Swift on Monday September 28, 2015. The Class Notes belongs to CS 367 at George Mason University taught by Richard Carver in Fall. Since its upload, it has received 12 views. For similar materials see /class/215112/cs-367-george-mason-university in ComputerScienence at George Mason University.
Reviews for Computer Systems and Programm
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/28/15
Topics I Process context switches I Creating and destroying processes Def A process is an instance of a running program I One of the most profound ideas in computer science I Not the same as program or processor Process provides each program with two key abstractions I Logical control flow 0 Each program seems to have exclusive use of the CPU I Private address space 0 Each program seems to have exclusive use of main memory How are these Illusions maintained I Process executions interleaved multitasking I Address spaces managed by virtual memory system Page 1 Logical Emmi Flows Each process has its own logical control flow Process A Process B Process C Time Processes Two processes run concurrently are concurrent if their flows overlap in time Otherwise they are sequential Examples I Concurrent A amp B A amp C I Sequential B amp C Process A Process B Process C Time Page 2 User V at Concurrent Processes Control flows for concurrent processes are physically disjoint in time However we can think of concurrent processes are running in parallel with each other Process A Process B Process C Context 8 Processes are managed by a shared chunk of OS code called the kernel I Important the kernel is not a separate process but rather runs as part of some user process Control flow passes from one process to another via a context switch Process A user code context switch e TIme user code kernel code context switch user code Page 3 Prquot 1 Address Spaces Each process has its own private address space Oxffffffff kernel virtual memory code data heap stack T invisible to OchOOOOOO usercode user stac created at runtime iesp stack pointer f nu OX4 O 00 O 00 O T brk runtIme hea managed by malloc readwn39te segment 39data 39bss loaded 39om the readonly segment executable le OX08048000 init text rodata 0 unused Em Cilia int fork void I creates a new process child process that is identical to the calling process parent process I returns 0 to the child process I returns child s pid to the parent process if ff39o39rk 39 0 it rintfl h evl39io from chiis irnquotL Fork is interesting 39 quot5 I M and often confusing Purltf uhello 39m Pare t because it is called 1 once but returns twice Page 4 Fork Example 1I Key Points I Parent and child both run same code 0 Distinguish parent from child by return value from fork I Start with same state but each has private copy 0 Including shared output file descriptor 0 Relative ordering of their print statements undefined writs ltI To 6 E Eem c 2 g l a gt34 qu a s 1 Emerges cm Agata g idwa 123 5 Fork Example 2 Key Points I Both parent and child can continue forking TEIME W Jle gt3 10 Page 5 Fork Example 3 Key Points I Both parent and child can continue forking WELLS Erhard Cb d 11 Fork Exampie 4 Key Points I Both parent and child can continue forking WM 341 U i Egilniiiridii WWW 3 r at mg 1933 m warm 0 12 Page 6 Fork Example 5 Key Points I Both parent and child can continue forking E6423 i L at NE a EEW 5 9 MGmE m ib 5 E5FQ 53 979 H 13 exit Destroying Process void exit int status I exits a process 0 Normally return with status 0 I atexit registers functions to be executed upon exit mid Gib EEQWe i mimia mweemm mew 3 r 1d 1136 m a 14 Page 7 Zombies Idea I When process terminates still consumes system resources 0 Various tables maintained by OS I Called a zombie 0 Living corpse half alive and half dead Reaping I Performed by parent on terminated child I Parent is given exit status information I Kernel discards process What if Parent Doesn t Reap I If any parent terminates without reaping a child then child will be reaped by init process I Only need explicit reaping for longrunning processes 0 Eg shells and servers 15 Zmeiie 50 5mm Example Wilma linuxgt forks 7 E 1 5539 Running Parent PID 5539 Terminating Child PID 5540 linuxgt pm T39I39Y TIME CMD 5585 ttpr 000000 tcsh 39 PS ShOWS Chlld 5539 ttyp9 000003 forks process as defunct 5540 ttyp9 000000 forks ltdefunctgt 5541 ttypg 000000 PS I KIllIng parent allows linuxgt 1111 6639 child to be reaped 1 Terminated linuxgt p5 PID T39I39Y TIME CMD 5585 ttpr 000000 tcsh 5542 ttyp9 000000 p5 16 Page 8 Nonterminating 55 Game 9 a Child Example WE mmJam 81 39383 aim k hf z ix Kw linuxgt forks 8 Terminating Parent PID 5575 Running Child PID 5575 linuxgt p5 PID T39I39Y TIME CMD 5585 tipr 000000 tcsh 6676 tty129 000006 forks I Child process still active 5577 W 00000 1 5 even though parent has 1an lull 5575 t t d limp P5 ermIna e PID TTY TIME GMD I Must kill explicitly or else 5585 tipr 000000 tcsh 5578 tipr 000000 ps Nlquot runnlng IndefInItely 17 wait Synchronizing mm children int wait int childstatus I suspends current process until one of its children terminates I return value is the pid of the child process that terminated I if childstatus NULL then the object it points to will be set to a status indicating why the child process terminated 18 Page 9 void fork9 int childs tatus if fork 0 printfquotHC hello from childnquot else printfquotHP hello from parentnquot waitampchildstatus printfquotCT child has terminatednquot printfquotByenquot exit HC Bye HP CT Bye 19 W am I If multiple children completed will take in arbitrary order I Can use macros WIFEXITED and WEXITSTATUS to get information about exit status void forklOO pidt pidN int i int childstatus or i 0 i lt N i if pidi fork 0 exit100i Child for i 0 i lt N i pidt wpid waitampchildstatus if WIFEXITEDchildstatus printfquotChild d terminated with exit status dnquot wpid WEXITSTATUSchild tatus se printfquotChild d terminate abnormallynquot wpid Page 10 mammal I waitpidpid Estatus options 0 Can wait for specific process 0 Various options mid 16 f d 61 SJ wings Wyldu G i lld Wawwmpm Examplle Outputs Using wait forklO 23 mw m main gas am mm mm gm mm 133 3 gassing Mb r 142 m a quot39quot f W m a i aim ma Using waitpid forkll m mm mi h mt t y i i 4319 mmmb a hg 99m 11 m m m l 933131 i i 35mm 3 22 Page 11 CS 367 MachineLevel Prirammin Ill Prcelures Topics I IA32 stack discipline I Register saving conventions I Creating pointers to local variables lecture10ppt IA32 Stack I Region of memory managed with stack discipline Stack Bottom I Grows toward lower T addresses Increasing I Register esp indicates Addresses lowest stack address 0 address of top element Stack Grows Stack D own Pointer esp l Stack Top CS 367 IA32 Stack Pushing Pushing Stack Bottom l pushl SI C I Fetch operand at Src T I Decrement esp by 4 Increasing Addresses I Write operand at address given by esp Stack Grows Down l Stack Pointer esp 39 Stack Top 3 cs 367 IA32 Stack Popping Stack Bottom I popl Best I Read operand at address T given by esp Increasing Addresses I Increment esp by 4 I Write to Best I Stack Grows Down Stack Pointer esp Stack Top 4 CS 367 Stack Operation Examples pushl eax popl edx 0x110 0x100 0x108 0x110 0x100 0x108 0x104 0x110 0x100 0x108 0x104 5544555555 eax 213 eax 213 eax edx 555 edx 555 edx esp 0x108 esp esp 5 CS 367 Prceure Cntrol Flow I Use stack to support procedure call and return Procedure call call label Push return address on stack Jump to label Return address value I Address of instruction beyond call I Example from disassemny 804854e e8 3d 06 00 00 call 8048b90 ltmaingt 8048553 50 pushl eax OReturn address 0x8048553 Procedure return I ret Pop address from stack Jump to address 6 CS 367 Procedure Call Example 804854e e8 3d 06 00 00 call 8048b90 ltmaingt 8048553 50 pushl eax call 8048b90 0x110 0x110 0x100 0x100 0x108 0x108 0x104 0X8048553 esp 0x108 eip 0x804854e eip is program counter 7 CS 367 Prceure Return Example 8048591 03 ret ret 0x110 0x100 0x108 esp 0x104 esp eip 0x8048591 eip 0x8048553 eip is program counter 8 CS 367 StackBased Languages Languages that Support Recursion I eg C Pascal Java I Code must be Reentrant 0 Multiple simultaneous instantiations of single procedure I Need some place to store state of each instantiation o Arguments 0 Local variables 0 Return pointer Stack Discipline I State for given procedure needed for limited time c From when called to when return I Callee returns before caller does Stack Allocated in Frames I state for single procedure instantiation 9 cs 367 Call Chain Example Code Structure Call Chain amI amI amI I Procedure amI lm 0 recursive cs 367 10 Stack Frames Contents I Local variables I Return information who I Temporary space amI Management I Space allocated when enter procedure Frame 0 Setup code Pointer I Deallocated when return ebp gt 0 Finish code PrOC Stack Pointers Pointer esp Stack I Stack pomter esp Indicates Top stack top I Frame pointer ebp indicates 11 start of current frame CS 367 Stack Operation Frame Pointer Call Chain ebp Stack yoo Pointer o esp Wh t gt f 0 12 cs 367 Stack Operation h Call Chain L V Frame Pointer gt o o YOO amI who 39 39 39 who Stack amI Pointer o o o esp 13 CS 367 Stack Operation Call Chain amIm gt YOO l h amI who Frlame W O Pomter l ebp amI amI Stack F Pomter esp 14 CS 367 Stack Operation Call Chain amI yoo gt yoo who amI who amI Frame amI l Pointer amI ebP I amI Stack 39 Pointer esp 15 CS 367 Stack Operation Call Chain amIm gt yoo l who amI who amI amI amI l Frame amI Pointer amI ebp amI Stack 39 Pointer esp 16 CS 367 Stack Operation Call Chain amI gag yoo 39 h amIo who W gt 39 l amI Frame amI l Pointer amI ebP I amI Stack 39 Pointer esp 17 CS 367 Stack Operation Call Chain amIm yoo l h amI I who Frlame W O Pomter l S cebp gt amI amI Stack Pointer 39 esp 18 CS 367 Stack Operation h Call Chain M v o Frame gygora Pointer yoo S cebp gt amI who quot 39 39 who Stack amI Pointer o o o esp 19 CS 367 Stack Operation Call Chain amI yoo gt l h Frame Who W O Pointer S cebp gt amI amI Stack Pointer 39 esp 20 CS 367 1O y Stack Operation Call Chain Whom 39 yoo amI CI 0 j amI I V 7quot g y A 1 7 77 7 f 111 39 tfe QL e i 39 gtb r 21 Frame Pointer ebp Stack Pointer eSp CS 367 Stack peration Call Chain ylto 22 Frame Pointer ebp Stack Pointer eSp CS 367 11 lA32Linux Stack Frame Current Stack Frame Top f to Bottom I Parameters for function Caller about to call Frame lt o Argument build Arguments I LOCI va rlibles Frame Pointer Return Addr 0 cant eep In registers ebp I Saved register context H a I Old frame pointer 77 Reg rosters Caller Stack Frame I Return address 0 Pushed by call instruction I Arguments for this call 23 v Stack Pomter eSp gt CS 367 Revisiting swap 15213 91125 int zipl int zip2 void callswap swapampzip1 ampzip2 void swapint xp int yp int t0 xp int t1 yp xp t1 yp t0 24 Calling swap from callswap callswap C C Global Var Global Var pushl zip2 pushl zip1 call swap Resulting Stack ampzip2 ampzipl Rtn adr lt esp CS 367 12 Revisiting swap swap pushl ebp movl espebp set pushl ebx Up v01d swap1nt xp 1nt yp I movl 12ebpecx fnt t0 XPr movl 8ebpedx nt t1 YP39 movl ecxeax gt Bod XP tll movl edxebx y YP tor movl eaxedx movl ebxecx J movl 4ebpebx movl ebpesp gt Fh sh popl ebp ret J 25 CS 367 swap Setup 1 Entering tesukltmg Stack ac lt ebp ebp ampzip2 YP ampzipl XP Rtn adr lt esp Rtn adr esp swap ushl eb movl espebp pushl ebx 26 CS 367 13 swap Setup 2 Entering Resulting Stack Stack lt ebp ampzip2 yp ampzipl xp Rtn adr lt esp Rtn adr irlfd ebp esp swap pushl ebp movl espg p pushl ebx 27 CS 367 swap Setup 3 Entering Resu39ting Stack Stack lt ebp ampzip2 yp ampzipl xp Rtn adr lt esp Rtn adr iilid ebp 1 esp swap pushl ebp movl espebp pushl ebx 28 CS 367 14 Effect of swap Setup Entering Stack Resulting ebp Stack Offset relative to ebp ampzip2 12 yp ampzip1 XP Rtn adr lt esp 4 Rtn adr 0 Ifd 9691 Aid esp movl 12ebpecx get yp movl 8ebpedx get xp BOdy 29 CS 367 swap Finish 1 swap s Stack Offset Offset 12 yp 12 yp 8 xp 8 XP 4 Rtn adr 4 Rtn adr 0 is lt ebp o ebp 4 aflid lt esp 4 fitd lt esp movl 4ebpebx movl ebpesp Observation 1001 ebP r I Saved amp restored register ebx e 30 CS 367 15 swap Finish 2 swap s swap s Stack Stack Offset Offset 12 yp 12 yp 8 XP 8 xp 4 Rtn adr 4 Rtn adr 0 Id 96ebP o ebP 4 esp esp movl 4ebpebx movl ebp p popl ebp ret 31 CS 367 swap Flnlsh 3 a 1 ebp swap s swap 5 Offset Offset 12 yp 12 W 8 xp 8 xp 4 Rtn adr 4 Rtn adr A esp 0 lil fd ebp esp movl 4ebpebx movl ebpesp Lem ret 32 CS 367 16 swap Finish 4 swapls 1 ebp Stack Offset 12 yp 8 xp 4 Rtn adr esp Observation 33 I Saved amp restored register ebx lt ebp Exiting Stack ampzip2 ampzipl esp movl 4ebpebx movl ebpesp popl ebp 1 I Didn t do so for eax ecx or edx CS 367 Register Saving Conventins When procedure yoo calls who I yoo is the caller who is the caIIee Can Register be Used for Temporary Storage yoo Q C Q movl 15213 edx call who edx eax ret 039 o 0 WWE as F 5151 a Q a 0 EEE I Contents of register edx overwritten by who 34 CS 367 17 egister Saving Conventions When procedure yoo calls who I yoo is the caller who is the callee Can Register be Used for Temporary Storage Conventions I Caller Save 0 Caller saves temporary in its frame before calling I Callee Save 0 Callee saves temporary in its frame before using 35 CS 367 lA32Linux Register Usage Integer Registers I Two have special uses 96ebp esp CallerSave lt Temporarles I Three managed as calleesave ebxesiedi 0 Old values saved on CalleeSave lt stack prior to using Temporarles I Three managed as callersave eax edx ecx Special 0 Do what you please but expect any callee to do so as well I Register eax also 36 stores returned value CS 367 18 R F I globl rfact type rfactfunction int rfactint x rfact pushl ebp lnt rval movl espebp if X lt 1 pushl ebx return 1 movl 8ebpebx rval rfaCtX391 cmpl 1ebx return rval x jle L78 leal 1ebxeax pushl eax call rfact imull ebxeax Registers jmp L79 I eax used without first align 4 saving L78 I ebx used but save at m V1 1 quot be innin amp restore at end 39L79 9 9 movl 4 ebp ebx movl ebpesp popl ebp ret 37 9 267 T pre ebp lt ebp pre ebx Entering Stack Caller x l Rtn adr lt eSP rfact pushl ebp movl espebp ushl ebx T pre ebp Caller pre ebx 8 x 4 Rtn adr 0 ltlrd eb 1 4 96ebp Callee H g l 4 I esp 38 CS 367 19 Rfact Body movl 8ebpebx ebx cmpl 1ebx Compare x 1 jle L78 If lt goto Term leal 1ebxeax eax x 1 Recursion pushl eax Push x1 call rfact rfactx l imull ebxeax rval x jmp L79 Goto done L78 Term movl 1eax return val 1 L79 Done int rfactint x Registers int rval if x lt 1 return 1 rval rfactx l return rval x ebx Stored value of x eax oTemporary value of xl oReturned value from rfact x1 oReturned value from this call 39 CS 367 leal 1ebxeax x pushl eax Rtn adr ebp x esp Rtn adr call rfact 44444447 ebp X Rtn adr esp ebp eax x l ebx x Wp i eax x 1 kJ WA ebx x eSP eax x 1 ebx x 40 CS 367 20 Rfact Result Return from Call X Rtn adr eax xl ebx X ebp esp Assume that rfact xl returns xl in register imull ebxeax X eax ebx Rtn adr 5 eax 41 CS 367 Rfact COmPIEtIOH movl 4 ebp ebx movl ebpesp popl ebp pre ebp ret pre ebx 8 x 4 Rtn adr pre 96913 0 ebp pre ebx pre ebp lt ebp 4 116 8 x pre ebx 8 4esp 4 Rtn adr x 0 Rtn adr esp eax ebx i eax x ebx Old ebx 96eax x ebx Old ebx 42 CS 367 21 Pinter zode Recursive Procedure Topeve Call Hm 391 v I 39H 5 39Nx rm 73 k Lg L A 1 E m HL a E 331119 Ur I Pass pointer to update location 43 CS 367 ireating Initializinl Pintr Initial part of sfact sfact pushl ebp Save ebp 8 x movl espebp Set ebp subl 16esp Add 16 bytes movl 8ebpedx edx x movl 14ebp val 1 Using Stack for Local Variable I Variable val must be stored on stack 0 Need to create pointer to it I Compute pointer as 4 ebp I Push on stack as second argument 44 22 Passing Pointer Callin s hel er from sfact g p Stack at time of call leal 4ebpeax Compute ampval 8 x pushl eax Push on stack 4 Ru1adr pushl edx Push x 7 0 39 0A 0 call shelper call CMQ p movl 4ebpeax Return val 394 c c c Finish 8 12 33 16 E isms W ll a la esp 45 CS 367 void shelper int x int accum O O 0 int 2 accum x accum z eax raccumx 39 39 39 ecx x O O O movl ecxeax z x imull edxeax z accum movl eaxedx accum z 0 O O I Register ecx holds x I Register edx holds pointer to accum 0 Use access edx to reference memory 46 CS 367 23 CS 367 Processes amp Signals Topics I Process Hierarchy I Shells I Signals I Nonlocaljumps lecture16ppt The World of Multitasking System Runs Many Processes Concurrently I Process executing program 0 State consists of memory image register values program counter I Continually switches from one process to another 0 Suspend process when it needs lO resource or timer event occurs 0 Resume process when lO available or given scheduling priority I Appears to users as if all processes executing simultaneously 0 Even though most systems can only execute one process at a time 0 Except possibly with lower performance than if running alone 2 CS 367 Programmer s Model of Multitasking Basic Functions I fork spawns new process 0 Called once returns twice I exit terminates own process 0 Called once never returns 0 Puts it into zombie status I wait and waitpid wait for and reap terminated children I execl and execve run a new program in an existing process 0 Called once normally never returns Programming Challenge I Understanding the nonstandard semantics of the functions I Avoiding improper use of system resources 0 Eg Fork bombs can disable a system 3 CS 367 Unix Process Hierarchy 0 initE Login shell Child 4 CS 367 I III 39I o o o Unix Startup Step 1 1 Pushing reset button loads the PC with the address of a small bootstrap program 2 Bootstrap program loads the boot block disk block 0 3 Boot block program loads kernel binary eg bootvmlinux 4 Boot block program passes control to kernel 5 Kernel handcrafts the data structures for process 0 0 Process 0 handcrafted kernel process Process 0 forks child process 1 Child process 1 execs sbininit 5 CS 367 Unix Startup Step 2 0 etcinittab gt 39 39 111113 1 init forks and execs daemons per etcinittab and forks Daemons getty agrdtrezicgsnggyltty program neg ftpd httpd c 0 o n I I n I II I I 39 l l I I I 39 39 l I I I u I I I I I I n u I II 6 CS 367 Unix Startup Step 3 0 The getty process execs a login program CS 367 Unix Startup Step 4 0 login reads login and passwd if OK it execs a shell if not OK it execs another getty CS 367 A shell is an application program that runs programs on behalf of the user I sh Original Unix Bourne Shell I csh BSD Unix C Shell tcsh Enhanced C Shell I bash BourneAgain Shell Execution is a sequence of readevaluate steps CS 367 Problem with Simple Shell Example Shell correctly waits for and reaps foreground jobs But what about background jobs I Will become zombies when they terminate I Will never be reaped because shell typically will not terminate I Creates a memory leak that will eventually crash the kernel when it runs out of memory Solution Reaping background jobs requires a mechanism called a signal 1 1 CS 367 Signals A signal is a small message that notifies a process that an event of some type has occurred in the system I Kernel abstraction for exceptions and interrupts I Sent from the kernel sometimes at the request of another process to a process I Different signals are identified by small integer lD s I The only information in a signal is its ID and the fact that it arrived ID Name Default Action Corresponding Event 2 SIGINT Terminate Interrupt from keyboard ctlc 9 SISKILL Terminate Kill prOgram cannot override or ignore 11 SiITGfSEGV Terminate gamp Dump 39 Segmentation violation 1 4 Terminate Timer signal 17 Ignore Child stopped or terminated 12 cs 367 Signal Concepts Sending a signal I Kernel sends delivers a signal to a destination process by updating some state in the context of the destination process I Kernel sends a signal for one of the following reasons 0 Kernel has detected a system event such as dividebyzero SIGFPE or the termination of a child process SIGCHLD 0 Another process has invoked the kill system call to explicitly request the kernel to send a signal to the destination process 13 CS 367 Signal Concepts cont 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 o Ignore the signal do nothing 0 Terminate the process 0 Catch the signal by executing a userlevel function called a signal handler Akin to a hardware exception handler being called in response to an asynchronous interrupt 14 CS 367 Signal Concepts cont A signal is pending if it has been sent but not yet received I There can be at most one pending signal of any particular type I Important Signals are not queued o If a process has a pending signal of type k then subsequent signals of type k that are sent to that process are discarded A process can blockthe receipt of certain signals I Blocked signals can be delivered but will not be received until the signal is unblocked A pending signal is received at most once 15 CS 367 Signal Concepts 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 whenever a signal of type k is delivered 0 Kernel clears bit k in pending whenever 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 16 CS 367 rocess Groups Every process belongs to exactly one process group pid10 pgid10 Background Background process group 32 process group 40 getpgrp Return process group of current process quot39 set id Chan e rOCGSS Foreground paw f a rocegs p process group 20 g p p 17 CS 367 Sending Signals with kill Program kill program sends arbitrary signal to a 6 process or process hilQQg pie sl pgry group l mm vps EE J LEEME I ngg39b g g Examples 57 QiEsJ g m i m A zstsr2 gg2 fcrks I kill 9 24818 ts2 g22 0 send SIGKILL to pitsng gg 11939s lipase limu s ps I kill 9 24817 lam 0 Send SIGKILL to V eases every process 1n lim ggt process 24818 LEI K5 HP HP l W k3 l process group 24817 18 CS 367 frm Typing ctrlc ctrlz sends a SIGTERM SIGTSTP to every job in the foreground process group I SIGTERM default action is to terminate each process I SIGTSTP default action is to stop suspend each process BE kJ Und B Zk 76amphd process process group 32 group 40 Forernd process group 20 19 CS 367 Example ctrl c nd ctrlz 31 31 3 E E ts 20 CS 367 1O Sending Signals with kill Function void fork12 pidt pidN int i childstatus for i 0 i lt N i if pidi fork 0 while1 Child infinite loop Parent terminates the child processes for i 0 i lt N i printfquotKilling process dnquot pidi killpidi SIGINT Parent reaps terminated children for i 0 i lt N i pidt wpid waitampchildstatus if WIFEXITED childstatus printfquotChild d terminated with exit status dnquot wpid WEXITSTATUSchildstatus else printfquotChild d terminated abnormallynquot wpid 21 CS 367 Receiving Signals Suppose kernel is returning from exception handler and is 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 I Pass control to next instruction in the logical flow for p Else 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 k in pnb I Pass control to next instruction in logical flow for p 22 CS 367 11 Default Actions Each signal type has a predefined default action which 23 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 CS 367 Installing Signal Handlers The signal function modifies the default action associated with the receipt of signal signum l handlert signalint signum handlert handler Different values for handler 24 I SIGIGN ignore signals of type signum I SIGDFL revert to the default action on receipt of signals of type signum 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 back to instruction in the control flow of the process that was interrupted by receipt of the signal CS 367 12 Sinal Handling Example void inthandlerint sig printfquotProcess d received signal dnquot getpid sig exit0 void forkl3 M pidt pidN int i child status signalSIGINE inthandler i tag 2amp0 s EE hild Ghil 25 L Lash signan emimigl eei exit w it dew Phil Ram iW I ted quot EL tQ g CS 367 Signal Handler Funkiness Pending signals are not int ccount 0 void childhandlerint sig int childstatus pidt pid waitampchildstatus ccount printfquotReceived signal d from process dnquot sig pid void forkl4 pidt pidN int i childstatus ccount N signalSIGCHLD childhandler for i 0 i lt N i if pidli fork 0 Child Exit exit0 while ccount gt 0 pause Suspend until signal occurs queued I For each signal type just have single bit indicating whether or not signal is pending I Even if multiple processes have sent this signal CS 367 13 Living With Nonqueuing Signals Must check for all terminated jobs I Typically loop with waitpid void childhandler2int sig Pid void fork15 int childstatus pidt pid while pid waitpid 1ampchildstatusWNOHANG gt 0 ccount printfquotReceived signal d from process dnquot sig signalSIGCHLD childhandler2 27 CS 367 A Program That Reacts to Externally Generated Events ctrlc include ltstdlibhgt include ltstdiohgt include ltsignalhgt void handlerint sig main printfquotYou think hitting ctrl c will stop the bombnquot sleep2 printfquotWellquot fflushstdout sleepl printfquotOKnquot exit0 signalSIGINT handler while1 installs ctl c handler 28 CS 367 14 A Program That Reacts to Internally Generated Events include ltstdiohgt main include ltsignalhgt 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 linuxgtmauout alarml H else BEEP printf quotBOOMnquot BEEP exit0 Beep BEEP BEEP 1379M 5bassgt 29 CS 367 Nonlocal Jumps setjmplongjmp Powerful but dangerous userlevel mechanism for transferring control to an arbitrary location I Controlled to way to break the procedure callreturn discipline I Useful for error recovery and signal handling int setjmpjmpbuf j I Must be called before longjmp I Identifies a return site for a subsequent longjmp I Called once returns one or more times Implementation I Remember where you are by storing the current register context stack pointer and PC value in jmpbuf I Return 0 30 CS 367 15 setjmplongjmpcon void longjmp jmpbuf j int i I Meaning 0 return from the setjmp remembered by jump buffer j again 0 this time returning i instead of 0 I Called after setjmp I Called once but never returns longjmp Implementation I Restore register context from jump buffer j I Set eax the return value to i I Jump to the location indicated by the PC stored in jump buf j 31 CS 367 setjmplongjmp Example include ltsetjmphgt jmpbuf buf main if setjmpbuf 0 printfquotback in main due to an errornquot else printfquotfirst time throughnquot p1 p1 calls p2 which calls p3 P3 lterror checking codegt if error longjmpbuf 1 32 CS 367 16 Putting It All Together A Program That Restarts Itself When ctrl c d include ltstdiohgt include ltsignalhgt include ltsetjmphgt sigjmpbuf buf void handlerint sig siglongjmpbuf 1 main if sigsetjmpbuf 1 printfquotstartingnquot else While1 sleep1 printfquotprocessingnquot signalSIGINT handler printfquotrestartingnquot 33 bales morale Legeeeeeimc 0 o Legeeeeeimc 0 o Ecerereeeimego o o 4 Ctrlc gagcgmereeeiwego o o Ecerereeeimego o o gagcgmereeeiwego o o eeetaizeg o a i gog 4 Ctrlc 4 CtrIc CS 367 Limitations of Nonlocal Jumps Works within stack discipline I Can only long jump to environment of function that has been called but not yet completed em jmpbuf env Pl if setjmpenv else P2 P2 P2 P3 longjmpenv 1 34 Long Jump to here Illiiilll Before longjmp 17 After longjmp CS 367 Computer Systems amp Programming CS 367 Prof Richard Carver George Mason University Course Goals Previous courses CS 112 CS 211 highlevel programming in JavaC This course exposes you to C and assembly programming C is a procedural language not objectoriented Commonly used for lowlevel systems programming and embedded systems Theme of the course strip away abstractions provided by highlevel languages such as Java and let you understand what goes on under the hood Course Goals cont d Abstractions have limits Especially in the presence of bugs Need to understand underlying implementations Useful outcomes Become more effective programmers gtAble to find and eliminate bugs efficiently gtAble to tune program performance Prepare for later systems classes in CS amp ECE gtCompilers Operating Systems Networks Computer Architecture Great Reality 1 Int s are not Integers Float s are not Heals Examples is x2 a 0 gt Float s Yes gt lnt s 40000 40000 gt 1600000000 50000 50000 gt 392 isxyz xyz gtUnsigned amp Signed lnt s Yes gt Float s 1e20 1e20 314 gt 314 1e20 1e20 314 gt 392 Computer Arithmetic Does not generate random values Arithmetic operations have important mathematical properties Cannot assume usual properties Due to finiteness of representations Integer operations satisfy ring properties gtCommutativity associativity distributivity Floating point operations satisfy ordering properties gt Monotonicity values of signs Observation Need to understand which abstractions apply in which contexts Important issues for compiler writers and serious application programmers Great Reality 2 You ve got to know assembly Chances are you ll never write program in assembly Compilers are much better amp more patient than you are Understanding assembly key to machinelevel execution model Behavior of programs in presence of bugs gt Highlevel language model breaks down Tuning program performance gt Understanding sources of program inefficiency Implementing system software gt Compiler has machine code as target gt Operating systems must manage process state Great Reality 3 Memory Matters Memory is not unbounded It must be allocated and managed Many applications are memory dominated Memory referencing bugs especially pernicious Effects are distant in both time and space Memory performance is not uniform Cache and virtual memory effects can greatly affect program performance Adapting program to characteristics of memory system can lead to major speed improvements Memory Referencing Bug Example main long int a2 double d 314 a2 1073741824 Out of bounds reference printfquotd 1Sgnquot d exit0 Alpha MIPS Linux g 530498947741318e315 31399998664856 314 O 314 314 314 Linux version gives correct result but implementing as separate function gives segmentation fault Memory Referencing Errors C and C do not provide any memory protection Out of bounds array references Invalid pointer values Abuses of mallocfree Can lead to nasty bugs Whether or not bug has any effect depends on system and compiler Action at a distance gt Corrupted obiect logically unrelated to one being accessed gt Effect of bug may be first observed long after it is generated How can I deal with this Program in Java Lisp or ML Understand what possible interactions may occur Use or develop tools to detect referencing errors Course Perspective Most Systems Courses are BuilderCentric Computer Architecture gtDesign pipelined processor Operating Systems gt Implement portions of operating system Compilers gtWrite compiler for simple language Networking gt Implement and simulate network protocols Course Perspective Cont This Course is ProgrammerCentric Purpose is to show how by knowing more about the underlying system one can be more effective as a programmer Enable you to gtWrite programs that are more reliable and efficient gt Incorporate features that require hooks into OS Eg concurrency signal handlers Not just a course for dedicated hackers gtWe bring out the hidden hacker in everyone Cover material in this course that you won t see elsewhere gtLinking loading signals gdb debugger Relationship to other courses Prerequisites changing in the spring CS 211 Computer Science ll ECE 301303331 Digital Logic CS 112 211 310 have migrated to using Java instead of C CS 265 Assembly programming no longer taught Goal of this course CS 367 is to replace CS 265 Assembly Programming and expose students to a different programming language C from a bottom up perspective Programming assignments involving machine and assembly language x86 an programming in C Textbooks Randal E Bryant and David R O Hallaron Computer Systems A Programmer s Perspective Prentice Hall 2003 csappcscmuedu Brian Kernighan and Dennis Ritchie The C Programming Language Second Edition Prentice Hall 1988 You can use any book on C Course Outline Programming in C 2 weeks Data Representation 2 weeks Program Representation 5 weeks Linking 1 week Exceptional Control Flow amp Virtual Memory 3 weeks Programming in C Assumption You are comfortable programming in Java andor C C is a procedural imperative programming language Topics C Standard lO library for inputoutput Bitlevel operators Pointers amp Structures Memory allocation and deallocation Assignment P1 Write a nontrivial program in C Machinelevel Representation of Data and Programs Topics Bits operations arithmetic assembly language programs representation of C control and data structures Includes aspects of of architecture and compilers Assignments Lab Linking and Exceptional Control Flow Topics Object files static and dynamic linking libraries loading Hardware exceptions processes process control Unix signals nonlocal jumps Virtual Memory Includes aspects of compilers OS and architecture Assignments Lab Unix Processes Rationale for Assignments Doing an assignment should result in new skills and concepts P1 programming in C P2 computer arithmetic digital logic P3P4 assembly language using a debugger understanding the stack P5 understanding Unix processes Logistics Grading Programming Assignments and Homework 50 gt All programs will be tested on a Linux platform for grading You need to obtain an ITampE Unix Cluster account See syllabus Midterm 25 amp Final 25 Class TA Raimi Rufai tbd Office Hrs TBD My office hrs T 345430pm SampT ll Room 343 Also available at other times eg before class Always available via email Policies Classroom Set phones to vibrate mode if you must leave them on Introd uction to C Acknowledgement These slides are adapted from lecture slides made available by Prof Dave 0 Halloran Carnegie Mellon University Outline Overview comparison of C andJava Good evening Preprocessor Command line arguments o Arrays and structures Pointers and dynamic memory What we will cover A crash course in the basics of C You should read the KampR C book for lots more details Like Java like C Operators same asJava Arithmetic I i il i i i 2 Relationaland Logical lt gt ltl gtl 39 818 II amp I Syntax same as in Java l ifelse while do while fori1 i lt 100 i switch continue break case 1 m datatype char short int long float double Simple Data Types size values 1 128 to 127 2 32768 to 32767 4 2147483648 to 2147483647 4 2147483648 to 2147483647 4 34E38 7 digits 8 l7E308 15 digits long Java programmer gotchas 1 int i fori 0 i lt 10 i NOT forint i 0 i lt 10 i Java programmer gotchas 2 Uninitialized variables catch with Wall compiler option include ltstdiohgt int mainint argc char argv int i factoriali return 0 Java programmer gotchas 3 Error handling No exceptions Must look at return values Good evening include ltstdiohgt int mainint argc char argv print a greeting printfquotGood eveningnquot return 0 goodevening Good evening Breaking down the code 0 include ltstdiohgt Include the contents of the file stdioh Case sensitive lower case only No semicolon at the end of line 0 int main The OS calls this function when the program starts running printfformatstring argl Prints out a string specified by the format string and the arguments formatstring Composed of ordinary characters not Copied unchanged into the output Conversion specifications start with Fetches one or more arguments For example 0 char c 0 char 5 0 int d 0 float f For more details man 3 printf C Preprocessor define CS367 Computer Systems amp Programmingnquot int mainint argc char argv printfC5367 return 0 After the preprocessor gcc E int mainint argc char argv printfquotComputer Systems amp Programmingnquot return 0 Conditional Compilation define CS367 int mainint argc char argv ifdef CS367 printfquotComputer Systems amp Programmingnquot else printfquotSome other classnquot endif return 0 After the preprocessor gcc E int mainint argc char argv printf Computer Systems amp Programmingmw return 0 Command Line Arguments 1 int mainint argc char argv argc Number of arguments including program name argv Array of Chars that is an array of c strings 7 argv0 program name 7 argv1 first argument 7 argvargc 1 last argument Command Line Arguments 2 include ltstdiohgt int mainint argc char argv int i printfquotd argumentsnquot argc fori 0 i lt argc i printfquot d snquot i argvi return 0 Command Line Arguments 3 cmdline Computer Systems and Programming 5 arguments 0 cmdline Computer Systems and anNH Programming Arrays 0 char foo80 An array of 80 characters sizeof foo 80 X sizeofchar 80 x1 80 bytes 0 int bar40 An array of 40 integers sizeof bar 40 X sizeofint 40gtlt4 160 bytes Structures Aggregate data include ltstdiohgt struct name charquot name 39n age lt no new FORGET the semicolon int mainint argc char argvll struct name bovik bovikname v39IIarry Bovikquot 5 bovikage printfquots is 96d years 01dnquot bovikname bovikage return 0 Pointers Pointers are variables that hold an address in memory That address contains another variable Memory layout and addresses Using Pointers 1 float f data variable float faddr pointer variable f faddr any oat 4300 4304 any address faddr ampf amp address operator f faddr 4300 4304 Pointers made easy 2 faddr 32 indirection operator f faddr 4300 4304 float g faddr indirection g is now 32 f 13 but g is still 32 f faddr 4300 4304 Function Parameters Function arguments are passed by value What is pass by value The called function is given a copy of the arguments What does this imply The called function can t alter a variable in the caller function but its private copy Three exam ples Example 1 swap1 void swapl int 3 int b Q Let x3 y4 after swap1xy int temp X y temp a a b b temp39 A2 X3 y4 Example 2 swap2 void swap2int a int b Q Let x3 y4 after int temp swap2ampxampy temp a X y a b b temp A2 X4 y3 Example 3 include ltstdiohgt int main int x scanf dnquot ampx printf dnquot x scanf Q Why using pointers in scanf A We need to assign the value to X Dynamic Memory Java manages memory for you C does not C requires the programmer to explicitly allocate and deallocate memory Unknown amounts of memory can be allocated dynamically during runtime with malloc and deallocated using free Not like Java NO new No garbage collection You ask for n bytes Not a highlevel request such as I d like an instance of class string malloc Alocates memory in the heap Lives between function invocations Example Allocate an integer oint iptr int mallocsizeofint Allocate a structure ostruct name nameptr struct name mallocsizeofstruct name CS 367 MachineLevel Programming ll Control Flow Topics I Condition Codes 0 Setting 0 Testing I Control Flow 0 lfthenelse o Varieties of Loops 0 Switch Statements lecture9ppt Condition Codes Single Bit Registers CF Carry Flag SF Sign Flag ZF Zero Flag OF Overflow Flag lmplicitly Set By Arithmetic Operations addl SrcDest Canalog t a b I CF set if carry out from most significant bit oUsed to detect unsigned overflow I ZF set if t I SF set if t lt 0 I OF set if two s complement overflow agt0 ampamp bgt0 ampamp tlt0 alt0 ampamp blt0 ampamp tgt0 Not Set by leal instruction 2 CS 367 Setting Condition Codes cont Explicit Setting by Compare Instruction cmpl Srcz Src1 I cmpl ba like computing ab without setting destination I CF set if carry out from most significant bit 0 Used for unsigned comparisons I ZF set if a I SF set if ab lt 0 I OF set if two s complement overflow agt0 ampamp blt0 ampamp a blt0 alt0 ampamp bgt0 ampamp a bgt0 3 CS 367 Setting Condition Codes cont Explicit Setting by Test instruction testl Sr02Src1 I Sets condition codes based on value of Src1 amp Scm 0 Useful to have one of the operands be a mask I testl ba like computing aampb without setting destination I ZF set when aampb I SF set when aampb lt 0 4 CS 367 Reading Condition Codes SetX Instructions I Set single byte based on combinations of condition codes SetX Condition Description sete ZF Equal lZero setne ZF NotEquallNotZen sets SF Nega ve setns SF Nonnega ve setg SFAOF ampZF Greater Signed setge SFAOF Greater or Equal Signed setl SFAOF Less Signed setle SFAOF IZF Less or Equal Signed seta CFampZF Above unsigned setb CF Below unsigned CS 367 Reading Condition Codes Cont SetX Instructions I Set single byte based on combinations of condition codes eax ah al I One of 8 addressable byte registers 96edx 96dh d1 0 Embedded within first 4 integer 0 Does not alter remaining 3 bytes 96ebx 96bh 9611 0 Typically use movzbl to finish job esi int gt int x int y edi return x gt y Body movl 12ebpeax eax y cmpl eax 8 ebp Compare x y 4 Note setg al a1 x gt y inve ed movzbl aleax Zero rest of eax cwde ng 6 CS 367 Jumping jX Instructions l Jump to different part of code depending on condition codes jX Condition Description jmp 1 Unconditional je ZF Equal I Zero jne ZF Not Equal I Not Zero js SF Nega ve jns SF Nonnegative jg SFAOF ampZF Greater Signed jge SFAOF Greater or Equal Signed jl SFAOF Less Signed jle SFAOF IZF Less or Equal Signed ja CFampZF Above unsigned jb CF Below unsigned CS 367 Conditional Branch Example int maxint x int y if x gt y return x else return39y L9 pushl ebp movl espebp movl 8ebpedx movl 12ebpeax cmpl eaxedx jle L9 movl edxeax movl ebpesp popl ebp ret 39 Set Up Body Fh sh CS 367 Conditional Branch Example Cont int rval int ok if ok goto done rval done return rval x lt y X int gotomaxint x int y I C allows goto as means of transferring control 0 Closer to machinelevel programming style I Generally considered bad coding style movl 8ebpedx movl 12ebpeax cmpl eaxedx jle L9 movl edxeax L9 lll edx x eax y x y if lt goto L9 eax X Skipped when x s y Done CS 367 DoWhile Loop Example C Code iota feet i Q iogt 23 E l 5 E 11i 8 273 5 x gel Goto Version int factgotoint x int result loop result x x x1 if x gt 1 goto loop return result 1 I Use backward branch to continue looping I Only take branch when while condition holds 10 CS 367 DoWhile Loop Compilation Goto Version int factgoto int x int result 1 loop result x x x1 if x gt 1 goto loop return result Registers edx x eax result 11 Assembly factgoto pushl ebp Setup movl espebp Setup movl 1eax eax 1 movl 8ebpedx edx x L11 imull edxeax result x decl edx x cmpl 1edx Compare x 1 jg L11 if gt goto loop movl ebpesp Finish popl ebp Finish ret Finish C8367 General DoWhile Translation Goto Version C Code loop Body if Test goto loop I Body can be any C statement oTypically compound statement Statement1 Statemen 1 2 Statementquot I Testis expression returning integer 0 interpreted as false 12 0 interpreted as true CS 367 iut feet vii iutlzg Lo Example 1 First Goto Version int factwhilegoto intx int result 1 loop if x gt 1 goto done result x x xl goto loop done return result I Is this code equivalent to the dowhile version I Must jump out of loop if test fails 13 CS 367 All gt 1 g quot 0 0 4 quotJPquot 225 57 returu result I Uses same inner loop as dowhile version I Guards loop entry with extra test 14 while Lo Translatin Second Goto Version int factwhilegot02 intx int result 1 if x gt 1 goto done loop result x xi x 1 if x gt 1 goto loop done return result CS 367 General Translation DoWhile Version gt G t vers39on if Test jg 7 M goto done ltg7lt gtt 1 GOP Body if Test goto loop done 15 CS 367 E e i i C 397 I L Algorithm I Exploit property that p 190 2191 4192 zit1191 I Gives xP z0 z12 z2 22 zn1222 zi1 whenpi0 H J zi x when pl 1 n 1 times I Complexity Olog p 16 CS 367 iwr Comutatin 5 iiz t 9155 quot21 392 v Luv 1 1 9 9 81 9 1 6561 43046721 Ol NL O 17 CS 367 Exampm General Form Init Test Update 18 CS 367 iiForlle EEWhilell For Version While Version 39 while Test Body Update Goto Version In if Test goto done loop Body Update if Test goto loop done 19 CS 367 For Loop Compilation GOtO vers39on result 1 Init if p 0 if Tbsn goto dbne gOtO done loop loop gt if p amp 0x1 Bbdy result X Update x i x if Test P p1 goto loop if p 0 done goto loop done Init Test Bady Update 20 CS 367 1O Switch Stateme nt Implementation Options I Series of conditionals 0 Good if few cases 0 Slow if many I Jump Table 0 Lookup branch target 0 Avoids conditionals a Possible when cases are small integer constants I GCC 0 Picks one based on case structure I Bug in example code 0 No default given 21 CS 367 Switch Form Jump Table Jump Targets j tab TargO T argo Targl Targ2 Targl39 Targn1 Targ2 Approx Translation 2 target JTabIop 0 goto target Targn39l 22 CS 367 11 hf Branching Possibilities typegsglt m m 0 MQEEQ M m gg DEV MQDE swag hag E bl g 3 unparsesymbol pushl ebp movl espebp movl 8ebpeax cmpl 5eax Setup ja L49 jmp L57eax4 23 nt 39l Enumerated Values ADD 0 MULT 1 MINUS 2 DIV 3 MOD 4 BAD 5 Setup Setup eax op Compare op 5 If gt goto done goto Tableop CS 367 Assemly Setup Explanation Symbolic Labels I Labels of form LXX translated into addresses by assembler Table Structure I Each target requires 4 bytes I Base address at L57 Jumping jmp L49 I Jump target is denoted by label L49 jmp L57eax4 I Start of jump table denoted by label L57 I Register eax holds op I Must scale by factor of 4 to get offset into table I Fetch target from effective Address L57 op4 24 CS 367 12 Jump Table Table Contents Targets amp Completion section rodata L511 align 4 movl 43eax 39 L57 jmp L49 long L51Op 0 L521 1ong L52op 1 movl 42eax 39 long L53 Op 2 jmp L49 long L54 Op 3 L53 1ong L55op 4 movl 45eax 39 long L56 Op 5 jmp L49 L54 Enumerated Values movl 47eax rr ADD 0 jmp L49 MULT 1 L55 MINUS 2 movl 37eax DIV 3 jmp L49 MOD 4 L56 BAD 5 movl 63eax Fall Through to L49 25 CS 367 Switch Statement Completion L49 Done movl ebpesp Finish popl ebp Finish ret Finish Puzzle I What value returned when op is invalid Answer I Register eax set to op at beginning of procedure I This becomes the returned value Advantage of Jump Table I Can do kway branch in 01 operations 26 cs 367 13 Object Code Setup I Label L49 becomes address 0x804875c I Label L57 becomes address 0x8048ch 08048718 ltunparsesymbolgt 804871855 pushl ebp 804871989 e5 movl espebp 804871b8b 45 08 movl 0x8ebpeax 804871e83 f8 05 cmpl 0x5eax 804872177 39 ja 804875c ltunparsesymbol0x44gt 8048723ff 24 85 00 8b jmp 0x8048cheax4 27 CS 367 Object Code cont Jump Table I Doesn t show up in disassembled code I Can inspect using GDB gdb codeexamples gdb x6xw 0x8048ch o Eamine hexadecimal format LIords 4bytes each 0 Use command help x to get format documentation 0x8048ch ltfini32gt 0x08048730 0x08048737 0x08048740 0x08048747 0x08048750 0x08048757 28 CS 367 14 Extracting Jump Table from Binary Jump Table Stored in Read Only Data Segment rodata I Various fixed values needed by your code Can examine with objdump objdump codeexamples s se0tionrodata I Show everything in indicated segment Hard to read I Jump table entries shown with reversed byte ordering Contents of section rodata 8048b00 30870408 37870408 40870408 47870408 07G 8048de 50870408 57870408 46616374 28256429 PWFa0td 8048be0 203d2025 60640a00 43686172 203d2025 1dChar I Eg 30870408 really means 0x08048730 29 CS 367 Disassembled Targets 8048730b8 2b 00 00 00 movl 0x2beax 8048735eb 25 jmp 8048750 ltunparsesymbol0x44gt 8048737b8 2a 00 00 00 movl 0x2aeax 804873ceb 1e jmp 8048750 ltunparsesymbol0x44gt 804873e89 f6 movl esiesi 8048740b8 2d 00 00 00 movl 0x2deax 8048745eb 15 jmp 8048750 ltunparsesymbol0x44gt 8048747b8 2f 00 00 00 movl 0x2feax 8048740eb 0e jmp 8048750 ltunparsesymbol0x44gt 804874e89 f6 movl esiesi 8048750b8 25 00 00 00 movl 0x25eax 8048755eb 05 jmp 8048750 ltunparsesymbol0x44gt 8048757b8 3f 00 00 00 movl 0x3feax I movl esi esi does nothing I Inserted to align instructions for better cache performance 30 CS 367 15 aemlwe Tarets 8048730b8 2b 00 00 00 movl 8048735eb 25 jmp Entry 8048737b8 2a 00 00 00 movl I 804873e89 f6 movl OXOB048737 394quot8048740b8 2d 00 00 00 movl 0X 8048740 8048745eb 15 jmp 0x08048747 8048747b8 2f 00 00 00 movl 0x08048750 804874ceb 0e jmp 0x08048757 804874e89 f6 movl 8048750b8 25 00 00 00 movl 8048755eb 05 jmp 8048757b8 3f 00 00 00 movl 31 C8367 I Not practical to use jump table 0 Would require 1000 entries I Obvious translation into ifthenelse would have max of 9 tests f L r r 19 9 Ci 0 W 3 t Pr Sf t J 1 Q quot1 o 1 13953 u it y a 9 quot30 47s I x it J C911 quot7 811 3 1 1 1 0 50 32 CS 367 16 Sparse Switch Code movl 8ebp eax get x I Compares xto possible cmpl 444 96eax x 444 case vaues g 26 I Jumps different places cmpl 11196eax W111 depending on outcomes je L5 jg L17 testl eaxeax x0 L5 movl 1eax 3e L4 jmp L19 jmp L14 L6 movl 2eax jmp L19 L7 movl 3eax jmp L19 L8 movl 4eax jmp L19 33 Sparse Switch Code Structure I Organizes cases as binary tree I Logarithmic performance 34 CS 367 17 CS 367 Floating Point Topics I IEEE Floating Point Standard I Rounding I Floating Point Operations I Mathematical properties Floating Point Puzzles I For each of the following C expressions either 0 Argue that it is true for all argument values 0 Explain why not true x intfloat x int Xi mi x 1ntdouble x f f float double f i39 m d float d f f Assume neither 23 230 dnorfisNaN d lt 00 3 d2 lt 00 dgtf 3 f gt d d d gt 00 df d CS 367 IEEE Floating Point IEEE Standard 754 I Established in 1985 as uniform standard for floating point arithmetic 0 Before that many idiosyncratic formats I Supported by all major CPUs Driven by Numerical Concerns I Nice standards for rounding overflow underflow I Hard to make go fast 0 Numerical analysts predominated over hardware types in defining standard 3 CS 367 Fractional Binary Numbers 21 2i 1 Representation I Bits to right of binary point represent fractional powers of 2 I Represents rational number i k 2 bk 2 k j 4 CS 367 Frac Binary Number Examples Value Representation 534 101 112 278 10 1112 6364 01111112 Observations I Divide by 2 by shifting right I Multiply by 2 by shifting left I Numbers of form 01111112 just below 10 012 14 18 12quot gt 10 oUse notation 10 e 5 CS 367 Representable Numbers Limitation I Can only exactly represent numbers of the form x2quot I Other numbers have repeating bit representations Value Representation 13 001010101010112 15 0001100110011001112 110 0000110011001100112 6 08367 Floating Point Representation Numerical Form I 5 M 2E oSign bit 5 determines whether number is negative or positive oSignificand M normally a fractional value in range 1020 oExponent E weights value by power of two Encoding I I frac I MSB is sign bit I exp field encodes E I frac field encodes M 7 CS 367 Floating Point Precisions Encoding I MSB is sign bit I exp field encodes E I frac field encodes M Sizes I Single precision 8 exp bits 23 frac bits 32 bits total I Double precision 11 exp bits 52 frac bits 64 bits total I Extended precision 15 exp bits 63 frac bits oOnly found in Intelcompatible machines oStored in 80 bits 1 bit wasted 8 CS 367 Normalized Numeric Values Condition l exp 0000 and exp 6 1111 Exponent coded as biased value E Exp Bias oExp unsigned value denoted by exp oBias Bias value Single precision 127 Exp 1254 E 126127 Double precision 1023 Exp 12046 E 10221023 in general Bias 29391 1 where e is number of exponent bits Significand coded with implied leading 1 M 1 xxxx2 O bits of frac OMinimum when OOOO M 10 OMaximum when 1111 M 20 e oGet extra leading bit for free 9 CS 367 Normalized Encoding Example Value Float F 152130 l152131o 111O11O11O11O12 111O11O11O11O12X213 Significand M 111011011011012 frac 110110110110100000000002 Exponent E 13 Bias 127 EXp 140 100011002 Floating Point Representation Class 02 Hex 4 6 6 D B 4 0 0 Binary 0100 0110 0110 1101 1011 0100 0000 0000 140 100 0110 0 15213 1110 1101 1011 01 10 CS 367 Denormalized Values Condition l exp 0000 Value I Exponent value E Bias 1 I Significand value M 0 xxxx2 O xxxx bits of frac Cases l exp 0000 frac 0000 o Represents value 0 0 Note that have distinct values 0 and 0 l exp 0000 frac at 0000 0 Numbers very close to 00 0 Lose precision as get smaller 0 Gradual underflow Special Values Condition l exp 1111 Cases l exp 1111 frac 0000 O Represents value 00 infinity 0 Operation that overflows 0 Both positive and negative 0 Eg 1000 10 00 00 10 00 00 l exp 1111 frac 6 0000 o NotaNumberNaN o Represents case when no numeric value can be determined 0 Egsqrt 1oo oo 12 CS 367 Summary of Floating Point Real Number Encodings Normalized lDenorm Denorm Normalized 13 CS 367 Tiny Floating Point Example 8bit Floating Point Representation I the sign bit is in the most significant bit I the next four bits are the exponent with a bias of 7 I the last three bits are the frac 0 Same General Form as IEEE Format I normalized denormalized I representation of 0 NaN infinity 76 32 o Isl exp frac 14 CS 367 Values Related to the Exponent Exp exp E 2E 0 0000 6 164 denorms 1 0001 6 164 2 0010 5 132 3 0011 4 116 4 0100 3 18 5 0101 2 14 6 0110 1 12 7 0111 0 1 8 1000 1 2 9 1001 2 4 10 1010 3 8 11 1011 4 16 12 1100 5 32 13 1101 6 64 14 1110 7 128 15 1111 na inf NaN 15 08367 Dynamic Range 3 exp frac E Value 0 0000 000 6 0 0 0000 001 6 18164 1512 Closestto zero Denormalized 0 0000 010 6 28164 2512 numbers 0 0000 110 6 68164 6512 0 0000 111 6 78164 7512 4largestden0rm 0 0001 000 6 88164 8512 4snwmestnonn 0 0001 001 6 98164 9512 0 0110 110 1 14812 1416 0 0110 111 1 15812 1516 C390393tt01b9390W N a zed 0 0111 000 0 881 1 numbers 0 0111 001 o 981 98 Closestt01ab0ve 0 0111 010 0 1081 108 0 1110 110 7 148128 224 0 1110 111 7 158128 240 IargeStnorm 0 1111 000 na inf 16 CS 367 Distribution of Values 6bit lEEElike format I e 3 exponent bits I f 2 fraction bits I Bias is 3 Notice how the distribution gets denser toward zero l A A A A H A Wi A H H A A l 15 1o 5 0 5 10 15 o Denormalized A Normalized l In nity 17 cs 367 Distribution of Values closeup View 6bit lEEElike format I e 3 exponent bits I f 2 fraction bits I Bias is 3 A A A A A A A A A O H Q H O A A A A A A A A A 1 O5 O 05 1 o Denormalized A Normalized Infinity 18 CS 367 Interesting Numbers Description exp frac Zero OOOO OOOO Smallest Pos Denorm OOOO OOO1 I Single as 14 X10 45 I Double z 49 X10 324 Largest Denormalized OOOO 1111 I Single as 118 X10 38 I Double z 22 X10 308 Smallest Pos Normalized OOO1 OOOO I Just larger than largest denormalized One O111 OOOO Largest Normalized 1110 1111 I Single as 34 X 1038 I Double z 18 X 10308 19 Numeric Value 00 2 2352 X 2 1261022 10 8 X 2 1261022 10 X 2 12a1022 10 20 8 X 21271023 CS 367 Special Properties of Encoding FP Zero Same as Integer Zero Anmmo Can Almost Use Unsigned Integer Comparison Must first compare sign bits Must consider 0 0 NaNs problematic 0 Will be greater than any other values 0 What should comparison yield Otherwise OK 0 Denorm vs normalized 0 Normalized vs infinity 20 CS 367 10 Floating Point Operations Conceptual View I First compute exact result I Make it fit into desired precision oPossibly overflow if exponent too large oPossibly round to fit into frac Rounding Modes illustrate with rounding 140 160 150 250 150 I Zero 1 1 1 2 1 I Round down 00 1 1 1 2 2 I Round up oo 2 2 2 3 1 I Nearest Even default 1 2 2 2 2 Note 1 Round down rounded result is close to but no greater than true result 2 Round up rounded result is close to but no less than true result 21 cs 367 Closer Look at RoundToEven Default Rounding Mode I Hard to get any other kind without dropping into assembly I All others are statistically biased oSum of set of positive numbers will consistently be over or under estimated Applying to Other Decimal Places Bit Positions I When exactly halfway between two possible values oRound so that least significant digit is even I Eg round to nearest hundredth 12349999 123 Less than half way 12350001 124 Greater than half way 12350000 124 Half way round up 12450000 124 Half way round down 22 CS 367 11 Rounding Binary Numbers Binary Fractional Numbers I Even when least significant bit is 0 I Half way when bits to right of rounding position 1002 Examples I Round to nearest 14 2 bits right of binary point Value Binary Rounded Action Rounded Value 2332 10000112 10002 lt12 down 2 2316 10001102 10012 gt12 up 214 278 10111002 11002 12 up 3 258 10101002 10102 12 down 212 23 CS 367 FP Multiplication Operands 481 M1 2E1 182 M2 2E2 Exact Result 15 M 2E I Sign s 31quot 52 I Significand M M1 M2 I Exponent E E1 E2 Fixing I If M 2 2 shift M right increment E I If E out of range overflow I Round M to fit frac precision Implementation I Biggest chore is multiplying significands 24 cs 367 12 FP Addition Operands 1 M1 257 4 E1 E2 gt 152 M2 2E2 I 1s1 M1 I I Assume E1 gt E2 I 482 M2 Exact Result 15 M 2E 1SM l I Sign s significand M 0 Result of signed align amp add I Exponent E E1 Fixing I If M 2 2 shift M right increment E I if Mlt 1 shift M left k positions decrement E by k I Overflow if E out of range I Round M to fit frac precision 25 cs 367 Mathematical Properties of FF Add Compare to those of Abelian Group I Closed under addition YES oBut may generate infinity or NaN I Commutative YES I Associative NO oOverflow and inexactness of rounding I 0 is additive identity YES I Every element has additive inverse ALMOST oExcept for infinities amp NaNs Monotonicity I a 2 b gt 30 2 b0 ALMOST oExcept for infinities amp NaNs 26 CS 367 13 Math Properties of FF Mult Compare to Commutative Ring I Closed under multiplication YES oBut may generate infinity or NaN I Multiplication Commutative YES I Multiplication is Associative NO oPossibility of overflow inexactness of rounding I 1 is multiplicative identity YES I Multiplication distributes over addition NO oPossibility of overflow inexactness of rounding Monotonicity Ia2bamp0202a02b0 ALMOST oExcept for infinities amp NaNs 27 CS 367 Floating Point in C C Guarantees Two Levels float single precision double double precision Conversions I Casting between int float and double changes numeric values I Double or float to int c Truncates fractional part 0 Like rounding toward zero 0 Not defined when out of range Generally saturates to TMin or TMax I int to double 0 Exact conversion as long as int has S 53 bit word size I int to float 0 Will round according to rounding mode 28 CS 367 14 Ans t Floating Point Puzzles float f m double d 7 N intfloat x intdouble x floatdouble f float d l39hQl39hN f 23 230 d lt 00 gtd2 lt 00 d gt f gt f gt d d d gt 00 dfd 29 Assume neither d nor f is NAN No 24 bit significand Yes 53 bit significand Yes increases precision No loses precision Yes Just change sign bit No 23 Yes Yes Yes No Not associative CS 367 Ariane 5 I Exploded 37 seconds after liftoff I Cargo worth 500 million Why I Computed horizontal velocity as floating point number I Converted to 16bit integer I Worked OK for Ariane 4 I Overflowed for Ariane 5 0 Used same software 30 CS 367 15 CS 367 Linking Topics I Static linking I Object files I Static libraries I Loading I Dynamic linking of shared libraries 1ecture13 ppt Linker Puzzles 2 CS 367 A Simplistic Program Translation Scheme m c A 50 source file Binary executable object file P memory image on disk Problems Efficiency small change requires complete recompilation Modularity hard to share common functions eg printf Solution Static linker or linker 3 CS 367 A Better Scheme Using a Linker Separately compiled relocatable object files Executable object file contains code P and data for all functions defined in m c and a c 4 CS 367 Translating the Example Program Compiler driver coordinates all steps in the translation and linking process I Typically included with each compilation system eg gcc I lnvokes preprocessor cpp compiler cc1 assembler as and linker 1d I Passes command line arguments to appropriate phases Example create executable p from m c and a c 5 CS 367 What Does a Linker Do Merges object files I Merges multiple relocatable 0 object files into a single executable object file that can loaded and executed by the loader Resolves external references I As part of the merging process resolves external references 0 External reference reference to a symbol defined in another obiect file Relocates symbols I Relocates symbols from their relative locations in the 0 files to new absolute positions in the executable I Updates all references to these symbols to reflect their new positions 0 References can be in either code or data gtgt code a reference to symbol a gtgt data int xpampx reference to symbol x 6 CS 367 Why Linkers Modularity I Program can be written as a collection of smaller source files rather than one monolithic mass I Can build libraries of common functions more on this later 0 eg Math library standard C library Efficiency I Time 0 Change one source file compile and then relink o No need to recompile other source files I Space 0 Libraries of common functions can be aggregated into a single file 0 Yet executable files and running memory images contain only code for the functions they actually use 7 CS 367 Executable and Linkable Format ELF Standard binary format for object files Derives from ATampT System V Unix I Later adopted by BSD Unix variants and Linux One unified format for I Relocatable object files o I Executable object files I Shared object files so Generic name ELF binaries Better support for shared libraries than old a out formats 8 CS 367 ELF Object File Format Elf header I Magic number type 0 exec so machine byte ordering etc Program header table I Page size virtual addresses memory segments sections segment sizes text section I Code data section I Initialized static data bss section I Uninitialized static data I Block Started by Symbol I Better Save Space I Has section header but occupies no space 9 CS 367 ELF Object File Format cont symtab section Symbol table Procedure and static variable names Section names and locations rel text section Relocation info for text section I Addresses of instructions that will need to be modified in the executable Instructions for modifying rel data section Relocation info for data section I Addresses of pointer data that will need to be modified in the merged executable debug section I Info for symbolic debugging gcc g 10 CS 367 Example C Program 1 1 CS 367 Merging Relocatable Object Files into an Executable Object File Relocatable Object Files Executable Object File headers rem l l text int e 7 int gp ampe system ata 39 data l 7 1 int x 15 ao int eb ampe 44f4747f7fifff bSS 12 CS 367 Relocating Symbols and Resolving Extern Def of local symbol e Ref to external symbol exit defined in libc so 13 al References Symbols are lexical entities that name functions and variables Each symbol has a value typically a memory address Code consists of symbol definitions and references References can be either local or external m C Ref to external symbol e Ref to external 9P YglrlIZOIS symbol a Def of y Refs of local local 5 mbols symbol a y eP Ixrl s 367 mo Relocation Info mo source objdump 14 CS 367 a 0 Relocation Info text 15 CS 367 ac 16 CS 367 Executable After Relocation and External Reference Resolution text Executable After Relocation and External Reference Resolutiondata mc CS 367 Strong and Weak Symbols Program symbols are either strong or weak I strong procedures and initialized globals I weak uninitialized globals 19 CS 367 Linker s Symbol Rules Rule 1 A strong symbol can only appear once Rule 2 A weak symbol can be overridden by a strong symbol of the same name I references to the weak symbol resolve to the strong symbol Rule 3 If there are multiple weak symbols the linker can pick an arbitrary one 20 CS 367 10 Linker Puzzles m Link time error two strong symbols p1 References to x will refer to the same uninitialized int Is this what you really want Writes to x in p2 might overwrite y Evil Writes to x in p2 will overwrite y Nasty References to x will refer to the same initialized variable Nightmare scenario two identical weak structs compiled by different compilers with different alignment rules 21 CS 367 Packaging Commonly Used Func ons How to package functions commonly used by programmers I Math lO memory management string manipulation etc Awkward given the linker framework so far I Option 1 Put all functions in a single source file 0 Programmers link big object file into their programs 0 Space and time inefficient I Option 2 Put each function in a separate source file 0 Programmers explicitly link appropriate binaries into their programs 0 More efficient but burdensome on the programmer Solution static libraries a archive files I Concatenate related relocatable object files into a single file with an index called an archive I Enhance linker so that it tries to resolve unresolved external references by looking for the symbols in one or more archives I If an archive member file resolves reference link into executable 22 CS 367 11 Static Libraries archives pl 0 p2 c static library archive of 0 p1 p2 o libc a relocatable object files concatenated into one file executable object file only contains code P and data for libc functions that are called from p1 c and p2 c Further improves modularity and efficiency by packaging commonly used functions eg C standard library libc math library libm Linker selectively only the 0 files in the archive that are actually needed by the program CS 367 Creating Static Libraries atoi c printf 0 random 0 atoi o printf 0 random 0 atoi o printf o random 0 libc a 0 standard library Archiver allows incremental updates Recompile function that changes and replace 0 file in archive 24 CS 367 Commonly Used Libraries libc a the C standard library I 8 MB archive of 900 object files I O memory allocation signal handling string handling data and time random numbers integer math libm a the C math library I 1 MB archive of 226 object files I floating point math sin cos tan log exp sqrt Using Static Libraries Linker s algorithm for resolving external references I Scan 0 files and a files in the command line order I During the scan keep a list of the current unresolved references I As each new 0 or a file obj is encountered try to resolve each unresolved reference in the list against the symbols in obj I If any entries in the unresolved list at end of scan then error Problem I Command line order matters I Moral put libraries at the end of the command line 26 CS 367 13 Loading Executable Binaries Executable object file for example program p ELF header Program header table Process image required for executables inquot and shared I 0x080483eo segments Virtual addr 0x08048494 symtab reltext data segment 0x0804a010 reldata initialized rw debug Section header table x 8 4a3b required for relocatables 27 CS 367 Shared Libraries Static libraries have the following disadvantages I Potential for duplicating lots of common code in the executable files on a filesystem o eg every C program needs the standard C library I Potential for duplicating lots of code in the virtual memory space of many processes I Minor bug fixes of system libraries require each application to explicitly relink Solution I Shared Iibrariesdynamic link libraries DLLs whose members are dynamically loaded into memory and linked into an application at runtime 0 Dynamic linking can occur when executable is first loaded and run Common case for Linux handled automatically by ld linux so 0 Dynamic linking can also occur after program has begun ln Linux this is done explicitly by user with dlopen Basis for HighPerformance Web Servers 0 Shared library routines can be shared by multiple processes 28 CS 367 14 Programming in C in a UNIX environment Software Development Lifecycle Understand the requirements Develop the algorithmapproach Write the code Debug the code Test the code Iterate until you get it right Programming Tools Several Integrated Development Environments lDEs Visual Studio Netbeans Eclipse jGRASP lDEs are great but there is a learning curve But you don t need to use an IDE You need a Text Editor use vi or emacs or Edit not PICO Compiler use gcc in conjunction with the Make utility Debugger use gdblnsight Become familiar and comfortable with UNIX See useful links on class web page Links to several tutorials on UNIX gdb make emacs vi etc Program with multiple files include ltstdiohgt include mypgmh void mainvoid mYProc hwc Library headers Standard Userdefined include ltstdiohgt include mypgmh void myprocvoid mydata2 some code mypgmc void myprocvoid int mydata mypgmh Externs include ltstdiohgt extern char user21ine 20 global variable defined in another file char userlline30 global for this file void dummyvoid void mainvoid char userlline20 different from earlier userlline30 restricted to this func void dummy extern char userlline the global userlline30 Example to show separate compilation and make Consider a program which is split into several files with each function in a separate file Note this is just for illustrating the use of make Defsh Mainc ReadLinec WordCountc ExternVarsh PrintLinec UpdateCountsc Example cont d ExternVarsh extern char LineMaxLine extern int NCharsNWordsNLinesLineLength Defsh define MaxLine 200 Mainc introductory C program implements a subset of the Unix wc command reports character word and line counts in this version the quotfilequot is read from the standard input include quotDefshquot extern int ReadLineWordCount char LineMaxLine one line from the file int NChars O number of characters seen so far NWords O number of words seen so far NLines O number of lines seen so far LineLength length of the current line main while 1 LineLength ReadLine if LineLength 0 break UpdateCounts printfquot d dnquotNCharsNWordsNLines PrintLinec include quotDefshquot include quotExternVarshquot PrintLine Code not shown m Readlinec include quotDefshquot include quotExternVarshquot int ReadLine Code not shown m WordCountc include quotDefshquot include quotExternVarshquot int WordCount Code not shown m UpdateCountsc include quotDefshquot include quotExternVarshquot extern int WordCount UpdateCounts Code not shown m Makefile Makefile 3 WC Maino ReadLineo WordCounto UpdateCountso PrintLineo 4 cc g 0 WC Maino ReadLineo WordCounto UpdateCountso PrintLineo 5 6 Maino Mainc Defsh ExternVarsh notice the space after N 7 cc g c Mainc 8 9 ReadLineo ReadLinec Defsh ExternVarsh 10 cc g c ReadLinec this line must starts with a tab 11 12 WordCounto WordCountc Defsh ExternVarsh 13 cc g c WordCountc 14 15 UpdateCountso UpdateCountsc Defsh ExternVarsh 16 cc g c UpdateCountsc 17 18 PrintLineo PrintLinec Defsh ExternVarsh 19 cc g c PrintLinec Note The makefile does not really have line numbers as shown 10 Example using getline include ltstdiohgt int main int b tesread int n ytes 100 char m string puts quotP ease enter a line of textquot These 2 lines are the heart of the program mystring char malloc nbytes 1 bytesread getline ampmystring ampnbytes stdin if bytes read 1 puts quotERROFHquot else puts 39You typedf39 puts mystrng return 0 11 CS 367 Spring 2008 Optional Lab 4 Assignment Writing Your Own Unix Shell Due Last class a December 4 at 1030am No late submissinns will be Introduction The purpose of this assignment is to become more familiar with the concepts of process control and signaling You ll do this by writing a simple Unix shell program that supports job control Logistics This is NOT a group project No collaboration between students is permitted The only handiinquot will be electronic This assignment is optional not extra If you choose to submit this assignment it will count like any other lab Don t submit this assignment if it will lower your overall course grade Hand Out Instructions This project requires you to work on a Linux system Start by downloading the file shlabihandouttar to the protected directory the lab directory in which you plan to do your work You can work on Zeus Then do the following Type the command tar xvf shiabihandouttar to expand the tar file Type the command make to compile and link some test routines Type your name and login ID in the header comment at the top of tshc Looking at the tshctiny shell file you will see that it contains a functional skeleton of a simple Unix shell To help you get started we have already implemented the less interesting functions Your assignment is to complete the remaining empty functions listed below As a sanity check for you we ve listed the approximate number of lines of code for each of these functions in our reference solution which includes lots of comments eyal Main routine that parses and interprets the command line 70 lines builtinicmd Recognizes and interprets the builtiin commands quit fg bg and jobs 25 linem doibgfg Tmplements the bg and fg builtiin commands 50 lines waitfg Waits for a foreground job to complete 20 lines sigchldihandler Catches STGCHTLD signals 80 lines sigintihandler Catches STGTNT ctrlic signals 15 lines sigtstpihandler Catches STGTSTP ctrliz signals 15 lines Each time you modify your tshc file type make to recompile it To run your shell type tsh on the command line unixgt tsh tshgt type commands to your shell here General Overview of Unix Shells A shell is an interactive commandiline interpreter that runs programs on behalf of the user A shell repeatedly prints a prompt waits for a command line to be entered on stdin and then carries out some action as directed by the contents of the command The command line is a sequence of ASCII text words delimited by whitespace The first word in the command line is either the name of a builtiin command or the pathname of an executable file The remaining words are commandiline arguments If the first word is a builtiin command the shell immediately executes the command in the current process Otherwise the word is assumed to be the pathname of an executable program In this case the shell forks a child process then loads and runs the program in the context of the child The child processes created as a result of interpreting a single command line are known collectively as a job In general a job can consist of multiple child processes connected by Unix pipes If the command line ends with an ampersand quotampquot then the job runs in the background which means that the shell does not wait for the job to terminate before printing the prompt and waiting for the next command line Otherwise the job runs in the foreground which means that the shell waits for the job to terminate before waiting for the next command line Thus at any point in time at most one job can be running in the foreground However an arbitrary number of jobs can run in the background For example typing the command line tshgt jobs causes the shell to execute the builtiin jobs command Typing the command line tshgt binls fl 7d runs the is program in the foreground By convention the shell ensures that when the is program begins executing its main routine int mainint argc char argv the argc and argv arguments have the following values argc argvO argvl argv2 Alternatively typing the command line tshgt binls fl 7d amp runs the is program in the background Unix shells support the notion of job control which allows users to move jobs back and forth between background and foreground and to change the process state running stopped or terminated of the processes in a job Typing ctrl7c causes a STGTNT signal to be delivered to each process in the foreground job The default action for STGTNT is to terminate the process Similarly typing ctrl7z causes a STGTSTP signal to be delivered to each process in the foreground job The default action for STGTSTP is to place a process in the stopped state where it remains until it is awakened by the receipt of a STGCONT signal Unix shells also provide various built7in commands that support job control For example jobs List the running and stopped background jobs bg ltjobgt Change a stopped background job to a running background job fg ltjobgt Change a stopped or running background job to a running in the foreground kill ltjobgt Terminate a job The tsh Specification Your tsh shell should have the following features The prompt should be the string tshgt quot The command line typed by the user should consist of a name and zero or more arguments all separated by one or more spaces Tf name is a built7in command then tsh should handle it immediately and wait for the next command line Otherwise tsh should assume that name is the path of an executable file which it loads and runs in the context of an initial child process In this context the term job refers to this initial child process tsh need not support pipes l or 10 redirection ltand gt Typing ctrl7c ctrl7z should cause a STGTNT STGTSTP signal to be sent to the current foreground job as well as any descendents of that job eg any child processes that it forked If there is no foreground job then the signal should have no effect If the command line ends with an ampersand amp then tsh should run the job in the background Otherwise it should run the job in the foreground Each job can be identified by either a process ID PTD or a job TD JTDL which is a positive integer assigned by tsh JTDs should be denoted on the command line by the prefix For example 5quot denotes JTD 5 and 5quot denotes PTD 5 We have provided you with all of the routines you need for manipulating the job listJ tsh should support the following built7in commands 7 The quit command terminates the shell 7 The jobs command lists all background jobs The bg ltjobgt command restarts ltjobgt by sending it a STGCONT signal and then runs it in the background The ltjobgt argument can be either a PTD or a JTD 7 The fg ltjobgt command restarts ltjobgt by sending it a STGCONT signal and then runs it in the foreground The ltjobgt argument can be either a PTD or a JTD tsh should reap all of its zombie children If any job terminates because it receives a signal that it didn t catch then tsh should recognize this event and print a message with the job s PTD and a description of the offending signal Checking Your Work We have provided some tools to help you check your work Reference solution The Linux executable tshref is the reference solution for the shell Run this program to resolve any questions you have about how your shell should behave Your shell should emit output that is identical to the reference solution except for PTDs of course which change from run to run Shell driver The sdriverpl program executes a shell as a child process sends it commands and signals as directed by a trace file and captures and displays the output from the shell Use the 7h argument to find out the usage of sdriverpl unixgt sdriverpl 7h Usage sdriverpl 7hv it lttracegt is ltshellproggt 7a ltargsgt Options 7h Print this message 7v Be more verbose it lttracegt Trace file is ltshellgt Shell program to test 7a ltargsgt Shell arguments 7g Generate output for autograder We have also provided 16 trace files traceOlil6txt that you will use in conjunction with the shell driver to test the correctness of your shell The lowerenumbered trace files do very simple tests and the higherinumbered tests do more complicated tests You can run the shell driver on your shell using trace file traceOltxt for instance by typing unixgt sdriverpl it traceOltxt is tsh 7a quotpquot the 7a quotpquot argument tells your shell not to emit a prompt or unixgt make testOl Similarly to compare your result with the reference shell you can run the trace driver on the reference shell by typing unixgt sdriverpl it traceOltxt is tshref 7a quotpquot unixgt make rtestOl For your reference tshrefout gives the output of the reference solution on all races This might be more convenient for you than manually running the shell driver on all trace files The nice thing about the trace files is that they generate the same output you would have gotten had you run your shell interactively except for an initial comment that identifies the trace For example bassgt make testl5 sdriverpl it tracel5txt is tsh 7a quotpquot tracel5txt 7Putting it all together tshgt bogus bogus Command not found tshgt myspin Job 9721 terminated by signal 2 tshgt myspin 3 amp l 9723 myspin 3 amp tshgt myspin 4 amp 2 9725 myspin 4 amp tshgt jobs 1 9723 Running myspin 3 amp 2 9725 Running myspin 4 amp tshgt fg l Job 1 9723 stopped by signal 20 tshgt jobs 1 9723 Stopped myspin 3 amp 2 9725 Running myspin 4 amp tshgt bg 3 l 9723 myspin 3 amp tshgt jobs 1 9723 Running myspin 3 amp 2 9725 Running myspin 4 amp tshgt fg l tshgt quit bassgt Hints Read every word of Chapter 8 Exceptional Control Flow in your textbook Use the trace files to guide the development of your shell Starting with traceOltxt make sure that your shell produces the identical output as the reference shell Then move on to trace file trace02txt and so on The waitpid kill fork execve setpgid and sigprocmask functions will come in very handy The WUNTRACED and WNOHANG options to waitpidwill also be useful When you implement your signal handlers be sure to send STGTNT and STGTSTP signals to the entire foreground process group using quotpidquot instead of quotpidquot in the argument to the kill function The sdriverpl program tests for this error One of the tricky parts of the assignment is deciding on the allocation of work between the waitfg and sigchldihandler functions We recommend the following approach 7 In waitfg use a busy loop around the sleep function 7 In sigchldihandler use exactly one call to waitpid While other solutions are possible such as calling waitpid in both waitfg and sigchldihandler these can be very confusing It is simpler to do all reaping in the handler
Are you sure you want to buy this material for
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'