CS 345 slide 257 Spring 20055 April 2005Allocation of Space for Local VariablesAssumption:space for a block’s variables is provided inan activation record (in the STACK).To calculate the offset from AR’s base for variablei,the compiler must know how much space is occupiedby variable0,…,variablei –1. Space for every variable is static— it cannot bechanged after compilation..How are variables’ space requirements computed?For Integers, Floats, Chars, Booleans, pointers, …:fixed #bytes eachFor Arrays:size (array [m..n] of T ) = (n–m+1) size(T )For Records:size (record N0:T0; … ;Nn:Tn)= ( i | 0i n : size(Ti))for Variant sections in records:size (case … of v0:T0 | … | vn:Tn end)= (max i | 0i n : size(Ti))CS 345 slide 258 Spring 20055 April 2005Example:program // globaltype R = record char c, int n;integer b; float x; pointer to char y;procedure p() int m[5], n; R a; double b;begin ... b ... y ... a.n ... m[2] ... n ...end p;procedure q() boolean f; R h; double r[10], m, n;begin... b ... x ... h.c ... m ... n ...... r[b] ...end q;begin... x ... b ... y ...end program.Assume that• offsets are given in bytes• basic data types’ space requirements (in bytes) areas follows:boolean, char: 1integer, float, pointer: 4double: 8CS 345 slide 259 Spring 20055 April 2005Step 1: Build a table for each block showing• the size of each variable declared in the block• the address(es) of each variable relative to itsblock’s activation record (AR)variable size addressesprogram:b4 0–3(global) x 4 4–7y 4 8–11procedure p: m 5*4 0–19n 4 20–23a 5 24–28 a.c 1 24–24 a.n 4 25–28b 8 29–36procedure q: f 1 0–0h 5 1–5 h.c 1 1–1 h.n 4 2–5r 10*8 6–85m 8 86–93n 8 94–101Java note: ARs contain only basic types; all others(records, arrays, …) are stored in the heap (ARscontain only pointers to them).CS 345 slide 260 Spring 20055 April 2005Step 2: Translate each variable reference into anactivation-record reference.• Each local reference is represented by a singlenumber (offset relative to base of current AR).• Each global reference is represented by a numbertagged G (offset relative to base of static storage)in program:x G 4bG 0y G 8in procedure p: b 29y G 8a.n 25m[2] 8 (= 0 + 2*4)n 20in procedure q: b G 0x G 4h.c 1m 86n 94r[b] 6+8*(G 0)A consequence of this allocation method: variables’sizes cannot vary during execution.How does C++ handle declarations intermixed withexecutable code?How does Java provide variable-size arrays?CS 345 slide 261 Spring 20055 April 2005Concurrency and Parallelism in ProgrammingNote: Sethi’s distinction:concurrency = potential parallelismis (regrettably) not standard in the literature.Process: a sequential computation • no parallelism • single threadConcurrent computations are often viewed assets of concurrent sequential processes.Concurrent processes can be independent, or theycan interact with one another.Modes of interaction:•communication via messages shared variables•synchronization: restrictions on ordering of eventsin different processes.Motivation for concurrent programming: to manage… • competition among processes for sharedresources • cooperation among processes working ondifferent parts of a computation.CS 345 slide 262 Spring 20055 April 2005Modes of Concurrent Programming• implicit synchronization by I/O Unix™ pipes functional composition• explicit synchronization by explicit constraintson interleavingImplicit Synchronization (example: Unix)process :: [char] [char]Process composition in Unix–shell notation:p0 | p1 | … | pk—a pipeline of producer/consumer processes.Each pi is a sequential program that• reads chars from stdin(Unix standard input stream)• writes chars to stdout(Unix standard output stream).When processes are pipelined, Unix• provides a buffer between each pair pi and pi+1• runs each process until…– its input buffer is emptyor– its output buffer is full.CS 345 slide 263 Spring 20055 April 2005Hence several processes (or coroutines) in a singlepipeline can be active simultaneously:• each pair pi and pi+1 run concurrently• each buffer is filled and emptied concurrently• first output can precede last inputpipi+1We can view each pi as a function:• input stream is the function’s argument• output stream is the function’s result.Sethi: The power of pipes is based on• standard I/O interface (i.e., [char])• a suitable collection of primitive processesExample: find a file’s duplicate lines• sort sorts a file’s lines• uniq -d produces one copy of each adjacentrepeated lineConcurrent shell program:sort | uniq -dCS 345 slide 264 Spring 20055 April 2005Sethi’s examples1. Give expressions’ values in English3 + 2 H S fiveThe program:bc | numberwhere bc :: [exp r ] [in t ]number :: [in t ] [wor d ]could be used keyboard-to-screen:bc | numberor file-to-file:bc <exprs | number >wordsThe latter is equivalent tobc <expr >tempnumber <temp >wordsNotes:• The “types” such as [expr] exist only in the mindof the programmer; as far as C and Unix are con-cerned, they’re all [char], and any other “typechecking” can be done only during execution.• for I/O to be interleaved (interactive), pipelineprocesses must be run (quasi-)
View Full Document
Unlocking...