COMP5211_Algorithms_2012 Semester 2_6_dp2

格式：pdf
大小：287.72 KB
文档页数：10

下载文档原格式

2012-HCI-MA-H2-P1-Prelim

(i)
f :x→
kx 2 − 5 x + 3 , x−2
(ii) (iii)
Use the standard series for ln(1 + x ) to find the first three terms of the 1 Maclaurin's series for y = . [3] 1 + ln (1 + 2 x )
One NETO logistics commander was tasked to deliver goods to an army camp in Abghan during June 2012. The commander delivered 1000 tons of goods on 1st June, 1100 tons on 2nd June, ... etc. Each subsequent day’s delivery was 100 tons more than the previous day’s delivery. After several days of delivery, due to more road attacks from Bl Paeda, the commander had to change the plan so that each subsequent day’s delivery was 100 tons less than the previous day’s delivery. By 15th June, the commander managed to deliver a total of 21300 tons of goods for the past 15 days. On which day did the commander deliver the most goods to the camp? How many tons of goods did he deliver on this particular day? [5] Given that all terms in a geometric progression {un } , n = 1, 2, 3, ... are positive with first term a and common ratio r, where r ≠ 1, the sums H and C are defined as follows:

现代操作系统(第三版)答案

MODERNOPERATINGSYSTEMSTHIRD EDITION PROBLEM SOLUTIONSANDREW S.TANENBAUMVrije UniversiteitAmsterdam,The NetherlandsPRENTICE HALLUPPER SADDLE RIVER,NJ07458Copyright Pearson Education,Inc.2008SOLUTIONS TO CHAPTER1PROBLEMS1.Multiprogramming is the rapid switching of the CPU between multiple proc-esses in memory.It is commonly used to keep the CPU busy while one or more processes are doing I/O.2.Input spooling is the technique of reading in jobs,for example,from cards,onto the disk,so that when the currently executing processes areﬁnished, there will be work waiting for the CPU.Output spooling consists ofﬁrst copying printableﬁles to disk before printing them,rather than printing di-rectly as the output is generated.Input spooling on a personal computer is not very likely,but output spooling is.3.The prime reason for multiprogramming is to give the CPU something to dowhile waiting for I/O to complete.If there is no DMA,the CPU is fully occu-pied doing I/O,so there is nothing to be gained(at least in terms of CPU utili-zation)by multiprogramming.No matter how much I/O a program does,the CPU will be100%busy.This of course assumes the major delay is the wait while data are copied.A CPU could do other work if the I/O were slow for other reasons(arriving on a serial line,for instance).4.It is still alive.For example,Intel makes Pentium I,II,and III,and4CPUswith a variety of different properties including speed and power consumption.All of these machines are architecturally compatible.They differ only in price and performance,which is the essence of the family idea.5.A25×80character monochrome text screen requires a2000-byte buffer.The1024×768pixel24-bit color bitmap requires2,359,296bytes.In1980these two options would have cost$10and$11,520,respectively.For current prices,check on how much RAM currently costs,probably less than$1/MB.6.Consider fairness and real time.Fairness requires that each process be allo-cated its resources in a fair way,with no process getting more than its fair share.On the other hand,real time requires that resources be allocated based on the times when different processes must complete their execution.A real-time process may get a disproportionate share of the resources.7.Choices(a),(c),and(d)should be restricted to kernel mode.8.It may take20,25or30msec to complete the execution of these programsdepending on how the operating system schedules them.If P0and P1are scheduled on the same CPU and P2is scheduled on the other CPU,it will take20mses.If P0and P2are scheduled on the same CPU and P1is scheduled on the other CPU,it will take25msec.If P1and P2are scheduled on the same CPU and P0is scheduled on the other CPU,it will take30msec.If all three are on the same CPU,it will take35msec.2PROBLEM SOLUTIONS FOR CHAPTER19.Every nanosecond one instruction emerges from the pipeline.This means themachine is executing1billion instructions per second.It does not matter at all how many stages the pipeline has.A10-stage pipeline with1nsec per stage would also execute1billion instructions per second.All that matters is how often aﬁnished instruction pops out the end of the pipeline.10.Average access time=0.95×2nsec(word is cache)+0.05×0.99×10nsec(word is in RAM,but not in cache)+0.05×0.01×10,000,000nsec(word on disk only)=5002.395nsec=5.002395μsec11.The manuscript contains80×50×700=2.8million characters.This is,ofcourse,impossible toﬁt into the registers of any currently available CPU and is too big for a1-MB cache,but if such hardware were available,the manuscript could be scanned in2.8msec from the registers or5.8msec from the cache.There are approximately27001024-byte blocks of data,so scan-ning from the disk would require about27seconds,and from tape2minutes7 seconds.Of course,these times are just to read the data.Processing and rewriting the data would increase the time.12.Maybe.If the caller gets control back and immediately overwrites the data,when the writeﬁnally occurs,the wrong data will be written.However,if the driverﬁrst copies the data to a private buffer before returning,then the caller can be allowed to continue immediately.Another possibility is to allow the caller to continue and give it a signal when the buffer may be reused,but this is tricky and error prone.13.A trap instruction switches the execution mode of a CPU from the user modeto the kernel mode.This instruction allows a user program to invoke func-tions in the operating system kernel.14.A trap is caused by the program and is synchronous with it.If the program isrun again and again,the trap will always occur at exactly the same position in the instruction stream.An interrupt is caused by an external event and its timing is not reproducible.15.The process table is needed to store the state of a process that is currentlysuspended,either ready or blocked.It is not needed in a single process sys-tem because the single process is never suspended.16.Mounting aﬁle system makes anyﬁles already in the mount point directoryinaccessible,so mount points are normally empty.However,a system admin-istrator might want to copy some of the most importantﬁles normally located in the mounted directory to the mount point so they could be found in their normal path in an emergency when the mounted device was being repaired.PROBLEM SOLUTIONS FOR CHAPTER13 17.A system call allows a user process to access and execute operating systemfunctions inside the er programs use system calls to invoke operat-ing system services.18.Fork can fail if there are no free slots left in the process table(and possibly ifthere is no memory or swap space left).Exec can fail if theﬁle name given does not exist or is not a valid executableﬁle.Unlink can fail if theﬁle to be unlinked does not exist or the calling process does not have the authority to unlink it.19.If the call fails,for example because fd is incorrect,it can return−1.It canalso fail because the disk is full and it is not possible to write the number of bytes requested.On a correct termination,it always returns nbytes.20.It contains the bytes:1,5,9,2.21.Time to retrieve theﬁle=1*50ms(Time to move the arm over track#50)+5ms(Time for theﬁrst sector to rotate under the head)+10/100*1000ms(Read10MB)=155ms22.Block specialﬁles consist of numbered blocks,each of which can be read orwritten independently of all the other ones.It is possible to seek to any block and start reading or writing.This is not possible with character specialﬁles.23.System calls do not really have names,other than in a documentation sense.When the library procedure read traps to the kernel,it puts the number of the system call in a register or on the stack.This number is used to index into a table.There is really no name used anywhere.On the other hand,the name of the library procedure is very important,since that is what appears in the program.24.Yes it can,especially if the kernel is a message-passing system.25.As far as program logic is concerned it does not matter whether a call to a li-brary procedure results in a system call.But if performance is an issue,if a task can be accomplished without a system call the program will run faster.Every system call involves overhead time in switching from the user context to the kernel context.Furthermore,on a multiuser system the operating sys-tem may schedule another process to run when a system call completes, further slowing the progress in real time of a calling process.26.Several UNIX calls have no counterpart in the Win32API:Link:a Win32program cannot refer to aﬁle by an alternative name or see it in more than one directory.Also,attempting to create a link is a convenient way to test for and create a lock on aﬁle.4PROBLEM SOLUTIONS FOR CHAPTER1Mount and umount:a Windows program cannot make assumptions about standard path names because on systems with multiple disk drives the drive name part of the path may be different.Chmod:Windows uses access control listsKill:Windows programmers cannot kill a misbehaving program that is not cooperating.27.Every system architecture has its own set of instructions that it can execute.Thus a Pentium cannot execute SPARC programs and a SPARC cannot exe-cute Pentium programs.Also,different architectures differ in bus architecture used(such as VME,ISA,PCI,MCA,SBus,...)as well as the word size of the CPU(usually32or64bit).Because of these differences in hardware,it is not feasible to build an operating system that is completely portable.A highly portable operating system will consist of two high-level layers---a machine-dependent layer and a machine independent layer.The machine-dependent layer addresses the specifics of the hardware,and must be implemented sepa-rately for every architecture.This layer provides a uniform interface on which the machine-independent layer is built.The machine-independent layer has to be implemented only once.To be highly portable,the size of the machine-dependent layer must be kept as small as possible.28.Separation of policy and mechanism allows OS designers to implement asmall number of basic primitives in the kernel.These primitives are sim-pliﬁed,because they are not dependent of any specific policy.They can then be used to implement more complex mechanisms and policies at the user level.29.The conversions are straightforward:(a)A micro year is10−6×365×24×3600=31.536sec.(b)1000meters or1km.(c)There are240bytes,which is1,099,511,627,776bytes.(d)It is6×1024kg.SOLUTIONS TO CHAPTER2PROBLEMS1.The transition from blocked to running is conceivable.Suppose that a processis blocked on I/O and the I/Oﬁnishes.If the CPU is otherwise idle,the proc-ess could go directly from blocked to running.The other missing transition, from ready to blocked,is impossible.A ready process cannot do I/O or any-thing else that might block it.Only a running process can block.PROBLEM SOLUTIONS FOR CHAPTER25 2.You could have a register containing a pointer to the current process tableentry.When I/O completed,the CPU would store the current machine state in the current process table entry.Then it would go to the interrupt vector for the interrupting device and fetch a pointer to another process table entry(the ser-vice procedure).This process would then be started up.3.Generally,high-level languages do not allow the kind of access to CPU hard-ware that is required.For instance,an interrupt handler may be required to enable and disable the interrupt servicing a particular device,or to manipulate data within a process’stack area.Also,interrupt service routines must exe-cute as rapidly as possible.4.There are several reasons for using a separate stack for the kernel.Two ofthem are as follows.First,you do not want the operating system to crash be-cause a poorly written user program does not allow for enough stack space.Second,if the kernel leaves stack data in a user program’s memory space upon return from a system call,a malicious user might be able to use this data toﬁnd out information about other processes.5.If each job has50%I/O wait,then it will take20minutes to complete in theabsence of competition.If run sequentially,the second one willﬁnish40 minutes after theﬁrst one starts.With two jobs,the approximate CPU utiliza-tion is1−0.52.Thus each one gets0.375CPU minute per minute of real time.To accumulate10minutes of CPU time,a job must run for10/0.375 minutes,or about26.67minutes.Thus running sequentially the jobsﬁnish after40minutes,but running in parallel theyﬁnish after26.67minutes.6.It would be difﬁcult,if not impossible,to keep theﬁle system consistent.Sup-pose that a client process sends a request to server process1to update aﬁle.This process updates the cache entry in its memory.Shortly thereafter,anoth-er client process sends a request to server2to read thatﬁle.Unfortunately,if theﬁle is also cached there,server2,in its innocence,will return obsolete data.If theﬁrst process writes theﬁle through to the disk after caching it, and server2checks the disk on every read to see if its cached copy is up-to-date,the system can be made to work,but it is precisely all these disk ac-cesses that the caching system is trying to avoid.7.No.If a single-threaded process is blocked on the keyboard,it cannot fork.8.A worker thread will block when it has to read a Web page from the disk.Ifuser-level threads are being used,this action will block the entire process, destroying the value of multithreading.Thus it is essential that kernel threads are used to permit some threads to block without affecting the others.9.Yes.If the server is entirely CPU bound,there is no need to have multiplethreads.It just adds unnecessary complexity.As an example,consider a tele-phone directory assistance number(like555-1212)for an area with1million6PROBLEM SOLUTIONS FOR CHAPTER2people.If each(name,telephone number)record is,say,64characters,the entire database takes64megabytes,and can easily be kept in the server’s memory to provide fast lookup.10.When a thread is stopped,it has values in the registers.They must be saved,just as when the process is stopped the registers must be saved.Multipro-gramming threads is no different than multiprogramming processes,so each thread needs its own register save area.11.Threads in a process cooperate.They are not hostile to one another.If yield-ing is needed for the good of the application,then a thread will yield.After all,it is usually the same programmer who writes the code for all of them. er-level threads cannot be preempted by the clock unless the whole proc-ess’quantum has been used up.Kernel-level threads can be preempted indivi-dually.In the latter case,if a thread runs too long,the clock will interrupt the current process and thus the current thread.The kernel is free to pick a dif-ferent thread from the same process to run next if it so desires.13.In the single-threaded case,the cache hits take15msec and cache misses take90msec.The weighted average is2/3×15+1/3×90.Thus the mean re-quest takes40msec and the server can do25per second.For a multithreaded server,all the waiting for the disk is overlapped,so every request takes15 msec,and the server can handle662/3requests per second.14.The biggest advantage is the efﬁciency.No traps to the kernel are needed toswitch threads.The biggest disadvantage is that if one thread blocks,the en-tire process blocks.15.Yes,it can be done.After each call to pthread create,the main programcould do a pthread join to wait until the thread just created has exited before creating the next thread.16.The pointers are really necessary because the size of the global variable isunknown.It could be anything from a character to an array ofﬂoating-point numbers.If the value were stored,one would have to give the size to create global,which is all right,but what type should the second parameter of set global be,and what type should the value of read global be?17.It could happen that the runtime system is precisely at the point of blocking orunblocking a thread,and is busy manipulating the scheduling queues.This would be a very inopportune moment for the clock interrupt handler to begin inspecting those queues to see if it was time to do thread switching,since they might be in an inconsistent state.One solution is to set aﬂag when the run-time system is entered.The clock handler would see this and set its ownﬂag, then return.When the runtime systemﬁnished,it would check the clockﬂag, see that a clock interrupt occurred,and now run the clock handler.PROBLEM SOLUTIONS FOR CHAPTER27 18.Yes it is possible,but inefﬁcient.A thread wanting to do a system callﬁrstsets an alarm timer,then does the call.If the call blocks,the timer returns control to the threads package.Of course,most of the time the call will not block,and the timer has to be cleared.Thus each system call that might block has to be executed as three system calls.If timers go off prematurely,all kinds of problems can develop.This is not an attractive way to build a threads package.19.The priority inversion problem occurs when a low-priority process is in itscritical region and suddenly a high-priority process becomes ready and is scheduled.If it uses busy waiting,it will run forever.With user-level threads,it cannot happen that a low-priority thread is suddenly preempted to allow a high-priority thread run.There is no preemption.With kernel-level threads this problem can arise.20.With round-robin scheduling it works.Sooner or later L will run,and eventu-ally it will leave its critical region.The point is,with priority scheduling,L never gets to run at all;with round robin,it gets a normal time slice periodi-cally,so it has the chance to leave its critical region.21.Each thread calls procedures on its own,so it must have its own stack for thelocal variables,return addresses,and so on.This is equally true for user-level threads as for kernel-level threads.22.Yes.The simulated computer could be multiprogrammed.For example,while process A is running,it reads out some shared variable.Then a simula-ted clock tick happens and process B runs.It also reads out the same vari-able.Then it adds1to the variable.When process A runs,if it also adds one to the variable,we have a race condition.23.Yes,it still works,but it still is busy waiting,of course.24.It certainly works with preemptive scheduling.In fact,it was designed forthat case.When scheduling is nonpreemptive,it might fail.Consider the case in which turn is initially0but process1runsﬁrst.It will just loop forever and never release the CPU.25.To do a semaphore operation,the operating systemﬁrst disables interrupts.Then it reads the value of the semaphore.If it is doing a down and the sema-phore is equal to zero,it puts the calling process on a list of blocked processes associated with the semaphore.If it is doing an up,it must check to see if any processes are blocked on the semaphore.If one or more processes are block-ed,one of them is removed from the list of blocked processes and made run-nable.When all these operations have been completed,interrupts can be enabled again.8PROBLEM SOLUTIONS FOR CHAPTER226.Associated with each counting semaphore are two binary semaphores,M,used for mutual exclusion,and B,used for blocking.Also associated with each counting semaphore is a counter that holds the number of up s minus the number of down s,and a list of processes blocked on that semaphore.To im-plement down,a processﬁrst gains exclusive access to the semaphores, counter,and list by doing a down on M.It then decrements the counter.If it is zero or more,it just does an up on M and exits.If M is negative,the proc-ess is put on the list of blocked processes.Then an up is done on M and a down is done on B to block the process.To implement up,ﬁrst M is down ed to get mutual exclusion,and then the counter is incremented.If it is more than zero,no one was blocked,so all that needs to be done is to up M.If, however,the counter is now negative or zero,some process must be removed from the list.Finally,an up is done on B and M in that order.27.If the program operates in phases and neither process may enter the nextphase until both areﬁnished with the current phase,it makes perfect sense to use a barrier.28.With kernel threads,a thread can block on a semaphore and the kernel canrun some other thread in the same process.Consequently,there is no problem using semaphores.With user-level threads,when one thread blocks on a semaphore,the kernel thinks the entire process is blocked and does not run it ever again.Consequently,the process fails.29.It is very expensive to implement.Each time any variable that appears in apredicate on which some process is waiting changes,the run-time system must re-evaluate the predicate to see if the process can be unblocked.With the Hoare and Brinch Hansen monitors,processes can only be awakened on a signal primitive.30.The employees communicate by passing messages:orders,food,and bags inthis case.In UNIX terms,the four processes are connected by pipes.31.It does not lead to race conditions(nothing is ever lost),but it is effectivelybusy waiting.32.It will take nT sec.33.In simple cases it may be possible to determine whether I/O will be limitingby looking at source code.For instance a program that reads all its inputﬁles into buffers at the start will probably not be I/O bound,but a problem that reads and writes incrementally to a number of differentﬁles(such as a compi-ler)is likely to be I/O bound.If the operating system provides a facility such as the UNIX ps command that can tell you the amount of CPU time used by a program,you can compare this with the total time to complete execution of the program.This is,of course,most meaningful on a system where you are the only user.34.For multiple processes in a pipeline,the common parent could pass to the op-erating system information about the ﬂow of data.With this information the OS could,for instance,determine which process could supply output to a process blocking on a call for input.35.The CPU efﬁciency is the useful CPU time divided by the total CPU time.When Q ≥T ,the basic cycle is for the process to run for T and undergo a process switch for S .Thus (a)and (b)have an efﬁciency of T /(S +T ).When the quantum is shorter than T ,each run of T will require T /Q process switches,wasting a time ST /Q .The efﬁciency here is thenT +ST /QT which reduces to Q /(Q +S ),which is the answer to (c).For (d),we just sub-stitute Q for S and ﬁnd that the efﬁciency is 50%.Finally,for (e),as Q →0the efﬁciency goes to 0.36.Shortest job ﬁrst is the way to minimize average response time.0<X ≤3:X ,3,5,6,9.3<X ≤5:3,X ,5,6,9.5<X ≤6:3,5,X ,6,9.6<X ≤9:3,5,6,X ,9.X >9:3,5,6,9,X.37.For round robin,during the ﬁrst 10minutes each job gets 1/5of the CPU.Atthe end of 10minutes,C ﬁnishes.During the next 8minutes,each job gets 1/4of the CPU,after which time D ﬁnishes.Then each of the three remaining jobs gets 1/3of the CPU for 6minutes,until B ﬁnishes,and so on.The ﬁn-ishing times for the ﬁve jobs are 10,18,24,28,and 30,for an average of 22minutes.For priority scheduling,B is run ﬁrst.After 6minutes it is ﬁnished.The other jobs ﬁnish at 14,24,26,and 30,for an average of 18.8minutes.If the jobs run in the order A through E ,they ﬁnish at 10,16,18,22,and 30,for an average of 19.2minutes.Finally,shortest job ﬁrst yields ﬁnishing times of 2,6,12,20,and 30,for an average of 14minutes.38.The ﬁrst time it gets 1quantum.On succeeding runs it gets 2,4,8,and 15,soit must be swapped in 5times.39.A check could be made to see if the program was expecting input and didanything with it.A program that was not expecting input and did not process it would not get any special priority boost.40.The sequence of predictions is 40,30,35,and now 25.41.The fraction of the CPU used is35/50+20/100+10/200+x/250.To beschedulable,this must be less than1.Thus x must be less than12.5msec. 42.Two-level scheduling is needed when memory is too small to hold all theready processes.Some set of them is put into memory,and a choice is made from that set.From time to time,the set of in-core processes is adjusted.This algorithm is easy to implement and reasonably efﬁcient,certainly a lot better than,say,round robin without regard to whether a process was in memory or not.43.Each voice call runs200times/second and uses up1msec per burst,so eachvoice call needs200msec per second or400msec for the two of them.The video runs25times a second and uses up20msec each time,for a total of 500msec per second.Together they consume900msec per second,so there is time left over and the system is schedulable.44.The kernel could schedule processes by any means it wishes,but within eachprocess it runs threads strictly in priority order.By letting the user process set the priority of its own threads,the user controls the policy but the kernel handles the mechanism.45.The change would mean that after a philosopher stopped eating,neither of hisneighbors could be chosen next.In fact,they would never be chosen.Sup-pose that philosopher2ﬁnished eating.He would run test for philosophers1 and3,and neither would be started,even though both were hungry and both forks were available.Similarly,if philosopher4ﬁnished eating,philosopher3 would not be started.Nothing would start him.46.If a philosopher blocks,neighbors can later see that she is hungry by checkinghis state,in test,so he can be awakened when the forks are available.47.Variation1:readers have priority.No writer may start when a reader is ac-tive.When a new reader appears,it may start immediately unless a writer is currently active.When a writerﬁnishes,if readers are waiting,they are all started,regardless of the presence of waiting writers.Variation2:Writers have priority.No reader may start when a writer is waiting.When the last ac-tive processﬁnishes,a writer is started,if there is one;otherwise,all the readers(if any)are started.Variation3:symmetric version.When a reader is active,new readers may start immediately.When a writerﬁnishes,a new writer has priority,if one is waiting.In other words,once we have started reading,we keep reading until there are no readers left.Similarly,once we have started writing,all pending writers are allowed to run.48.A possible shell script might beif[!–f numbers];then echo0>numbers;ﬁcount=0while(test$count!=200)docount=‘expr$count+1‘n=‘tail–1numbers‘expr$n+1>>numbersdoneRun the script twice simultaneously,by starting it once in the background (using&)and again in the foreground.Then examine theﬁle numbers.It will probably start out looking like an orderly list of numbers,but at some point it will lose its orderliness,due to the race condition created by running two cop-ies of the script.The race can be avoided by having each copy of the script test for and set a lock on theﬁle before entering the critical area,and unlock-ing it upon leaving the critical area.This can be done like this:if ln numbers numbers.lockthenn=‘tail–1numbers‘expr$n+1>>numbersrm numbers.lockﬁThis version will just skip a turn when theﬁle is inaccessible,variant solu-tions could put the process to sleep,do busy waiting,or count only loops in which the operation is successful.SOLUTIONS TO CHAPTER3PROBLEMS1.It is an accident.The base register is16,384because the program happened tobe loaded at address16,384.It could have been loaded anywhere.The limit register is16,384because the program contains16,384bytes.It could have been any length.That the load address happens to exactly match the program length is pure coincidence.2.Almost the entire memory has to be copied,which requires each word to beread and then rewritten at a different location.Reading4bytes takes10nsec, so reading1byte takes2.5nsec and writing it takes another2.5nsec,for a total of5nsec per byte compacted.This is a rate of200,000,000bytes/sec.To copy128MB(227bytes,which is about1.34×108bytes),the computer needs227/200,000,000sec,which is about671msec.This number is slightly pessimistic because if the initial hole at the bottom of memory is k bytes, those k bytes do not need to be copied.However,if there are many holes andmany data segments,the holes will be small,so k will be small and the error in the calculation will also be small.3.The bitmap needs1bit per allocation unit.With227/n allocation units,this is224/n bytes.The linked list has227/216or211nodes,each of8bytes,for a total of214bytes.For small n,the linked list is better.For large n,the bitmap is better.The crossover point can be calculated by equating these two formu-las and solving for n.The result is1KB.For n smaller than1KB,a linked list is better.For n larger than1KB,a bitmap is better.Of course,the assumption of segments and holes alternating every64KB is very unrealistic.Also,we need n<=64KB if the segments and holes are64KB.4.Firstﬁt takes20KB,10KB,18KB.Bestﬁt takes12KB,10KB,and9KB.Worstﬁt takes20KB,18KB,and15KB.Nextﬁt takes20KB,18KB,and9 KB.5.For a4-KB page size the(page,offset)pairs are(4,3616),(8,0),and(14,2656).For an8-KB page size they are(2,3616),(4,0),and(7,2656).6.They built an MMU and inserted it between the8086and the bus.Thus all8086physical addresses went into the MMU as virtual addresses.The MMU then mapped them onto physical addresses,which went to the bus.7.(a)M has to be at least4,096to ensure a TLB miss for every access to an ele-ment of X.Since N only affects how many times X is accessed,any value of N will do.(b)M should still be atleast4,096to ensure a TLB miss for every access to anelement of X.But now N should be greater than64K to thrash the TLB, that is,X should exceed256KB.8.The total virtual address space for all the processes combined is nv,so thismuch storage is needed for pages.However,an amount r can be in RAM,so the amount of disk storage required is only nv−r.This amount is far more than is ever needed in practice because rarely will there be n processes ac-tually running and even more rarely will all of them need the maximum al-lowed virtual memory.9.The page table contains232/213entries,which is524,288.Loading the pagetable takes52msec.If a process gets100msec,this consists of52msec for loading the page table and48msec for running.Thus52%of the time is spent loading page tables.10.(a)We need one entry for each page,or224=16×1024×1024entries,sincethere are36=48−12bits in the page numberﬁeld.。

6603_Lecture3-4(1)

2
Detection in Fading Channel
• Consider a slow flat Rayleigh fading channel.
y[m] h[m]s[m] z[m] h[m] (0,1)
How to detect? What is the error performance?
− Received signal y [ y[1], y[2],..., y[ L]]' :
y hx z
h [h[1], h[2],..., h[ L]]'
h h y || h || x z || h || || h ||
Maximal ratio combiner: it weighs the received signal in each branch in
Pe E h Q

1 SNR 2 | h | SNR 1 2 1 SNR
2

SNR 1 1 1 O 2 1 SNR 2 SNR SNR
Pe 1 4 SNR
at high SNR
Semester A, 2010
proportion to the signal strength and also aligns the phases of the signals in the summation to maximize the output SNR.
Semester A, 2010 Wireless Communication Technologies
15
Transmit Diversity I: with CSIT
• If the transmitter has full Channel State Information (CSIT):

A File is Not a File

A File is Not a File:Understanding the I/O Behaviorof Apple Desktop ApplicationsTyler Harter,Chris Dragga,Michael Vaughn,Andrea C.Arpaci-Dusseau,Remzi H.Arpaci-DusseauDepartment of Computer SciencesUniversity of Wisconsin,Madison{harter,dragga,vaughn,dusseau,remzi}@ABSTRACTWe analyze the I/O behavior of iBench,a new collection of produc-tivity and multimedia application workloads.Our analysis reveals a number of differences between iBench and typicalﬁle-system workload studies,including the complex organization of modern ﬁles,the lack of pure sequential access,the inﬂuence of underlying frameworks on I/O patterns,the widespread use ofﬁle synchro-nization and atomic operations,and the prevalence of threads.Our results have strong ramiﬁcations for the design of next generation local and cloud-based storage systems.1.INTRODUCTIONThe design and implementation ofﬁle and storage systems has long been at the forefront of computer systems research.Inno-vations such as namespace-based locality[21],crash consistency via journaling[15,29]and copy-on-write[7,34],checksums and redundancy for reliability[5,7,26,30],scalable on-disk struc-tures[37],distributedﬁle systems[16,35],and scalable cluster-based storage systems[9,14,18]have greatly inﬂuenced how data is managed and stored within modern computer systems.Much of this work inﬁle systems over the past three decades has been shaped by measurement:the deep and detailed analysis of workloads[4,10,11,16,19,25,33,36,39].One excellent example is found in work on the Andrew File System[16];de-tailed analysis of an early AFS prototype led to the next-generation protocol,including the key innovation of callbacks.Measurement helps us understand the systems of today so we can build improved systems for tomorrow.Whereas most studies ofﬁle systems focus on the corporate or academic intranet,mostﬁle-system users work in the more mun-dane environment of the home,accessing data via desktop PCs, laptops,and compact devices such as tablet computers and mo-bile phones.Despite the large number of previous studies,little is known about home-user applications and their I/O patterns. Home-user applications are important today,and their impor-tance will increase as more users store data not only on local de-vices but also in the ers expect to run similar applications across desktops,laptops,and phones;therefore,the behavior of these applications will affect virtually every system with which a Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for proﬁt or commercial advantage and that copies bear this notice and the full citation on theﬁrst page.To copy otherwise,to republish,to post on servers or to redistribute to lists,requires prior speciﬁc permission and/or a fee.Copyright2011ACM978-1-59593-591-5/07/0010...$er interacts.I/O behavior is especially important to understand since it greatly impacts how users perceive overall system latency and application performance[12].While a study of how users typically exercise these applications would be interesting,theﬁrst step is to perform a detailed study of I/O behavior under typical but controlled workload tasks.This style of application study,common in theﬁeld of computer archi-tecture[40],is different from the workload study found in systems research,and can yield deeper insight into how the applications are constructed and howﬁle and storage systems need to be designed in response.Home-user applications are fundamentally large and complex, containing millions of lines of code[20].In contrast,traditional U NIX-based applications are designed to be simple,to perform one task well,and to be strung together to perform more complex tasks[32].This modular approach of U NIX applications has not prevailed[17]:modern applications are standalone monoliths,pro-viding a rich and continuously evolving set of features to demand-ing users.Thus,it is beneﬁcial to study each application individu-ally to ascertain its behavior.In this paper,we present theﬁrst in-depth analysis of the I/O behavior of modern home-user applications;we focus on produc-tivity applications(for word processing,spreadsheet manipulation, and presentation creation)and multimedia software(for digital mu-sic,movie editing,and photo management).Our analysis centers on two Apple software suites:iWork,consisting of Pages,Num-bers,and Keynote;and iLife,which contains iPhoto,iTunes,and iMovie.As Apple’s market share grows[38],these applications form the core of an increasingly popular set of workloads;as de-vice convergence continues,similar forms of these applications are likely to access userﬁles from both stationary machines and mov-ing cellular devices.We call our collection the iBench task suite. To investigate the I/O behavior of the iBench suite,we build an instrumentation framework on top of the powerful DTrace tracing system found inside Mac OS X[8].DTrace allows us not only to monitor system calls made by each traced application,but also to examine stack traces,in-kernel functions such as page-ins and page-outs,and other details required to ensure accuracy and com-pleteness.We also develop an application harness based on Apple-Script[3]to drive each application in the repeatable and automated fashion that is key to any study of GUI-based applications[12]. Our careful study of the tasks in the iBench suite has enabled us to make a number of interesting observations about how applica-tions access and manipulate stored data.In addition to conﬁrming standard pastﬁndings(e.g.,mostﬁles are small;most bytes ac-cessed are from largeﬁles[4]),weﬁnd the following new results. Aﬁle is not aﬁle.Modern applications manage large databases of information organized into complex directory trees.Even simple word-processing documents,which appear to users as a“ﬁle”,arein actuality smallﬁle systems containing many sub-ﬁles(e.g.,a Microsoft.docﬁle is actually a FATﬁle system containing pieces of the document).File systems should be cognizant of such hidden structure in order to lay out and access data in these complexﬁles more effectively.Sequential access is not sequential.Building on the trend no-ticed by V ogels for Windows NT[39],we observe that even for streaming media workloads,“pure”sequential access is increas-ingly rare.Sinceﬁle formats often include metadata in headers, applications often read and re-read theﬁrst portion of aﬁle before streaming through its contents.Prefetching and other optimizations might beneﬁt from a deeper knowledge of theseﬁle formats. Auxiliaryﬁles dominate.Applications help users create,mod-ify,and organize content,but userﬁles represent a small fraction of theﬁles touched by modern applications.Mostﬁles are helper ﬁles that applications use to provide a rich graphical experience, support multiple languages,and record history and other metadata. File-system placement strategies might reduce seeks by grouping the hundreds of helperﬁles used by an individual application. Writes are often forced.As the importance of home data in-creases(e.g.,family photos),applications are less willing to simply write data and hope it is eventuallyﬂushed to disk.Weﬁnd that most written data is explicitly forced to disk by the application;for example,iPhoto calls fsync thousands of times in even the sim-plest of tasks.Forﬁle systems and storage,the days of delayed writes[22]may be over;new ideas are needed to support applica-tions that desire durability.Renaming is popular.Home-user applications commonly use atomic operations,in particular rename,to present a consistent view ofﬁles to users.Forﬁle systems,this may mean that trans-actional capabilities[23]are needed.It may also necessitate a re-thinking of traditional means ofﬁle locality;for example,placing aﬁle on disk based on its parent directory[21]does not work as expected when theﬁle isﬁrst created in a temporary location and then renamed.Multiple threads perform I/O.Virtually all of the applications we study issue I/O requests from a number of threads;a few ap-plications launch I/Os from hundreds of threads.Part of this us-age stems from the GUI-based nature of these applications;it is well known that threads are required to perform long-latency oper-ations in the background to keep the GUI responsive[24].Thus,ﬁle and storage systems should be thread-aware so they can better allocate bandwidth.Frameworks inﬂuence I/O.Modern applications are often de-veloped in sophisticated IDEs and leverage powerful libraries,such as Cocoa and Carbon.Whereas UNIX-style applications often di-rectly invoke system calls to read and writeﬁles,modern libraries put more code between applications and the underlyingﬁle system; for example,including"cocoa.h"in a Mac application imports 112,047lines of code from689differentﬁles[28].Thus,the be-havior of the framework,and not just the application,determines I/O patterns.Weﬁnd that the default behavior of some Cocoa APIs induces extra I/O and possibly unnecessary(and costly)synchro-nizations to disk.In addition,use of different libraries for similar tasks within an application can lead to inconsistent behavior be-tween those tasks.Future storage design should take these libraries and frameworks into account.This paper contains four major contributions.First,we describe a general tracing framework for creating benchmarks based on in-teractive tasks that home users may perform(e.g.,importing songs, exporting video clips,saving documents).Second,we deconstruct the I/O behavior of the tasks in iBench;we quantify the I/O behav-ior of each task in numerous ways,including the types ofﬁles ac-cessed(e.g.,counts and sizes),the access patterns(e.g.,read/write, sequentiality,and preallocation),transactional properties(e.g.,dura-bility and atomicity),and threading.Third,we describe how these qualitative changes in I/O behavior may impact the design of future systems.Finally,we present the34traces from the iBench task suite;by making these traces publicly available and easy to use,we hope to improve the design,implementation,and evaluation of the next generation of local and cloud storage systems:/adsl/Traces/ibench The remainder of this paper is organized as follows.We begin by presenting a detailed timeline of the I/O operations performed by one task in the iBench suite;this motivates the need for a systematic study of home-user applications.We next describe our methodol-ogy for creating the iBench task suite.We then spend the majority of the paper quantitatively analyzing the I/O characteristics of the full iBench suite.Finally,we summarize the implications of our ﬁndings onﬁle-system design.2.CASE STUDYThe I/O characteristics of modern home-user applications are distinct from those of U NIX applications studied in the past.To motivate the need for a new study,we investigate the complex I/O behavior of a single representative task.Speciﬁcally,we report in detail the I/O performed over time by the Pages(4.0.3)application, a word processor,running on Mac OS X Snow Leopard(10.6.2)as it creates a blank document,inserts15JPEG images each of size 2.5MB,and saves the document as a Microsoft.docﬁle.Figure1shows the I/O this task performs(see the caption for a description of the symbols used).The top portion of theﬁgure il-lustrates the accesses performed over the full lifetime of the task:at a high level,it shows that more than385ﬁles spanning six different categories are accessed by eleven different threads,with many in-tervening calls to fsync and rename.The bottom portion of the ﬁgure magniﬁes a short time interval,showing the reads and writes performed by a single thread accessing the primary.doc productiv-ityﬁle.From this one experiment,we illustrate eachﬁnding de-scribed in the introduction.Weﬁrst focus on the single access that saves the user’s document(bottom),and then consider the broader context surrounding thisﬁle save,where we observe aﬂurry of ac-cesses to hundreds of helperﬁles(top).Aﬁle is not aﬁle.Focusing on the magniﬁed timeline of reads and writes to the productivity.docﬁle,we see that theﬁle format comprises more than just a simpleﬁle.Microsoft.docﬁles are based on the FATﬁle system and allow bundling of multipleﬁles in the single.docﬁle.This.docﬁle contains a directory(Root),three streams for large data(WordDocument,Data,and1Table),and a stream for small data(Ministream).Space is allocated in theﬁle with three sections:aﬁle allocation table(FAT),a double-indirect FAT(DIF)region,and a ministream allocation region(Mini). Sequential access is not sequential.The complex FAT-based ﬁle format causes random access patterns in several ways:ﬁrst,the header is updated at the beginning and end of the magniﬁed access; second,data from individual streams is fragmented throughout the ﬁle;and third,the1Table stream is updated before and after each image is appended to the WordDocument stream.Auxiliaryﬁles dominate.Although saving the single.doc we have been considering is the sole purpose of this task,we now turn our attention to the top timeline and see that385differentﬁles are accessed.There are several reasons for this multitude ofﬁles. First,Pages provides a rich graphical experience involving many images and other forms of multimedia;together with the15in-serted JPEGs,this requires118multimediaﬁles.Second,usersF i l e sSequential RunsF i l e O f f s e t (K B )Figure 1:Pages Saving A Word Document.The top graph shows the 75-second timeline of the entire run,while the bottom graph is a magniﬁed view of seconds 54to 58.In the top graph,annotations on the left categorize ﬁles by type and indicate ﬁle count and amount of I/O;annotations on the right show threads.Black bars are ﬁle accesses (reads and writes),with thickness logarithmically proportional to bytes of I/O./is an fsync ;\is a rename ;X is both.In the bottom graph,individual reads and writes to the .doc ﬁle are shown.Vertical bar position and bar length represent the offset within the ﬁle and number of bytes touched.Thick white bars are reads;thin gray bars are writes.Repeated runs are marked with the number of repetitions.Annotations on the right indicate the name of each ﬁle section.want to use Pages in their native language,so application text is not hard-coded into the executable but is instead stored in25different .stringsﬁles.Third,to save user preferences and other metadata, Pages uses a SQLite database(2ﬁles)and a number of key-value stores(218.plistﬁles).Writes are often forced;renaming is popular.Pages uses both of these actions to enforce basic transactional guarantees.It uses fsync toﬂush write data to disk,making it durable;it uses rename to atomically replace oldﬁles with newﬁles so that aﬁle never contains inconsistent data.The timeline shows these invo-cations numerous times.First,Pages regularly uses fsync and rename when updating the key-value store of a.plistﬁle.Second, fsync is used on the SQLite database.Third,for each of the15 image insertions,Pages calls fsync on aﬁle named“tempData”(classiﬁed as“other”)to update its automatic backup.Multiple threads perform I/O.Pages is a multi-threaded appli-cation and issues I/O requests from many different threads during the ing multiple threads for I/O allows Pages to avoid blocking while I/O requests are outstanding.Examining the I/O behavior across threads,we see that Thread1performs the most signiﬁcant portion of I/O,but ten other threads are also involved.In most cases,a single thread exclusively accesses aﬁle,but it is not uncommon for multiple threads to share aﬁle.Frameworks inﬂuence I/O.Pages was developed in a rich pro-gramming environment where frameworks such as Cocoa or Car-bon are used for I/O;these libraries impact I/O patterns in ways the developer might not expect.For example,although the appli-cation developers did not bother to use fsync or rename when saving the user’s work in the.docﬁle,the Cocoa library regularly uses these calls to atomically and durably update relatively unim-portant metadata,such as“recently opened”lists stored in.plist ﬁles.As another example,when Pages tries to read data in512-byte chunks from the.doc,each read goes through the STDIO library, which only reads in4KB chunks.Thus,when Pages attempts to read one chunk from the1Table stream,seven unrequested chunks from the WordDocument stream are also incidentally read(off-set12039KB).In other cases,regions of the.docﬁle are repeat-edly accessed unnecessarily.For example,around the3KB off-set,read/write pairs occur dozens of times.Pages uses a library to write2-byte words;each time a word is written,the library reads, updates,and writes back an entire512-byte chunk.Finally,we see evidence of redundancy between libraries:even though Pages has a backing SQLite database for some of its properties,it also uses.plistﬁles,which function across Apple applications as generic property stores.This one detailed experiment has shed light on a number of in-teresting I/O behaviors that indicate that home-user applications are indeed different than traditional workloads.A new workload suite is needed that more accurately reﬂects these applications.3.IBENCH TASK SUITEOur goal in constructing the iBench task suite is two-fold.First, we would like iBench to be representative of the tasks performed by home users.For this reason,iBench contains popular applications from the iLife and iWork suites for entertainment and productivity. Second,we would like iBench to be relatively simple for others to use forﬁle and storage system analysis.For this reason,we auto-mate the interactions of a home user and collect the resulting traces of I/O system calls.The traces are available online at this site: /adsl/Traces/ibench.We now describe in more detail how we met these two goals.3.1RepresentativeTo capture the I/O behavior of home users,iBench models the ac-tions of a“reasonable”user interacting with iPhoto,iTunes,iMovie, Pages,Numbers,and Keynote.Since the research community does not yet have data on the exact distribution of tasks that home users perform,iBench contains tasks that we believe are common and usesﬁles with sizes that can be justiﬁed for a reasonable user. iBench contains34different tasks,each representing a home user performing one distinct operation.If desired,these tasks could be combined to create more complex workﬂows and I/O workloads. The six applications and corresponding tasks are as follows.iLife iPhoto8.1.1(419):digital photo album and photo manip-ulation software.iPhoto stores photos in a library that contains the data for the photos(which can be in a variety of formats,including JPG,TIFF,and PNG),a directory of modiﬁedﬁles,a directory of scaled down images,and twoﬁles of thumbnail images.The library stores metadata in a SQLite database.iBench contains six tasks ex-ercising user actions typical for iPhoto:starting the application and importing,duplicating,editing,viewing,and deleting photos in the library.These tasks modify both the imageﬁles and the underlying database.Each of the iPhoto tasks operates on4002.5MB photos, representing a user who has imported12megapixel photos(2.5MB each)from a full1GBﬂash card on his or her camera.iLife iTunes9.0.3(15):a media player capable of both audio and video playback.iTunes organizes itsﬁles in a private library and supports most common music formats(e.g.,MP3,AIFF,W A VE, AAC,and MPEG-4).iTunes does not employ a database,keeping media metadata and playlists in both a binary and an XMLﬁle. iBench containsﬁve tasks for iTunes:starting iTunes,importing and playing an album of MP3songs,and importing and playing an MPEG-4movie.Importing requires copyingﬁles into the library directory and,for music,analyzing each songﬁle for gapless play-back.The music tasks operate over an album(or playlist)of ten songs while the movie tasks use a single3-minute movie.iLife iMovie8.0.5(820):video editing software.iMovie stores its data in a library that contains directories for raw footage and projects,andﬁles containing video footage thumbnails.iMovie supports both MPEG-4and Quicktimeﬁles.iBench contains four tasks for iMovie:starting iMovie,importing an MPEG-4movie, adding a clip from this movie into a project,and exporting a project to MPEG-4.The tasks all use a3-minute movie because this is a typical length found from home users on video-sharing websites. iWork Pages4.0.3(766):a word processor.Pages uses a ZIP-basedﬁle format and can export to DOC,PDF,RTF,and basic text. iBench includes eight tasks for Pages:starting up,creating and saving,opening,and exporting documents with and without images and with different formats.The tasks use15page documents. iWork Numbers2.0.3(332):a spreadsheet application.Num-bers organizes itsﬁles with a ZIP-based format and exports to XLS and PDF.The four iBench tasks for Numbers include starting Num-bers,generating a spreadsheet and saving it,opening the spread-sheet,and exporting that spreadsheet to XLS.To model a possible home user working on a budget,the tasks utilize aﬁve page spread-sheet with one column graph per sheet.iWork Keynote5.0.3(791):a presentation and slideshow appli-cation.Keynote saves to a.key ZIP-based format and exports to Microsoft’s PPT format.The seven iBench tasks for Keynote in-clude starting Keynote,creating slides with and without images, opening and playing presentations,and exporting to PPT.Each Keynote task uses a20-slide presentation.Accesses I/O MB Name DescriptionFiles (MB)Accesses (MB)RD%WR%/CPU Sec/CPU Seci L i f e i P h o t oStart Open iPhoto with library of 400photos 779(336.7)828(25.4)78.821.2151.1 4.6Imp Import 400photos into empty library 5900(1966.9)8709(3940.3)74.425.626.712.1Dup Duplicate 400photos from library2928(1963.9)5736(2076.2)52.447.6237.986.1Edit Sequentially edit 400photos from library 12119(4646.7)18927(12182.9)69.830.219.612.6Del Sequentially delete 400photos;empty trash 15246(23.0)15247(25.0)21.878.2280.90.5View Sequentially view 400photos 2929(1006.4)3347(1005.0)98.1 1.924.17.2i T u n e s Start Open iTunes with 10song album 143(184.4)195(9.3)54.745.372.4 3.4ImpS Import 10song album to library 68(204.9)139(264.5)66.333.775.2143.1ImpM Import 3minute movie to library 41(67.4)57(42.9)48.052.0152.4114.6PlayS Play album of 10songs 61(103.6)80(90.9)96.9 3.10.40.5PlayM Play 3minute movie56(77.9)69(32.0)92.37.7 2.2 1.0i M o v i e Start Open iMovie with 3minute clip in project 433(223.3)786(29.4)99.90.1134.8 5.0Imp Import 3minute .m4v (20MB)to “Events”184(440.1)383(122.3)55.644.429.39.3Add Paste 3minute clip from “Events”to project 210(58.3)547(2.2)47.852.2357.8 1.4Exp Export 3minute video clip 70(157.9)546(229.9)55.144.9 2.3 1.0i W o r kP a g e s Start Open Pages218(183.7)228(2.3)99.90.197.7 1.0New Create 15text page document;save as .pages 135(1.6)157(1.0)73.326.750.80.3NewP Create 15JPG document;save as .pages 408(112.0)997(180.9)60.739.354.69.9Open Open 15text page document 103(0.8)109(0.6)99.50.557.60.3PDF Export 15page document as .pdf 107(1.5)115(0.9)91.09.041.30.3PDFP Export 15JPG document as .pdf 404(77.4)965(110.9)67.432.649.7 5.7DOC Export 15page document as .doc 112(1.0)121(1.0)87.912.144.40.4DOCP Export 15JPG document as .doc 385(111.3)952(183.8)61.138.946.38.9N u m b e r s Start Open Numbers283(179.9)360(2.6)99.60.4115.50.8New Save 5sheets/column graphs as .numbers 269(4.9)313(2.8)90.79.39.60.1Open Open 5sheet spreadsheet119(1.3)137(1.3)99.80.248.70.5XLS Export 5sheets/column graphs as .xls 236(4.6)272(2.7)94.9 5.18.50.1K e y n o t e Start Open Keynote517(183.0)681(1.1)99.80.2229.80.4New Create 20text slides;save as .key 637(12.1)863(5.4)92.47.6129.10.8NewP Create 20JPG slides;save as .key654(92.9)901(103.3)66.833.270.88.1Play Open and play presentation of 20text slides 318(11.5)385(4.9)99.80.295.0 1.2PlayP Open and play presentation of 20JPG slides 321(45.4)388(55.7)69.630.472.410.4PPT Export 20text slides as .ppt 685(12.8)918(10.1)78.821.2115.2 1.3PPTP Export 20JPG slides as .ppt 723(110.6)996(124.6)57.642.461.07.6Table 1:34Tasks of the iBench Suite.The table summarizes the 34tasks of iBench,specifying the application,a short name for the task,and a longer description of the actions modeled.The I/O is characterized according to the number of ﬁles read or written,the sum of the maximum sizes of all accessed ﬁles,the number of ﬁle accesses that read or write data,the number of bytes read or written,the percentage of I/O bytes that are part of a read (or write),and the rate of I/O per CPU-second in terms of both ﬁle accesses and bytes.Each core is counted individually,so at most 2CPU-seconds can be counted per second on our dual-core test machine.CPU utilization is measured with the UNIX top utility,which in rare cases produces anomalous CPU utilization snapshots;those values are ignored.Table 1contains a brief description of each of the 34iBench tasks as well as the basic I/O characteristics of each task when running on Mac OS X Snow Leopard 10.6.2.The table illustrates that the iBench tasks perform a signiﬁcant amount of I/O.Most tasks access hundreds of ﬁles,which in aggregate contain tens or hundreds of megabytes of data.The tasks typically access ﬁles hundreds of times.The tasks perform widely differing amounts of I/O,from less than a megabyte to more than a gigabyte.Most of the tasks perform many more reads than writes.Finally,the tasks exhibit high I/O throughput,often transferring tens of megabytes of data for every second of computation.3.2Easy to UseTo enable other system evaluators to easily use these tasks,the iBench suite is packaged as a set of 34system call traces.To ensure reproducible results,the 34user tasks were ﬁrst automated with AppleScript,a general-purpose GUI scripting language.Apple-Script provides generic commands to emulate mouse clicks through menus and application-speciﬁc commands to capture higher-level operations.Application-speciﬁc commands bypass a small amount of I/O by skipping dialog boxes;however,we use them whenever possible for expediency.The system call traces were gathered using DTrace [8],a kernel and user level dynamic instrumentation tool.DTrace is used toinstrument the entry and exit points of all system calls dealing with the ﬁle system;it also records the current state of the system and the parameters passed to and returned from each call.While tracing with DTrace was generally straightforward,we ad-dressed four challenges in collecting the iBench traces.First,ﬁle sizes are not always available to DTrace;thus,we record every ﬁle’s initial size and compute subsequent ﬁle size changes caused by system calls such as write or ftruncate .Second,iTunes uses the ptrace system call to disable tracing;we circumvent this block by using gdb to insert a breakpoint that automatically re-turns without calling ptrace .Third,the volfs pseudo-ﬁle sys-tem in HFS+(Hierarchical File System)allows ﬁles to be opened via their inode number instead of a ﬁle name;to include path-names in the trace,we instrument the build path function to obtain the full path when the task is run.Fourth,tracing system calls misses I/O resulting from memory-mapped ﬁles;therefore,we purged memory and instrumented kernel page-in functions to measure the amount of memory-mapped ﬁle activity.We found that the amount of memory-mapped I/O is negligible in most tasks;we thus do not include this I/O in the iBench traces or analysis.To provide reproducible results,the traces must be run on a sin-gle ﬁle-system image.Therefore,the iBench suite also contains snapshots of the initial directories to be restored before each run;initial state is critical in ﬁle-system benchmarking [1].4.ANALYSIS OF IBENCH TASKSThe iBench task suite enables us to study the I/O behavior of a large set of home-user actions.As shown from the timeline of I/O behavior for one particular task in Section2,these tasks are likely to accessﬁles in complex ways.To characterize this complex behavior in a quantitative manner across the entire suite of34tasks, we focus on answering four categories of questions.•What different types ofﬁles are accessed and what are the sizes of theseﬁles?•How areﬁles accessed for reads and writes?Areﬁles ac-cessed sequentially?Is space preallocated?•What are the transactional properties?Are writesﬂushed with fsync or performed atomically?•How do multi-threaded applications distribute I/O across dif-ferent threads?Answering these questions has two beneﬁts.First,the answers can guideﬁle and storage system developers to target their systems better to home-user applications.Second,the characterization will help users of iBench to select the most appropriate traces for eval-uation and to understand their resulting behavior.All measurements were performed on a Mac Mini running Mac OS X Snow Leopard version10.6.2and the HFS+ﬁle system. The machine has2GB of memory and a2.26GHz Intel Core Duo processor.4.1Nature of FilesOur analysis begins by characterizing the high-level behavior of the iBench tasks.In particular,we study the different types ofﬁles opened by each iBench task as well as the sizes of thoseﬁles. 4.1.1File TypesThe iLife and iWork applications store data across a variety of ﬁles in a number of different formats;for example,iLife applica-tions tend to store their data in libraries(or data directories)unique to each user,while iWork applications organize their documents in proprietary ZIP-basedﬁles.The extent to which tasks access dif-ferent types ofﬁles greatly inﬂuences their I/O behavior.To understand accesses to differentﬁle types,we place eachﬁle into one of six categories,based onﬁle name extensions and us-age.Multimediaﬁles contain images(e.g.,JPEG),songs(e.g., MP3,AIFF),and movies(e.g.,MPEG-4).Productivityﬁles are documents(e.g.,.pages,DOC,PDF),spreadsheets(e.g.,.numbers, XLS),and presentations(e.g.,.key,PPT).SQLiteﬁles are database ﬁles.Plistﬁles are property-listﬁles in XML containing key-value pairs for user preferences and application properties.Stringsﬁles contain strings for localization of application text.Finally,Other contains miscellaneousﬁles such as plain text,logs,ﬁles without extensions,and binaryﬁles.Figure2shows the frequencies with which tasks open and ac-cessﬁles of each type;most tasks perform hundreds of these ac-cesses.Multimediaﬁle opens are common in all workloads,though they seldom predominate,even in the multimedia-heavy iLife ap-plications.Conversely,opens of productivityﬁles are rare,even in iWork applications that use them;this is likely because most iWork tasks create or view a single productivityﬁle.Because.plistﬁles act as generic helperﬁles,they are relatively common.SQLiteﬁles only have a noticeable presence in iPhoto,where they account for a substantial portion of the observed opens.Stringsﬁles occupy a signiﬁcant minority of most workloads(except iPhoto and iTunes). Finally,between5%and20%ofﬁles are of type“Other”(except for iTunes,where they are more prevalent).Figure3displays the percentage of I/O bytes accessed for each ﬁle type.In bytes,multimedia I/O dominates most of the iLife tasks,while productivity I/O has a signiﬁcant presence in the iWork tasks;ﬁle descriptors on multimedia and productivityﬁles tend to receive large amounts of I/O.SQLite,Plist,and Stringsﬁles have a smaller share of the total I/O in bytes relative to the number of openedﬁles;this implies that tasks access only a small quantity of data for each of theseﬁles opened(e.g.,several key-value pairs in a.plist).In most tasks,ﬁles classiﬁed as“Other”receive a more signiﬁcant portion of the I/O(the exception is iTunes). Summary:Home applications access a wide variety ofﬁle types, generally opening multimediaﬁles the most frequently.iLife tasks tend to access bytes primarily from multimedia orﬁles classiﬁed as“Other”;iWork tasks access bytes from a broader range ofﬁle types,with some emphasis on productivityﬁles.4.1.2File SizesLarge and smallﬁles present distinct challenges to theﬁle sys-tem.For largeﬁles,ﬁnding contiguous space can be difﬁcult,while for smallﬁles,minimizing initial seek time is more important.We investigate two different questions regardingﬁle size.First,what is the distribution ofﬁle sizes accessed by each task?Second,what portion of accessed bytes resides inﬁles of various sizes?To answer these questions,we recordﬁle sizes when each unique ﬁle descriptor is closed.We categorize sizes as very small(<4KB), small(<64KB),medium(<1MB),large(<10MB),or very large (≥10MB).We track how many accesses are toﬁles in each cate-gory and how many of the bytes belong toﬁles in each category. Figure4shows the number of accesses toﬁles of each size.Ac-cesses to very smallﬁles are extremely common,especially for iWork,accounting for over half of all the accesses in every iWork task.Smallﬁle accesses have a signiﬁcant presence in the iLife tasks.The large quantity of very small and smallﬁles is due to frequent use of.plistﬁles that store preferences,settings,and other application data;theseﬁles oftenﬁll just one or two4KB pages. Figure5shows the proportion of theﬁles in which the bytes of accessedﬁles rge and very largeﬁles dominate every startup workload and nearly every task that processes multimedia ﬁles.Smallﬁles account for few bytes and very smallﬁles are essentially negligible.Summary:Agreeing with many previous studies(e.g.,[4]),we ﬁnd that while applications tend to open many very smallﬁles (<4KB),most of the bytes accessed are in largeﬁles(>1MB).4.2Access PatternsWe next examine how the nature ofﬁle accesses has changed, studying the read and write patterns of home applications.These patterns include whetherﬁles are used for reading,writing,or both; whetherﬁles are accessed sequentially or randomly;andﬁnally, whether or not blocks are preallocated via hints to theﬁle system.4.2.1File AccessesOne basic characteristic of our workloads is the division between reading and writing on openﬁle descriptors.If an application uses an openﬁle only for reading(or only for writing)or performs more activity onﬁle descriptors of a certain type,then theﬁle system may be able to make more intelligent memory and disk allocations. To determine these characteristics,we classify each openedﬁle descriptor based on the types of accesses–read,write,or both read and write–performed during its lifetime.We also ignore the ac-tualﬂags used when opening theﬁle since we found they do not accurately reﬂect behavior;in all workloads,almost all write-only ﬁle descriptors were opened with O RDWR.We measure both the。

Ubuntu：Intel+fftw+openmpi+openmx (sequent)

Step 1. Intel更新编译器1.sudo apt-get update sudo apt-get install gcc sudo apt-get install g++sudo apt-get install python gcc --version g++ --version python --version进入目录2.cd parallel_studio_xe_2013_update2_intel64启动3../install.sh欢迎界面，根据提示，基本都是默认选项直接按‘Enter’;4.sudo passwd root a.选择Root选项：passwd；如果是首次使用root，可能会出现密码错误，需要先重设root passwd：5.进入设置界面6.Step no: 1 of 7 | Welcome--------------------------------------------------------------------------------Welcome to the Intel(R) Parallel Studio XE 2013 Update 2 for Linux* installation program.--------------------------------------------------------------------------------You will complete the steps below during this installation:Step 1 : Welcome Step 2 : License Step 3 : ActivationStep 4 : Intel(R) Software Improvement Program Step 5 : Options Step 6 : Installation Step 7 : Complete--------------------------------------------------------------------------------Press "Enter" key to continue or "q" to quit: ‘Enter'CentOS 操作系统会提示不支持，跳过。

ACM2012

Common Mode Choke Coils for Signal Line SMDFEATURES•Although greatly miniaturized, this wire-wound chip-type filter maintains the characteristics needed for a common-mode filter. Common-mode impedance is 1000Ω [at 100MHz], so this filter is greatly effective in supporting noise.•Almost no affect upon even high speed signals since differential mode impedance is kept low.•This series includes both 2-line and 3-line types. They are used for various types of circuits and noise.APPLICATIONS•Used for radiation noise suppression for any electronic devices. •Used to counter common-mode noise affecting signals within high speed lines.•USB line for personal computers and peripheral equipment. •IEEE1394 line for personal computers, DVC, STB, etc.•LVDS, panel link line for liquid crystal display panels.SHAPES AND DIMENSIONS/CIRCUIT DIAGRAMS/RECOMMENDED PC BOARD PATTERNS 2-LINE TYPE ACM2012-2PPRODUCT IDENTIFICATION (1) Series name (2) Dimensions L ×W 2012: 2.0×1.2mm(3) Impedance[at 100MHz]900: 90Ω(4) Number of line 2P:2-line 3P:3-line(5) Packaging styleT: ø180mm reel taping TL: ø330mm reel taping (6) TDK internal code TEMPERATURE RANGESPACKAGING STYLE AND QUANTITIESACM2520-2PACM3225-2PACM 2012 -900-2P -T Operating–25 to +85°CPackaging styleType Reel QuantityTapingACM2012ø330mm 10000 pieces/reel ACM2520ø180mm 2000 pieces/reel ø330mm 10000 pieces/reelACM3225ø330mm 5000 pieces/reel ACM4532ø180mm 500 pieces/reelCommon Mode Choke Coils for Signal Line SMDSHAPES AND DIMENSIONS/CIRCUIT DIAGRAMS/RECOMMENDED PC BOARD PATTERNS 3-LINE TYPE ACM2520-3P ACM4532-102-3PELECTRICAL CHARACTERISTICSPart No.(Ω)typ.[100MHz](Ω)max.[Per 1line]Edc(V)max.Idc(A)max.2-LINEACM2012-201-2P 2000.25500.35ACM2520-451-2P 4500.4200.35ACM2520-601-2P 6000.45200.3ACM3225-800-2P 800.15200.4ACM3225-161-2P 1600.2200.353-LINECommon Mode Choke Coils for Signal Line SMDTYPICAL ELECTRICAL CHARACTERISTICSIMPEDANCE vs. FREQUENCY CHARACTERISTICS ACM2012-900-2P ACM2012-121-2PACM2012-201-2PACM2012-361-2PACM2520-301-2PACM2520-451-2PACM2520-601-2PACM2520-102-2PACM3225-800-2PACM3225-161-2PACM3225-271-2PACM3225-102-2PMEASURING CIRCUITS 2-LINECommon Mode Choke Coils for Signal LineSMDTYPICAL ELECTRICAL CHARACTERISTICSIMPEDANCE vs. FREQUENCY CHARACTERISTICS MEASURING CIRCUITS ACM2520-801-3P ACM4532-102-3P3-LINE。

COMP5211_Algorithms_2012 Semester 2_5_dp

- F(0) = 1 - F(1) = 1 - F(2) = 2 - F(3) = 3 - F(4) = 5
What’s the pattern?
Dynamic Programming - Julián Mestre
2
A counting problem
To see the pattern, condition on the last move
Dynamic Programming - Julián Mestre
7
Recursive algorithm
def MWIS(intervals,w): def helper(i): if i == 0: return 0 return max(helper(i-1), w[i] + helper(p[i])
6
The structure of optimum
Assume intervals are sorted so that f1 ≤ f2 ≤ ⋯ ≤ fn Let OPT(i) be an optimal solution for intervals {1, …, i} Obs 1: If interval n ∉ OPT(n) then OPT(n) = OPT(n-1) Obs 2: If interval n ∈ OPT(n) then OPT(n) = {n} ∪ OPT(p(n)), where p(i) is the largest index such that fp(i) ≤ si Let M(i) be the value of the optimal solution then M(i) = max { M(i-1), w(i) + M(p(i) } for i > 0

withanemphasison

directory – You are ready to go!
MSU NSCL DAQ School—Notre Dame 2006
More to Read
• MSU NSCL DAQ:
– Everything: /daq/index.php
– Software project: /projects/nscldaq
– Tree parameter GUI for powerful manipulation of the definition of parameters, spectra, variables, and gates
– Xamine for easy display and operations of histograms – Tcl/Tk for user-tailorable control GUI and easy extension of
SpectroDaq Data Server
SpecTcl Xamine
Scalers
Scaler Configuration
offline analysis
MSU NSCL DAQ School—Notre Dame 2006
Disk
Hardware Setup
¾ Caen v785, 32-ch ADC ¾ Caen v775, 32-ch TDC ¾ Caen v830, 32-ch Scaler ¾ Trigger to be upgraded
• SpecTcl
– Home: /daq/spectcl/ – Project: /projects/nsclspectcl – Tree Parameters:
/daq/spectcl/treeparam/TreeParameter.html – Tcl/Tk: /

ACER_用户手册说明书

Figure 3: ACER program main window.
Within the first section “Build ACER functions for different k” you have to load data and initiate constants that enable calculation and plotting of ACER functions.
3 www.cesos.ntnu.no
Figure 1: Extraction of files
1. Using “Browse…” and “Install” buttons to extract files. Installation of MATLAB Compiler Runtime (MCR) will start automatically after extracting files. This is crucial since the MATLAB Compiler lets you run ACER_v2 application outside the MATLAB environment. We recommend that you to restart your computer after setup has finished.
ACER_v2_Online_Installer - 3 Mb installation wizard, which also comprises the ACER app, but this time - together with the downloader of the MATLAB Runtime Compiler R2021b. It requires a good stable Internet connection to first download the MCR and then install it and the ACER app. Other than that, the installation wizard is absolutely alike the offline one. Download ACER_v2_Online_Installer.exe

1_PetroMod_2012.1_InstallGuide

Installation Guide Version 2012.1PetroModPetroMod petroleum systems modeling software PetroModPM*Mark of SchlumbergerCopyright © 2012 Schlumberger. All rights reserved.Copyright © 2012 Schlumberger. All rights reserved.This work contains the confidential and proprietary trade secrets of Schlumberger and may not be copied or stored in an information retrieval system, transferred, used, distributed, translated or retransmitted in any form or by any means, electronic or mechanical, in whole or in part, without the express written permission of the copyright owner.Trademarks & Service MarksSchlumberger, the Schlumberger logotype, and other words or symbols used to identify the products and services described herein are either trademarks, trade names or service marks of Schlumberger and its licensors, or are the property of their respective owners. These marks may not be copied, imitated or used, in whole or in part, without the express prior written permission of Schlumberger. In addition, covers, page headers, custom graphics, icons, and other design elements may be service marks, trademarks, and/or trade dress of Schlumberger, and may not be copied, imitated, or used, in whole or in part, without the express prior written permission of Schlumberger. Other company, product, and service names are the properties of their respective owners.An asterisk (*) is used throughout this document to designate a mark of Schlumberger.iv PetroMod 2012.1 Installation GuideContents1 Information Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-1Schlumberger Product Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-2 About Schlumberger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-2 Documentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-2 Typestyle Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-2 Alert Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-2 Contacting Schlumberger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-3 Technical Support . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1-32 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2-1Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2-2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2-2 Audience . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2-2 System Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2-2 Licensing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2-43 Installation (Windows) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-1Downloading the Installation Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-2 Installing PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-3 Installing PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-3 Files Installed During Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-6 Optional: Installing Runtime Environment for Parallel Processing . . . . . . . . . . . . . . . . . . . . . . . .3-7 Installing Runtime Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-7 Activating Parallel Processing in the PetroMod Simulation Interface . . . . . . . . . . . . . . . . . . .3-7 Installing the Licensing Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-9 CodeMeter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3-9 Schlumberger Licensing Tool . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-10 Configuring the PetroMod License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13 Before you start . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13 Obtaining the license . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-13 Activating a local license . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-14 Activating an external license server . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-15 Checking the License Status . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3-16Contents v4 Uninstalling PetroMod (Windows) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4-1Uninstalling PetroMod (Windows) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4-2 Before You Begin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4-2 Uninstalling PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4-2 Results of the Uninstallation Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .4-25 Installation (Unix) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-1Downloading the Installation Package . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-2 Installing PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-3 Installing PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-3 Files Installed During Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-4 Parallel Processing Set-up (Systems Admin) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-6 Intel MPI runtime . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-6 PetroMod Machine Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-6 Configuring users for ssh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-7 Configuring users for rsh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-7 Activating Parallel Processing in PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-8 Load Sharing Facility (LSF) in Conjunction with Parallel PetroMod . . . . . . . . . . . . . . . . . . . . . . .5-9 Editing the MPI location . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-9 Intel MPI Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .5-9 Running Parallel PetroMod with Queuing Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-10 Running PetroMod Software with LSF . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-10 Configuring the License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-12 Setting the Environment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-12 Obtaining a License Key . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-12 Setting up the License Server (Systems Administrator) . . . . . . . . . . . . . . . . . . . . . . . . . . . 5-136 Uninstalling PetroMod (Unix) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6-1Uninstalling PetroMod (Unix) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6-2 Before You Begin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6-2 Uninstalling PetroMod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6-2 Files Removed During Uninstallation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6-2vi PetroMod 2012.1 Installation Guide1Information ResourcesIn This SectionSchlumberger Product Documentation.........................................................1-2About Schlumberger.............................................................................1-2Documentation.....................................................................................1-2Typestyle Conventions..........................................................................1-2Alert Statements..................................................................................1-2 Contacting Schlumberger............................................................................1-3Technical Support.................................................................................1-3Information Resources1-1Schlumberger Product Documentation1-2PetroMod 2012.1 Installation Guide Schlumberger Product DocumentationAbout Schlumberger Schlumberger is the leading oilfield services provider, trusted to deliver superiorresults and improved E&P performance for oil and gas companies around the world.Through our well site operations and in our research and engineering facilities, wedevelop products, services, and solutions that optimize customer performance in asafe and environmentally sound manner.Documentation Documentation is provided in the following electronic formats via the listed location:•PetroMod 2012.1 Installation Guide (Adobe ® Acrobat ® PDF file):https://•PetroMod 2012.1 User Guides (Adobe ® Acrobat ® PDF files):https://•Online help for some applications: PetroMod -> HelpYou must have Adobe ® Reader ® installed to read the PDF files. Adobe Readerinstallation programs for common operating systems are available for a freedownload from the Adobe Web site at .Typestyle Conventions The following conventions are observed throughout this guide:•Bold text is used to designate file and folder names, dialog titles, names ofbuttons, icons, and menus, and terms that are objects of a user selection.•Italic text is used for word emphasis, defined terms, and manual titles.•Monospace text (Courier ) is used to show literal text as you would enter it, or asit would appear onscreen.Alert Statements The alerting statements are Notes, Cautions, and Warnings. These statements areformatted in the following style:• • • • • •Note:Information that is incidental to the main text flow, or to an important pointor tip provided in addition to the previous statement or instruction.• • • • • •Caution:Advises of machine or data error that could occur should the user fail totake or avoid a specified action.• • • • • •Warning:Requires immediate action by the user to prevent actual loss of data orwhere an action is irreversible, or when physical damage to themachine or devices is possible.Contacting SchlumbergerInformation Resources1-3Contacting SchlumbergerTechnical Support Schlumberger has sales and support offices around the world. For information oncontacting Schlumberger, please refer to the information below.For Technical Support for PetroMod software please contact the Customer CareCenter via the Schlumberger Support Portal at https://Internet Postal Mail SchlumbergerAachen Technology Center (AaTC)Ritterstr . 2352072 Aachen - GermanyContacting Schlumberger1-4PetroMod 2012.1 Installation Guide2Getting StartedIn This ChapterOverview...................................................................................................2-2Introduction.........................................................................................2-2System Requirements...........................................................................2-2System Requirements...........................................................................2-2Licensing.............................................................................................2-4Getting Started2-1Overview2-2PetroMod 2012.1 Installation Guide OverviewIntroduction This document describes the steps necessary to install PetroMod* 2012.1. Theinstaller includes a full PetroMod installation.•Installing on a workstation using a local license•Installing on a workstation using a license on a central license serverThis guide also explains the procedures required after installation:•Defining your license environmentThis module has been designed by the Schlumberger Aachen Technology Center(AaTC), Germany.Audience This guide is useful for the following people:•PetroMod users who install PetroMod on their workstations•System Administrator who installs PetroMod on a network shared diskSystem Requirements Before you install PetroMod 2012.1 your machine must meet the followingrequirements:Hardware Requirements Table 2-1Hardware Requirements for workstation (e.g. Dell T7500)Table 2-2Hardware Requirements for laptop (e.g. Dell M4600)Computer CPU 2 x Intel X5667 (quad core) or X5675 (hexa core)Physical Memory12 GB RAM Hard Disk Space 5 GB of free disk space Graphic Card Nvidia Quadro 5000 Network Card 1000 Mbit NicComputerIntel Core i7-2860Q 2.5 GHz Physical Memory16 GB RAM Hard Disk Space5 GB of free disk space Graphic CardNvidia Quadro 2000MOverviewGetting Started2-3Table 2-3Hardware Requirements for Linux Cluster • • • • • •Warning:Linux Users - Due to known issues concerning the instability ofOpenGL graphics, PetroMod only supports local rendering on 3Dgraphic cards with stable graphic drivers. Rendering via a networkcould cause stability issues. In particular, we observed problems withthe Mesa OpenGL package that is delivered with RHEL5 and works asa fall-back when no other driver is installed.Software Requirements Table 2-4Software Requirements • • • • • •Caution:It is possible that graphics do not display correctly when using older ATIgraphics cards and drivers. Thus, we recommend the use of Nvidiagraphics cards. We also recommend to install the latest graphicsdrivers available from Nvidia to avoid OpenGL graphic display errors.The driver version that comes with the OS in most cases is quite old oreven generic drivers are used if the graphics hardware is notrecognized correctly during the installation of the OS. These driversonly support basic functionalities and do not offer the OpenGL featuresrequired by PetroMod. Please be aware that most onboard graphicshardware does not support OpenGL at all. A dedicated graphics card isrequired for PetroMod.• • • • • •Note:Software applications created under older operating system versions willrun under newer operating system versions, but not vice puter CPU 2 x Intel X5667 (quad core) or X5675 (hexa core)Physical Memory48GB RAM Network Card1000 Mbit Nic Hard Disk Space 5 GB of free disk space Microsoft Vista 64-bit Microsoft Windows 7(recommended)64-bit RedHat EnterpriseLinux 5.3(recommended)64 bit Framework 2.0OverviewLicensing Licenses are required to access PetroMod. Certain functionalities or modules willonly be available with the respective licenses. Contact your Schlumberger SISCustomer Support representative to obtain the necessary licensesMaintenance contracts are usually yearly contracts, renewed at any time during theyear. Prior to 2012.1, PetroMod licenses allowed you to step up to a new PetroModversion based on the PetroMod license expiration date without having a validmaintenance contract. Beginning with 2012.1, upgrades are based on yourmaintenance contract expiration date. This is how you read the new licensingformat:FEATURE petrobuilder3D slbsls <yyyy.mm> <dd-mmm-yyyy> <#>Where• <yyyy.mm> is the maintenance expiration year and month• <dd-mmm-yyyy> is the license expiration day, month, year• <#> is the number of licensesMaintenance renewal is required to run any PetroMod version released after yourmaintenance expiration date. You will be automatically contacted by SchlumbergerInformation Systems before your maintenance expires.2-4PetroMod 2012.1 Installation Guide3Installation (Windows)In This ChapterDownloading the Installation Package..........................................................3-2Installing PetroMod.....................................................................................3-3Installing PetroMod...............................................................................3-3Files Installed During Installation...........................................................3-6 Optional: Installing Runtime Environment for Parallel Processing....................3-7Installing Runtime Environment.............................................................3-7Activating Parallel Processing in the PetroMod Simulation Interface..........3-7 Installing the Licensing Tool........................................................................3-9CodeMeter...........................................................................................3-9Schlumberger Licensing Tool................................................................3-10 Configuring the PetroMod License...............................................................3-13Before you start..................................................................................3-13Obtaining the license...........................................................................3-13Activating a local license......................................................................3-14Activating an external license server.....................................................3-15Checking the License Status.................................................................3-16Installation (Windows)3-1Downloading the Installation PackageDownloading the Installation PackageTo install PetroMod, you need the installation package. If you have a DVD, you canuse it. Otherwise, download PetroMod from the Software Download Center.••••••Note:If you are a new user of the Software Download Center, you must registerbefore you can download PetroMod.To download PetroMod 2012 from the Software Download Center1Go to .2Click SIS Software download center.3Log in to the site.4On the Welcome Message page, click Continue.5In the Product Group Name list (in the upper-left corner), click Geology &Geophysics.6In the table on the right, click PetroMod.7In the table of PetroMod downloads, click the Download icon for the PetroMod2012.1 file you need.You are ready to install PetroMod 2012.3-2PetroMod 2012.1 Installation GuideInstalling PetroModInstallation (Windows)3-3Installing PetroModPerform the following tasks prior to beginning the installation:•Ensure that you have admin privileges on the machine on which you are installing PetroMod and/or install the software together with your systems administrator since superuser passwords are required.•Ensure that the “System Requirements” on page 2-2 are met.PetroMod 2012 is a full installation. If you are already using an earlier PetroMod release, copy the new release into a new directory! Do not install the new version ‘over’ the old version to ensure that all programs and files can be updated and will then be compatible.Installing PetroMod The installation ensures that the files required to run PetroMod are installed on yourcomputer.To Install PetroMod 20121Insert the DVD or navigate to the location where you downloaded theinstallation files.2Double-click PetroMod2012.1.exe to start the installation. The folderPetroMod2012.1.msi will be unpacked, then the InstallShield Wizard will open, see Fig. 3-1. Click Next .Fig. 3-1PetroMod InstallShield Wizard3Fill in your User Name and Organization , see Fig. 3-2, then click Next.Installing PetroMod3-4PetroMod 2012.1 Installation GuideFig. 3-2Filling in user name and organization 4Determine the location of the files, see Fig. 3-3. Default is a folder calledSchlumberger in your Program Files folder. If this is not what you want you need to change that manually by clicking the Change button.When you are content with the location, click Next.Fig. 3-3Determining the location of the files 5 A summary of the settings will be displayed, see Fig. 3-4. Click Install .Installing PetroModInstallation (Windows)3-5Fig. 3-4Summary of settings 6You can follow the progress of the installation in the InstallShield Wizard, seeFig. 3-5.Fig. 3-5Installation progress 7Once the installation is complete the InstallShield Wizard will display the finaldialog, see Fig. 3-6. Click Finish .Installing PetroMod3-6PetroMod 2012.1 Installation Guide Fig. 3-6Installation complete 8The PetroMod 2012.1 icon will appear on your desktop . PetroMod 2012.1 willalso be added to the Schlumberger folder in the Progams list of your Start menu.Proceed with the installation of the .NETruntime environment, the MS HPC runtime for parallel processing and / or with installing Flexnet.Files Installed During Installation The following files / folders are installed during the installation of PetroMod:•one folder: PetroMod 2012.1:-client folder incl. sub folders/files-cult folder incl. sub folders/files-def folder incl. sub folders/files-doc folder incl. sub folders/files-geo folder incl. sub folders/files-well folder incl. sub folders/files-WIN64 folder incl. sub folders/files-PetroMod2012.1.batOptional: Installing Runtime Environment for Parallel Processing Optional: Installing Runtime Environment for Parallel ProcessingPetroMod 2012.1 supports parallel processing on Windows platforms usingMicrosoft HPC Pack 2008 R2 SP3. Using parallel processing from the SimulationInterface Microsoft requires the previous installation of Microsoft HPC runtimeenvironment.Installing Runtime Environment You can find the files in the installation package in the RuntimeEnvironment/ Windows folder:•mpi_x64.exe - MS MPI runtime•HpcClient_x64.exe - MS HPC web interface (optional)Once you have installed the files you need to obtain and activate the necessary licenses.••••••Note:If you want to consolidate your existing MS HPC runtime environments (installed with PM 11 or PetroMod 2011) to the latest version that shipswith PetroMod 2012.1, then you have to uninstall the MS HPC Pack 2008SDK on your system and manually set the required environment variable(called CCP_SDK) to C:\Program Files|Microsoft HPC Pack 2008 R2.Otherwise, PetroMod 2011.1 or PetroMod 11 SP4 will complain about themissing MPI runtime environment.Activating Parallel Processing in the PetroMod Simulation Interface 1After the licenses have been activated open the PetroMod Simulation Interface and select Processors for Parallel Run, see Fig. 3-7.Fig. 3-7Activating parallel processing in the PetroMod Simulation InterfaceOptional: Installing Runtime Environment for Parallel Processing2Increase the number of processors in the Processors Selection dialog.••••••Caution:Parallel processing is only supported on your local machine. Youcannot run a simulation on several nodes (as you could on Linuxclusters).Installing the Licensing Tool Installing the Licensing ToolPetroMod 2012 supports the use of the CodeMeter dongle as well as HOSTIDs forlicense authentication.•If you use CodeMeter, you must install CodeMeter software prior to installing theSchlumberger Licensing tool.•If you use HOSTIDs, you can continue by installing the Schlumberger Licensingtool.CodeMeter PetroMod 2012 uses the CodeMeter dongle for license authentication. Before youinsert your CodeMeter dongle into a USB port on your local workstation or on acentral license server, you must install the CodeMeter software. You should useCodeMeter 4.40 in the following circumstances:•If you use a local license (that is, your local workstation is your local licenseserver), install the CodeMeter dongle, appropriate CodeMeter driver, and theSchlumberger Licensing tool on your computer.•If you use a license on a central license server, the Administrator installs theCodeMeter dongle, CodeMeter driver, and the Schlumberger Licensing tool on theserver. Individual users do not need to install any licensing hardware or softwareon their computers.Installing CodeMeter Follow the steps in this section to uninstall previous versions of CodeMeter, andinstall the version required for this PetroMod release.◆To uninstall previous versions of CodeMeterIf you have an older version of CodeMeter installed on your computer, uninstall itand then install the latest version.1If you want to check the version of CodeMeter you are currently using beforeuninstalling it, on the Windows toolbar right-click the CodeMeter icon and selectAbout to open the About CodeMeter window.2Remove your CodeMeter dongle from the USB port.3Select Start > Control Panel > Programs and Features.4On the list of currently installed programs, select CodeMeter Runtime Kit vx.x.5Click Remove.You are ready to install the latest CodeMeter version.◆To install Codemeter••••••Note:CodeMeter automatically installs in your default Program Files directory:%program files%/Codemeter (usually C:/Program Files).1From the Licensing folder in the PetroMod installation package run the correctprogram (.exe) file:Installing the Licensing Tool•For PetroMod 64-bit, run CodeMeterRuntime64.exeAlternatively, go to the CodeMeter website () anddownload CodeMeter 4.40 from their website.The CodeMeter installation wizard opens.2On the Welcome panel, click Next.3On the License Agreement panel, read the agreement, select I accept thelicense agreement, and then click Next.4On the User Information panel, enter your name, your company’s name, andwho will use CodeMeter on your computer, and then click Next.5On the Select Features panel, select the features you want to install and thenclick Next.Schlumberger recommends that you accept the default settings.6On the Ready to Install panel, click Next to begin the installation.7When the installation is complete, on the last panel click Finish.8Restart your computer.The CodeMeter icon appears in your Windows taskbar. When you insert yourCodeMeter dongle into the USB port, the icon changes to show that your computerrecognizes the dongle. If you double-click the icon, you can view information aboutthe dongle.You are ready to install the Schlumberger Licensing tool.Schlumberger Licensing Tool PetroMod uses FlexNet for licensing. The Schlumberger Licensing tool is a simple interface for FlexNet. Using the Schlumberger Licensing 2012 tool to configure and manage your PetroMod license is recommended, but you may use FlexNet tools instead.If you do not already have the Schlumberger licensing tool on your computer, install the Licensing tool as follows:•If you use a local license (that is, your local workstation is your local license server), install the licensing tool on your computer.•If you use a license on a central license server, the Administrator installs the licensing tool on the server. The Schlumberger Licensing tool is not required for the Administrator to install, configure, and manage the PetroMod license. The Administrator may choose to manage PetroMod licenses with FlexNet native tools.The computer that you use to run the Schlumberger licensing tool is the license server for your PetroMod 2012 installaton.Installing the Schlumberger Licensing Tool Follow the steps in this section to install the Schlumberger Licensing tool. If you have a previous version of the licensing tool and want the latest version (2012), uninstall the older version first, and then install the latest version.。

1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

Dynamic programming - Julián Mestre
4
RNA’s secondary structure
A RNA molecule can be represented as a string over the alphabet {A, C, G, U}; each character is called a base. Some bases pair up, causing the strand to fold onto itself. This pairing is called RNA secondary structure
- A single position may change to a different letter - A letter (or several) may be deleted - A letter (or several) may be added
Each of these can happen with some low probability. Over evolutionary time, these low probability events accumulate. The longer two species have diverged, the more differences we should see.
Nature prefers low energy conﬁgurations. In our case this means minimizing the number of unmatched positions
Dynamic programming - Julián Mestre
6
RNA secondary structure prediction
Dynamic programming - Julián Mestre
2
Nim
Board conﬁgurations can be classiﬁed into:
- winning : if player 1 can force a win, no matter what player 2 does - losing : if player 2 can force a win, no matter what player 1 does
- for each (i,j) in M such that xi ≠ yj we pay a mismatch cost α(xi,yj) - for each position in X or Y left unmatched we pay a gap penalty δ
Dynamic programming - Julián Mestre
3
RNA
RNA is a close relative of DNA but has a single strand of genetic code Unlike DNA, which folds into a double helix shape, RNA folds onto itself The 3D structure of RNA inﬂuences its behavior and molecular function
10
Dynamic programming - Julián Mestre
7
DNA sequence alignment
A fundamental task in biology is to determine how closely related two organisms are. For this we compare their DNA sequences. DNA sequence is string over the alphabet {A, G, C, T} Similar sequences:
- AGCCTATGCAT - AGCTቤተ መጻሕፍቲ ባይዱATAAGCAT
Dissimilar sequences
- AGCCTATGCAT - GGTATGCAACT
Dynamic programming - Julián Mestre
8
DNA sequences drift with time
Over time, mutations introduce changes in the DNA sequence of a species
Input:
- String over the alphabet {A, C, G, U}
Task:
- Find a matching S obeying properties (i)-(iv) that maximizes |S|
Properties:
- (i) [Matching] Each position is matched at most once - (ii) [Compatible matches] Only matches A-U and C-G are allowed - (iii) [No sharp turns] If (i,j) is a match then |i-j| > 4 - (iv) [Non crossing] If (i,j) and (k,l) are matched then intervals are either disjoint or nested in one another.
Dynamic programming - Julián Mestre
9
Sequence alignment
Let X=x1, x2, ..., xn and Y= y1, y2, ..., ym be two string. An alignment is a matching M between positions of the two string such that there are no crossings: if (i,j) in M and (i’, j’) in M then if i < i’ then j < j’ Associated with a matching there is a cost:
Algorithms and Complexity
Dynamic programming
Julián Mestre School of Information Technologies The University of Sydney
Nim
The game of Nim:
- Two player game - On the table there are heaps of matches - Players take turns - On each turn a player picks a heap and removes one or more matches - The player to take the last match from the table wins
Input:
- Board conﬁguration (a, b, c)
Task:
- Determine if (a, b, c) is a winning conﬁguration - If so, compute winning move
Dynamic programming - Julián Mestre
- [Matching] Each position is matched at most once - [Compatible matches] Only matches A-U and C-G are allowed - [No sharp turns] If (i,j) is a match then |i-j| > 4 - [Non crossing] If (i,j) and (k,l) are matched then intervals are either disjoint or nested in one another.
Dynamic programming - Julián Mestre
5
Matching bases
Let S be the set of paired positions. If (i,j) in S then we say that position i is matched to position j The pairing S must obey some properties

高一物理必修二机械能守恒定律单元测试及答案

页数:3
高中物理 7.8机械能守恒定律(精讲优练课型)课件新人教版必修2

页数:15
高中物理必修2机械能守恒定律教材分析

页数:2
高中物理必修二—机械能守恒定律

页数:32
人教版高中物理必修二机械能守恒定律

页数:8
高一必修2物理机械能守恒定律知识点总结

页数:2
必修二练习机械能守恒与能量守恒定律

页数:9
人教版高中物理必修二验证机械能守恒定律

页数:13
物理必修二_机械能守恒定律知识点总结

页数:4
高中物理必修二第七章-机械能守恒定律知识点总结

页数:4