Computer Time Scales 15 213 The course that gives CMU its Zip Microscopic Time Scale 1 Ghz Machine Integer Add FP Multiply FP Divide Time Measurement Feb 17 2004 1 ns 1 s 1 E 09 1 E 06 Keystroke Interrupt Handler Macroscopic Disk Access Screen Refresh Keystroke 1 ms Time seconds 1 E 03 1s 1 E 00 Topics Time scales Two Fundamental Time Scales Interval counting Cycle counters K best measurement scheme Processor 10 9 sec External events 10 2 sec Keyboard input Disk seek Screen refresh class11 ppt Implication Can execute many instructions while waiting for external event to occur Can alternate among processes without anyone noticing 15 213 s 04 2 Measurement Challenge Time on a Computer System How Much Time Does Program X Require CPU time real wall clock time How many total seconds are used when executing X Measure used for most applications Small dependence on other system activities user time time executing instructions in the user process Actual Wall Time system time time executing instructions in kernel on behalf of user process How many seconds elapse between the start and the completion of X Depends on system load I O times etc some other user s time time executing instructions in different user s process Confounding Factors How does time get measured Many processes share computing resources Transient effects when switching from one process to another Suddenly the effects of alternating among processes become noticeable 3 real wall clock time We will use the word time to refer to user time cumulative user time 15 213 s 04 4 Page 1 15 213 s 04 Activity Periods Light Load Activity Periods Heavy Load Activity Periods Load 2 Activity Periods Load 1 Active 1 Inactive Active 1 Inactive 0 0 10 20 30 40 Time ms Most of the time spent executing one process Periodic interrupts every 10ms 50 60 70 Other interrupts System time spent processing interrupts 250 000 clock cycles 30 40 Time ms 50 60 70 80 Other process is executing 15 213 s 04 5 20 Sharing processor with one other active process From perspective of this process system appears to be inactive for 50 of the time Due to I O activity Inactivity periods Interval timer Keep system from executing one process to exclusion of others 10 80 15 213 s 04 6 Interval Counting Interval Counting Example OS Measures Runtimes Using Interval Timer Maintain 2 counts per process User time System time a Interval Timings A Each time get timer interrupt increment counter for executing process B A B A Au Au Au As Bu Bs Bu Bu Bu Bu As Au Au Au Au Au Bs Bu Bu Bs Au Au Au As As User time if running in user mode System time if running in kernel mode A 110u 40s B 70u 30s b Actual Times A A B A B A 120 0u 33 3s B 73 3u 23 3s 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 7 15 213 s 04 8 Page 2 15 213 s 04 Unix time Command time make osevent gcc O2 Wall g march i486 gcc O2 Wall g march i486 gcc O2 Wall g march i486 gcc O2 Wall g march i486 0 820u 0 300s 0 01 32 84 8 Accuracy of Interval Counting c clock c c options c c load c o osevent osevent c 0 0k 0 0io 4049pf 0w A Minimum A Maximum Computed time 70ms Min Actual 60 Max Actual 80 0 10 20 30 40 50 60 70 80 0 82 seconds user time Worst Case Analysis 82 timer intervals Timer Interval 0 30 seconds system time Single process segment measurement can be off by No bound on error for multiple segments 30 timer intervals 1 32 seconds wall time Could consistently underestimate or consistently overestimate 84 8 of total was used running these processes 82 0 3 1 32 848 15 213 s 04 9 Accuracy of Interval Couting cont A Minimum Computed time 70ms A Maximum Min Actual 60 15 213 s 04 10 Cycle Counters Most modern systems have built in registers that are incremented every clock cycle Max Actual 80 Very fine grained Maintained as part of process state In Linux counts elapsed global time 0 10 20 30 40 50 60 70 80 Special assembly code instruction to access Average Case Analysis On recent model Intel machines Over underestimates tend to balance out As long as total run time is sufficiently large 64 bit counter RDTSC instruction sets edx to high order 32 bits eax to low order 32 bits Min run time 1 second 100 timer intervals Consistently miss 4 overhead due to timer interrupts 11 15 213 s 04 12 Page 3 15 213 s 04 Cycle Counter Period Measuring with Cycle Counter Idea Wrap Around Times for 550 MHz machine Get current value of cycle counter Low order 32 bits wrap around every 232 550 106 7 8 seconds High order 64 bits wrap around every 264 550 106 33539534679 seconds store as pair of unsigned s cyc hi and cyc lo Compute something Get new value of cycle counter Perform double precision subtraction to get elapsed cycles 1065 years For 2 GHz machine Keep track of most recent reading of cycle counter static unsigned cyc hi 0 static unsigned cyc lo 0 Low order 32 bits every 2 1 seconds High order 64 bits every 293 years void start counter Get current value of cycle counter access counter cyc hi cyc lo 15 213 s 04 13 15 213 s 04 14 Accessing the Cycle Cntr Closer Look at Extended ASM asm Instruction String Output List Input List Clobbers List GCC allows inline assembly code with mechanism for matching registers with program variables Code only works on x86 machine compiling with GCC void access counter unsigned hi unsigned lo Get cycle counter asm rdtsc movl edx 0 movl eax 1 r hi r lo No input edx eax void access counter unsigned hi unsigned lo Get cycle counter asm rdtsc movl edx 0 movl eax 1 r hi r lo No input edx eax Emit assembly with rdtsc and two movl instructions Instruction String Series of assembly commands Separated by or n Use where normally would use 15 15 213 s 04 16 Page 4 15 213 s 04 Closer Look at Extended ASM Closer Look at Extended ASM asm Instruction String Output List Input List void access counter Clobbers List unsigned hi unsigned lo Get cycle counter asm rdtsc movl edx 0 movl eax 1 r hi r lo No input edx eax asm Instruction String Output List Input List void access counter Clobbers List unsigned hi unsigned lo Get cycle counter asm rdtsc movl edx 0 movl eax 1 r hi r lo No input edx eax Output List Input List Expressions indicating destinations for values 0 1 j Series of expressions indicating sources for values j 1 j 2 Enclosed in parentheses Must be lvalue Value that can appear on LHS of assignment Enclosed in parentheses Any expression returning …
View Full Document
Unlocking...