Better External Memory Su?x Array Construction
Roman Dementiev?,Juha K¨a rkk¨a inen?,Jens Mehnert?,Peter Sanders?
Abstract
Su?x arrays are a simple and powerful data structure
for text processing that can be used for full text indexes,
data compression,and many other applications in par-
ticular in bioinformatics.However,so far it has looked
prohibitive to build su?x arrays for huge inputs that do
not?t into main memory.This paper presents design,
analysis,implementation,and experimental evaluation
of several new and improved algorithms for su?x array
construction.The algorithms are asymptotically opti-
mal in the worst case or on the average.Our imple-
mentation can construct su?x arrays for inputs of up
to4GBytes in hours on a low cost machine.
As a tool of possible independent interest we present
a systematic way to design,analyze,and implement
pipelined algorithms.
1Introduction
The su?x array[21,13],a lexicographically sorted array
of the su?xes of a string,has numerous applications,
e.g.,in string matching[21,13],genome analysis[1]and
text compression[6].For example,one can use it as full
text index:To?nd all occurrences of a pattern P in a
text T do binary search in the su?x array of T,i.e.,look
for the interval of su?xes that have P as a pre?x.A
lot of e?ort has been devoted to e?cient construction of
su?x arrays,culminating recently in three direct linear
time algorithms[17,18,19].One of the linear time
algorithms[17]is very simple and can also be adapted
to obtain an optimal algorithm for external memory:
The DC3-algorithm[17]constructs a su?x array of a
text T of length n using O(sort(n))I/Os where sort(n)
is the number of I/Os needed for sorting the characters
of T.
However,su?x arrays are still rarely used for
processing huge inputs.Less powerful techniques like
an index of all words appearing in a text are very
simple,have favorable constant factors and can be
a role in our analysis.
maxlcp:=max
0≤i (1.1) n 0≤i lcp(i,i+1) (1.2) log dps:= 1 DB log M/B x M scan(n) I/Os.We have not implemented this al- gorithm not only because more scalable algorithms are more interesting but also because all our algorithmic improvements(pipelining,discarding,quadrupling,the DC3-algorithm)add to a dramatic reduction in I/O volume and are not applicable to the GBS-algorithm. Moreover,the GBS-algorithm is quite expensive with respect to internal work,which contributes signi?cantly to the running time on our system as shown by the ex-periments.Nevertheless it should be kept in mind that the GBS-algorithm might be interesting for small inputs and fast machines with slow I/O. There is a very recent study of external su?x tree construction for the case that the text itself?ts in inter-nal memory[7].The proposed algorithm has quadratic worst case complexity.Experiments are reported for up to224·106characters(human chromosome1)and only optimistic estimates of I/O performance rather than ac-tual execution times are given. There has been considerable interest in space e?-cient internal memory algorithms for constructing suf-?x arrays[22,5]and even more compact full-text in- dexes[20,14,15].We view this as an indication that internal memory is too expensive for the big su?x ar-rays one would like to build.Going to external memory can be viewed as an alternative and more scalable so-lution to this problem.Once this step is made,space consumption is less of an issue because disk space is two orders of magnitude cheaper than RAM. The biggest su?x array computations we are aware of are for the human genome[23,20].One[20]computes the compressed su?x array on a PC with3GBytes of memory https://www.doczj.com/doc/ea15068687.html,pressed su?x arrays work well in this case(they need only2GByte of space)because the small alphabet size present in genomic information enables e?cient compression.The other implementa-tion[23]uses a supercomputer with64GBytes of mem-ory and needs7hours.Our algorithms have comparable speed using external memory. Pipelining to reduce I/Os is well known technique in executing database queries[24].However,previous algorithm libraries for external memory[4,9]do not support it.We decided quite early in the design of our library Stxxl[10]that we wanted to remove this de?cit.Since su?x array construction can pro?t im-mensely from pipelining and since the di?erent algo-rithms give a rich set of examples,we decided to use this application as a test bed for a prototype implemen-tation of pipelining. 2Doubling Algorithm Figure1gives pseudocode for the doubling algorithm. The basic idea is to replace characters T[i]of the input by lexicographic names that respect the lexicographic order of the length2k substring T[i,i+2k)in the k-th iteration.In contrast to previous variants of this algorithm,our formulation never actually builds the resulting string of names.Rather,it manipulates a sequence P of pairs(c,i)where each name c is tagged with its position i in the input.To obtain names for the next iteration k+1,the names for T[i,i+2k) and T[i+2k,i+2k+1)together with the position i are stored in a sequence S and sorted.The new names can now be obtained by scanning this sequence and comparing adjacent tuples.Sequence S can be build using consecutive elements of P if we sort P using the pair(i mod2k,i div2k).Previous formulations of the algorithm use i as a sorting criterion and therefore have to access elements that are2k characters apart. Our approach saves I/Os and simpli?es the pipelining optimization described in Section3. The algorithm performs a constant number of sort-ing and scanning operations for sequences of size n in each iteration.The number of iterations is determined by the logarithm of the longest common pre?x.Function doubling(T) S:=[((T[i],T[i+1]),i):i∈[0,n)](0) for k:=1to log n do sort S(1) P:=name(S)(2) invariant?(c,i)∈P: c is a lexicographic name for T[i,i+2k) if the names in P are unique then return[i:(c,i)∈P](3) sort P by(i mod2k,i div2k))(4) S:= ((c,c ),i):j∈[0,n),(5) (c,i)=P[j],(c ,i+2k)=P[j+1] Function name(S:Sequence of Pair) q:=r:=0;( , ):=($,$) result:= foreach((c,c ),i)∈S do q++ if(c,c )=( , )then r:=q;( , ):=(c,c ) append(r,i)to result return result Figure1:The doubling algorithm. Theorem2.1.The doubling algorithm computes a suf-?x array using O(sort(n) log maxlcp )I/Os. 3Pipelining The I/O volume of the doubling algorithm from Figure1 can be reduced signi?cantly by observing that rather than writing the sequence S to external memory,we can directly feed it to the sorter in Line(1).Similarly, the sorted tuples need not be written but can be directly fed into the naming procedure in Line(2)which can in turn forward it to the sorter in Line(4).The result of this sorting operation need not be written but can directly yield tuples of S that can be fed into the next iteration of the doubling algorithm.Appendix A gives a simpli?ed analysis of this example for pipelining. Let us discuss a more systematic model:The computations in many external memory algorithms can be viewed as a data?ow through a directed acyclic graph G=(V=F∪S∪R,E).The?le nodes F represent data that has to be stored physically on disk. When a?le node f∈F is accessed we need a bu?er of size b(f)=?(BD).The streaming nodes s∈S read zero,one or several sequences and output zero, one or several new sequences using internal bu?ers of size b(s).1The Sorting nodes r∈R read a sequence and output it in sorted order.Sorting nodes have a bu?er requirement of b (r )=Θ(M )and outdegree one 2.Edges are labeled with the number of machine words w (e )?owing between two nodes.In the proof of Theorem 3.2you ?nd the ?ow graph for the pipelined doubling algorithm.We will see a somewhat more complicated graph in Sections 4and 6.The following theorem gives necessary and su?cient conditions for an I/O e?cient execution of such a data ?ow graph.Moreover,it shows that streaming computations can be scheduled completely systematically in an I/O e?cient way. Theorem 3.1.The computations of a data ?ow graph G =(V =F ∪S ∪R,E )with edge ?ows w :E →R +and bu?er requirements b :V →R +can be executed using (3.4) e ∈E ∩(F ×V ∪V ×F ) scan(w (e ))+ e ∈E ∩(V ×R ) sort(w (e )) I/Os i?the following conditions are ful?lled.Consider the graph G which is a copy of G except that edges between streaming nodes are replaced by bidirected edges.The strongly connected components (SCCs)of G are required to be either single ?le nodes,single sorting nodes,or sets of streaming nodes.The total bu?er requirement of each SCC C of streaming nodes plus the bu?er requirements of the nodes directly connected to C has to be bounded by the internal memory size M . Proof.The basic observation is that all streaming nodes within an SCC C of G must be executed together exchanging data through their internal bu?ers —if any node from C is excluded it will eventually stall the computation because input or output bu?er ?ll up. Now assume that G ful?lls the requirements.We schedule the computations for each SCC of G in topo-logically sorted order.First consider an SCC C of streaming nodes.We perform in a single pass all the computations of the streaming nodes in C ,reading from the ?le nodes with edges entering C ,writing to the ?le nodes with edges coming from C ,performing the ?rst phase of sorting (e.g.,run formation)of the sorting nodes with edges coming from C ,and performing the last phase of sorting (e.g.multiway merging)for the sorting nodes with edges entering C .The requirement on the bu?er sizes ensures that there is su?cient inter-nal memory.The topological sorting ensures that all the data from incoming edges is available.Since there are Theorem 3.1can be used to design and analyze pipelined external memory algorithms in a systematic way.All we have to do is to give a data ?ow graph that ful?lls the requirements and we can then read o?the I/O https://www.doczj.com/doc/ea15068687.html,ing the relations a ·scan(x )=scan(a ·x )+ O (1)and a ·sort(x )≤sort(a ·x )+O (1),we can represent the result in the form scan(x )+sort(y )+O (1),i.e.,we can characterize the complexity in terms of the sorting volume x and the scanning volume y .One could further evaluate this function by plugging in the I/O complexity of a particular sorting algorithm (e.g.,≈2x/DB for x M 2/DB and M DB )but this may not be desirable because we lose information.In particular, scanning implies less internal work and can usually be implemented using bulk I/Os in the sense of [8](we then need larger bu?ers b (v )for ?le nodes)whereas sorting requires many random accesses for information theoretic reasons [2]. Now we apply Theorem 3.1to the doubling algo-rithm: Theorem 3.2.The doubling algorithm from Figure 1can be implemented to run using sort(5n ) log(1+maxlcp) +O (scan(n ))I/Os. Proof.The following?ow graph shows that each iter-ation can be implemented using sort(2n)+sort(3n)≤sort(5n)I/Os.The numbers refer to the line numbers in Figure1 streaming node sorting node After log(1+maxlcp) iterations,the algorithm?n-ishes.The O(sort(n))term accounts for the I/Os needed in Line0and for computing the?nal result. Note that there is a small technicality here:Although naming can?nd out“for free”whether all names are unique,the result is known only when naming?nishes. However,at this time,the?rst phase of the sorting step in Line4has also?nished and has already incurred some I/Os.Moreover,the convenient arrangement of the pairs in P is destroyed now.However we can then abort the sorting process,undo the wrong sorting,and compute the correct output. Figure2:Figure4.The edge weights are sums over the whole execution with N=n log dps. c is unique.We will fully discard(c,i)=(c k i,i)when also either c k i?2k or c k i?2k+1 is unique,because then in any iteration h>k,the?rst component of the tuple ((c h i?2h ,c h i),i?2h)must be unique.The?nal algorithm is given in Figure4. Theorem4.1.Doubling with discarding can be imple-mented to run using sort(5n log dps)+O(sort(n))I/Os. Proof.We prove the theorem by showing that the total amount of data in the di?erent steps of the algorithm over the whole execution is as in the data?ow graph in Figure2.The nontrivial points are that at most N=n log dps tuples are processed in each sorting step over the whole execution and that at most n tuples are written to P.The former follows from the fact that a su?x i is involved in the sorting steps as long as it has a non-unique rank,which happens in exactly log(1+dps(i)) iterations.To show the latter,we note that a tuple(c,i)is written to P in iteration k only if the previous tuple(c ,i?2k)was not unique.That previous tuple will become unique in the next iteration, because it is represented by((c ,c),i?2k)in S.Since each tuple turns unique only once,the total number of tuples written to P is at most n. log a n)log maxlcp+O(sort(n))or sort(a+3 log a .Evaluating this expression we get the optimum for a=5.But the value for a=4is only 1.5%worse,needs less memory,and calculations are much easier because four is a power two.Hence,we choose a=4for our implementation of the a-tupling algorithm.This quadrupling algorithm needs30%less I/Os than doubling. 6A Pipelined I/O-Optimal Algorithm The following three step algorithm outlines a linear time algorithm for su?x array construction[17]: 1.Construct the su?x array of the su?xes starting at positions i mod3=0.This is done by reduction to the su?x array construction of a string of two thirds the length,which is solved recursively. 2.Construct the su?x array of the remaining su?xes using the result of the?rst step. 3.Merge the two su?x arrays into one. Figure5gives pseudocode for an external implementa- tion of this algorithm and Figure6gives a data?ow graph that allows pipelined execution.Step1is imple- mented by Lines(1)–(6)and starts out quite similar to the tripling(3-tupling)algorithm described in Section5. The main di?erence is that triples are only obtained for two thirds of the su?xes and that we use recursion to ?nd lexicographic names that exactly characterize the relative order of these sample su?xes.As a preparation for the Steps2and3,in lines(7)–(10)these sample names are used to annotate each su?x position i with enough information to determine its global rank.More precisely,at most two sample names and the?rst one or two characters su?ce to completely determine the rank of a su?x.This information can be obtained I/O ef- ?ciently by simultaneously scanning the input and the names of the sample su?xes sorted by their position in the input.With this information,Step2reduces to sorting su?xes T i with i mod3=0by their?rst char- acter and the name for T i+1in the sample(Line11). Line(12)reconstructs the order of the mod-2su?xes and mod-3su?xes.Line(13)implements Step3by ordinary comparison based merging.The slight com- plication is the comparison function.There are three cases: ?A mod-0su?x T i can be compared with a mod-1 su?x T j by looking at at the?rst characters and the names for T i+1and T j+1in the sample respectively.?For a comparison between a mod-0su?x T i and a mod-2su?x T j the above technique does not work since T j+1is not in the sample.However,both T i+2 and T j+2are in the sample so that it su?ces to look at the?rst two characters and the names of T i+2 and T j+2respectively. ?Mod-1su?xes and Mod-2su?xes can be compared by looking at their names in the sample. The resulting data?ow graph is large but fairly straight-forward except for the?le node which stores a copy of input stream T.The problem is that the input is needed twice.First,Line2uses it for generating the sample and later,the node implementing Lines(8)–(10)scans it si-multaneously with the names of the sample su?xes.It is not possible to pipeline both scans because we would violate the requirement of Theorem3.1that edges be-tween streaming nodes must not cross sorting nodes. This problem can be solved by writing a temporary copy of the input stream.Note that this is still cheaper than using a?le representation for the input since this would mean that this?le is read twice.We are now ready to analyze the I/O complexity of the algorithm. Theorem6.1.The doubling algorithm from Figure5 can be implemented to run using sort(30n)+scan(6n) I/Os. Proof.Let V(n)denote the number of I/Os for the external https://www.doczj.com/doc/ea15068687.html,ing Theorem3.1and the data?ow diagram from Figure6we can conclude that V(n)≤sort((8 3+4 3 +3 3 )n) +scan(2n)+V( 2 3 n) This recurrence has the solution V(n)≤3(sort(10n)+ scan(2n))≤sort(30n)+scan(6n).Note that the data ?ow diagram assumes that the input is a data stream into the procedure call.However,we get the same complexity if the original input is a?le.In that case, we have to read the input once but we save writing it to the local?le node T. file node streaming node recursion sorting node Figure 6:Data ?ow graphs for the DC3-algorithm.The numbers refer to line numbers in Figure 5. Table 1:Statistics of the instances used in the experiments. T lcp log dps 232 128 231 ≈229 ≈29.56 Gutenberg 3070128194 5 21999999 454111 6.53HTML 547505710 128 173317 431 5.80 l o g a r i t h m i c l c p n Source:Source code (mostly C++)containing core-utils,gcc,gimp,kde,xfree,emacs,gdb,Linux kernel and Open O?ce). We have collected some of these instances at ftp://www.mpi-sb.mpg.de/pub/outgoing/sanders/.For a nonsynthetic instance T of length n ,our experiments use T itself and its pre?xes of the form T [0,2i ).Table 1shows statistics of the properties of these instances. The ?gure on the next page shows execution time and I/O volume side by side for each of our instance families and for the algorithms nonpipelined doubling,pipelined doubling,pipelined doubling with discarding,pipelined quadrupling,pipelined quadrupling with dis-carding 4,and DC3.All ten plots share the same x -axis and the same curve https://www.doczj.com/doc/ea15068687.html,puting all these in-stances takes about 14days moving more than 20TByte of data.Due to these large execution times it was not feasible to run all algorithms for all input sizes and all instances.However,there is enough data to draw some interesting conclusions. Complicated behavior is observed for “small”inputs up to 226characters.The main reason is that we made no particular e?ort to optimize special cases R a n d o m 2: T i m e [μs ] / n I /O V o l u m e [b y t e ] / n G u t e n b e r g : T i m e [μs ] / n I /O V o l u m e [b y t e ] / n G e n o m e : T i m e [μs ] / n I /O V o l u m e [b y t e ] / n H T M L : T i m e [μs ] / n I /O V o l u m e [b y t e ] / n S o u r c e : T i m e [μs ] / n n I /O V o l u m e [b y t e ] / n n one can see that pipelining brings a huge reduction of I/O volume whereas the execution time is a?ected much less—a clear indication that our algorithms are dom-inated by internal calculations.We also have reasons to believe that our nonpipelined sorter is more highly tuned than the pipelined one so that the advantage of pipelining may grow in future versions of our imple-mentation.We do not show the nonpipelined algorithm for the other inputs since the relative performance com-pared to pipelined doubling should remain about the same. A comparison of the new algorithms with previous algorithms is more di?cult.The implementation of [8]works only up to2GByte of total external memory consumption and would thus have to compete with space e?cient internal algorithms on our machine.At least we can compare I/O volume per byte of input for the measurements in[8].Their most scalable algorithm for the largest real world input tested(26MByte of text from the Reuters news agency)is nonpipelined doubling with partial discarding.This algorithm needs an I/O volume of1303Bytes per character of input.The DC3-algorithm needs about5times less I/Os.Furthermore, it is to be expected that the lead gets bigger for larger inputs.The GBS algorithm[13]needs486bytes of I/O per character for this input in[8],i.e.,even for this small input DC3already outperforms the GBS algorithm.We can also attempt a speed comparison in terms of clock cycles per byte of input.Here[8] needs157000cycles per byte for doubling with simple discarding and147000cycles per byte for the GBS algorithm whereas DC3needs only about20000cycles. Again,the advantage should grow for larger inputs in particular when comparing with the GBS algorithm. The following small table shows the execution time of DC3for1to8disks on the‘Source’instance. D t[μs/byte]Theorem8.1.The su?x array checker from Figure7 can be implemented to run using sort(5n)+scan(2n) I/Os. Function Checker(SA,T) P:=[(SA[i],i+1):i∈[0,n)](1) sort P by the?rst component(2) if[i:(i,r)∈S]=[0,n)then return false S:=[(r,(T[i],r )):i∈[0,n),(3) (i,r)=P[i],(i+1,r )=P[i+1]] sort S by?rst component(4) if[(c,r ):(r,(c,r ))∈S]is sorted(5) then return true else return false Figure7:The su?x array checker. 9Conclusion Our e?cient external version of the DC3-algorithm is theoretically optimal and clearly outperforms all pre-vious algorithms in practice.Since all practical previ-ous algorithms are asymptotically suboptimal and de-pendent on the inputs,this closes a gap between the-ory and practice.DC3even outperforms the pipelined quadrupling-with-discarding algorithm even for real world instances.This underlines the practical usefulness of DC3since a mere comparison with the relatively sim-ple,nonpipelined previous implementations would have been unfair. As a side e?ect,the various generalizations of dou-bling yield an interesting case study for the systematic design of pipelined external algorithms. The most important practical question is whether constructing su?x arrays in external memory is now feasible.We believe that the answer is a careful ‘yes’.We can now process4·109characters overnight on a low cost machine.Two orders of magnitude more than in[8]in a time faster or comparable to previous internal memory computations[23,20]on more expensive machines. There are also many opportunities to scale to even larger inputs.For example,one could exploit that about half of the sorting operations are just permutations which should be implementable with less internal work than general sorting.It should also be possible to better overlap I/O and computation.More interestingly, there are many ways to parallelize.On a small scale, pipelining allows us to run several sorters and one streaming thread in parallel.On a large scale DC3is also perfectly parallelizable[17].Since the algorithm is largely compute bound,even cheap switched Gigabit-Ethernet should allow high e?ciency(DC3sorts about 13MByte/s in our measurements).Considering all these improvements and the continuing advance in technology,there is no reason why it should not be possible to handle inputs that are another two orders of magnitude larger in a few years. Acknowledgements.We would like to thank Stefan Burkhardt and Knut Reinert for valuable pointers to interesting experimental input.Lutz Kettner helped with the design of Stxxl.The html pages were supplied by Sergey Sizov from the information retrieval group at MPII.Christian Klein helped with Unix tricks for assembling the data. References [1]M.I.Abouelhoda,S.Kurtz,and E.Ohlebusch.The enhanced su?x array and its applications to genome analysis.In Proc.2nd Workshop on Algorithms in Bioinformatics,volume2452of LNCS,pages449–463. Springer,2002. [2] A.Aggarwal and J.S.Vitter.The input/output com- plexity of sorting and related https://www.doczj.com/doc/ea15068687.html,munica-tions of the ACM,31(9):1116–1127,1988. [3]L.Arge,P.Ferragina,R.Grossi,and J.S.Vitter. On sorting strings in external memory.In29th ACM Symposium on Theory of Computing,pages540–548, El Paso,May1997.ACM Press. [4]L.Arge,O.Procopiuc,and J.S.Vitter.Implementing I/O-e?cient data structures using TPIE.In10th European Symposium on Algorithms(ESA),volume 2461of LNCS,pages88–100.Springer,2002. [5]S.Burkhardt and J.K¨a rkk¨a inen.Fast lightweight suf- ?x array construction and checking.In Proc.14th An-nual Symposium on Combinatorial Pattern Matching, volume2676of LNCS,pages55–69.Springer,2003. [6]M.Burrows and D.J.Wheeler.A block-sorting lossless data compression algorithm.Technical Report124, SRC(digital,Palo Alto),May1994. [7]C-F.Cheung,J.X.Yu,and H.Lu.Constructing su?x trees for gigabyte sequences with megabyte memory. IEEE Transactions on Knowledge and Data Engineer-ing,17(1):90–105,2005. [8] A.Crauser and P.Ferragina.Theoretical and exper- imental study on the construction of su?x arrays in external memory.Algorithmica,32(1):1–35,2002. [9] A.Crauser and K.Mehlhorn.LEDA-SM a platform for secondary memory computations.Technical report, MPII,1998.draft. [10]R.Dementiev.The stxxl library.documentation and download at http://www.mpi-sb.mpg.de/~rdementi/ stxxl.html. [11]R.Dementiev and P.Sanders.Asynchronous parallel disk sorting.In15th ACM Symposium on Parallelism in Algorithms and Architectures,pages138–148,San Diego,2003. [12]M.Farach-Colton,P.Ferragina,and S.Muthukrish- nan.On the sorting-complexity of su?x tree construc-tion.Journal of the ACM,47(6):987–1011,2000. [13]G.Gonnet,R.Baeza-Yates,and T.Snider.New indices for text:PAT trees and PAT arrays.In W.B.Frakes and R.Baeza-Yates,editors,Information Retrieval:Data Structures&Algorithms.Prentice-Hall,1992. [14]W.-K.Hon,https://www.doczj.com/doc/ea15068687.html,m,K.Sadakane,and W.-K. Sung.Constructing compressed su?x arrays with large alphabets.In Proc.14th International Symposium on Algorithms and Computation,volume2906of LNCS, pages240–249.Springer,2003. [15]W.-K.Hon,K.Sadakane,and W.-K.Sung.Breaking a time-and-space barrier in constructing full-text indices. In Proc.44th Annual Symposium on Foundations of Computer Science,pages251–260.IEEE,2003. [16]J.K¨a rkk¨a inen.Algorithms for Memory Hierarchies, volume2625of LNCS,chapter Full-Text Indexes in External Memory,pages171–192.Springer,2003. [17]J.K¨a rkk¨a inen and P.Sanders.Simple linear work su?x array construction.In Proc.30th International Conference on Automata,Languages and Program-ming,volume2719of LNCS,pages943–955.Springer, 2003. [18] D.K.Kim,J.S.Sim,H.Park,and K.Park.Linear- time construction of su?x arrays.In Proc.14th An-nual Symposium on Combinatorial Pattern Matching, volume2676of LNCS,pages186–199.Springer,June 2003. [19]P.Ko and S.Aluru.Space e?cient linear time con- struction of su?x arrays.In Proc.14th Annual Sympo-sium on Combinatorial Pattern Matching,volume2089 of LNCS,pages200–210.Springer,2003. [20]https://www.doczj.com/doc/ea15068687.html,m,K.Sadakane,W.-K.Sung,and Siu-Ming Yiu.A space and time e?cient algorithm for construct-ing compressed su?x arrays.In Proc.8th Annual In-ternational Conference on Computing and Combina-torics,volume2387of LNCS,pages401–410.Springer, 2002. [21]U.Manber and G.Myers.Su?x arrays:A new method for on-line string searches.SIAM Journal on Computing,22(5):935–948,October1993. [22]G.Manzini and P.Ferragina.Engineering a lightweight su?x array construction algorithm.In Proc.10th Annual European Symposium on Algorithms,volume 2461of LNCS,pages698–710.Springer,2002. [23]K.Sadakane and T.Shibuya.Indexing huge genome sequences for solving various problems.Genome In-formatics,12:175–183,2001. [24] A.Silberschatz,H. F.Korth,and S.Sudarshan. Database System Concepts.McGraw-Hill,4th edition, 2001. [25]J.S.Vitter and E.A.M.Shriver.Algorithms for parallel memory,I:Two level memories.Algorithmica, 12(2/3):110–147,1994. A An Introductory Example For Pipelining To motivate the idea of pipelining let us?rst analyze the constant factor in a naive implementation of the doubling algorithm from Figure 1.For simplicity assume for now that inputs are not too large so that sorting m words can be done in4m/D B I/Os using two passes over the data.For example,one run formation phase could build sorted runs of size M and one multiway merging phase could merge the runs into a single sorted sequence. Line(1)sorts n triples and hence needs12n/DB I/Os.Naming in Line(2)scans the triples and writes name-index pairs using3n/DB+2n/DB=5n/DB I/Os.The naming procedure can also determine whether all names are unique now,hence the test in Line(3)needs no I/Os.Sorting the pairs in P in Line(4) costs8n/DB I/Os.Scanning the pairs and producing triples in Line(5)costs another5n/DB I/Os.Overall, we get(12+5+8+5)n/DB=30n/DB I/Os for each iteration. This can be radically reduced by interpreting the sequences S and P not as?les but as pipelines similar to the pipes available in UNIX.In the beginning we explicitly scan the input T and produce triples for S. We do not count these I/Os since they are not needed for the subsequent iterations.The triples are not output directly but immediately fed into the run formation phase of the sorting operation in Line(1).The runs are output to disk(3n/DB I/Os).The multiway merging phase reads the runs(3n/DB I/Os)and directly feeds the sorted triples into the naming procedure called in Line(2)which generates pairs that are immediately fed into the run formation process of the next sorting operation in Line(3)(2n/DB I/Os).The multiway merging phase(2n/DB I/Os)for Line(3)does not write the sorted pairs but in Line(4)it generates triples for S that are fed into the pipeline for the next iteration. We have eliminated all the I/Os for scanning and half of the I/Os for sorting resulting in only10n/DB I/Os per iteration—only one third of the I/Os needed for the naive implementation. Note that pipelining would have been more compli-cated in the more traditional formulation where Line(3) sorts P directly by the index i.In that case,a pipelining formulation would require a FIFO of size2k to produce a shifted sequences.When2k>M this FIFO would have to be maintained externally causing2n/DB addi-tional I/Os per iteration,i.e.,our modi?cation simpli?es the algorithm and saves up to20%I/Os. 第一章 1.(Q1) What is the difference between a host and an end system List the types of end systems. Is a Web server an end system Answer: There is no difference. Throughout this text, the words “host” and “end system” are used interchangeably. End systems inc lude PCs, workstations, Web servers, mail servers, Internet-connected PDAs, WebTVs, etc. 2.(Q2) The word protocol is often used to describe diplomatic relations. Give an example of a diplomatic protocol. Answer: Suppose Alice, an ambassador of country A wants to invite Bob, an ambassador of country B, over for dinner. Alice doesn’t simply just call Bob on the phone and say, come to our dinner table now”. Instead, she calls Bob and suggests a date and time. Bob may respond by saying he’s not available that particular date, but he is available another date. Alice and Bob continue to send “messages” back and forth until they agree on a date and time. Bob then shows up at the embassy on the agreed date, hopefully not more than 15 minutes before or after the agreed time. Diplomatic protocols also allow for either Alice or Bob to politely cancel the engagement if they have reasonable excuses. 3.(Q3) What is a client program What is a server program Does a server program request and receive services from a client program Answer: A networking program usually has two programs, each running on a different host, communicating with each other. The program that initiates the communication is the client. Typically, the client program requests and receives services from the server program. 第一章半导体器件基础 1．试求图所示电路的输出电压Uo，忽略二极管的正向压降和正向电阻。 解： （a）图分析： 1）若D1导通，忽略D1的正向压降和正向电阻，得等效电路如图所示，则U O=1V，U D2=1-4=-3V。即D1导通，D2截止。 2）若D2导通，忽略D2的正向压降和正向电阻，得等效电路如图所示，则U O=4V，在这种情况下，D1两端电压为U D1=4-1=3V，远超过二极管的导通电压，D1将因电流过大而烧毁，所以正常情况下，不因出现这种情况。 综上分析，正确的答案是U O= 1V。 （b）图分析： 1.由于输出端开路，所以D1、D2均受反向电压而截止，等效电路如图所示，所以U O=U I=10V。 2．图所示电路中， E 解： （a）图 当u I＜E时，D截止，u O=E=5V； 当u I≥E时，D导通，u O=u I u O波形如图所示。 u I ωt 5V 10V uo ωt 5V 10V （b）图 当u I＜-E=-5V时,D1导通D2截止，uo=E=5V； 当-E＜u I＜E时，D1导通D2截止，uo=E=5V； 当u I≥E=5V时，uo=u I 所以输出电压u o的波形与（a）图波形相同。 5．在图所示电路中，试求下列几种情况下输出端F的电位UF及各元件(R、DA、DB)中通过的电流：( 1 )UA=UB=0V；( 2 )UA= +3V，UB = 0 V。( 3 ) UA= UB = +3V。二极管的正向压降可忽略不计。 解：（1）U A=U B=0V时，D A、D B都导通，在忽略二极管正向管压降的情况下，有：U F=0V mA k R U I F R 08 .3 9.3 12 12 = = - = 第2章习题答案 2-9. (1)x<=3 运行顺序为Px，P3，P5，P6，P9 T=(x+(x+3)+(x+3+5)+(x+3+5+6)+(x+3+5+6+9))/5=x+ (2)3 作业4还未到，只能选作业3运行。 作业3运行到结束，再计算剩余的作业2和4： 作业2的响应比=（（）+）/= 作业4的响应比=( /=2 选作业2运行。 作业2到完成。最后运行作业4。运行到,全部结束。 各个作业的周转时间计算如下： t1=2 t2== t3= t4== 各个作业的平均周转时间计算如下： T==(2++1+/4= 各个作业的平均带权周转时间计算如下： W=(2/2++1/+/4= 2-13．已知作业A,B,C,D,E需要的运行时间分别为10,6,2,4,8分钟，优先级分别为3,5,2,1,4。 （1）轮转法（假定时间片=2分钟） 作业完成的顺序为C,D,B,E,A 开始作业轮转一周需10分钟， 作业C的周转时间：Tc=10分钟（6分） C完成后，剩下四个作业，轮转一周需8分钟, 作业D的周转时间：Td=10+8×(4-2)/2=18分钟（16分） D完成后，剩下三个作业，轮转一周需6分钟, 作业B的周转时间：Tb=18+6×(6-2-2)/2=24分钟（22分） B完成后，剩下两个作业，轮转一周需4分钟, 作业E的周转时间：Te=24+4=28分钟（28分） E完成后，只剩下作业A, 作业A的周转时间：Ta=28+2=30分钟（30分） 平均周转时间：T=(10+18+24+28+30)/5=22分（分） （2）优先级调度法 作业完成顺序为：B,E,A,C,D Tb=6分，Te=6+8=14分，Ta=14+10=24分，Tc=24+2=26分， Td=26+4=30分。 平均周转时间：T=(6+14+24+26+30)/5=20分 第3章习题答案 3-7. 系统中有n+1个进程。其中A1、A2、…、An分别通过缓冲区向进程B发送消息。相互之间的制约关系为：发送进程A1、A2、…、An要互 第1章 1、在VMwane中安装CentOS 7的基本步骤有哪些？ （1）新建虚拟机 （2）虚拟机设置 （3）启动虚拟机 （4）设置安装信息，包括软件选择，安装位置，分区等 （5）完成最后安装 2、安装Linux时可以设置哪些分区？有哪些分区是必须的？ 能够设置的分区可以根据安装系统时提示，主要包括：/，/boot，swap，/home，/opt 等等；其中/（根）分区是必须的。 第2章 1、针对Linux 系统启动运行，有哪些运行目标？每个运行目标的含义是什么？ CentOS 从7.0 开始使用systemd 代替init 作为系统启动和服务器守护进程的管理器，负责在系统启动或运行时，激活系统资源，管理服务器进程。systemd 用目标（target）替代了运行级别的概念，提供了更大的灵活性，比如可以继承一个已有的目标，并添加其他服务来创建自己的目标。CentOS 7.0 之前的运行级别和systemd 目标之间的对应关系如下表所示。 2、Linux 有几种关机方法，每种关机操作有何异同？ 关闭系统的命令有： shutdown（最安全的方式），halt，init，telinit，poweroff，reboot，具体含义可以参考 帮助手册页。 第3章 more、less、cat、wc 命令有什么区别？ 这几个命令可用于对文本文件的处理显示，主要区别在：more命令以分页（一次一屏）显示文本信息；less类似于more，但增加了回滚功能；cat本意是连接文件并在标准输出上输出，也就是将文件一次全部输出；wc用于统计输出文件中的行数、单词数、字节数等。 第4章 （1）发出命令显示行号。 底端命令方式下 :set nu （2）保存到文件AboutLinux，并不退出。 底端命令方式下 :w AboutLinux （3）删除一句“It is this kernel that forms the base around which a Linux operating system is developed.”。 在命令方式下，先把光标移到It处，再按d$。（从当前光标处到行末的所有字符删除）（4）查找单词“Finland”。 命令方式下输入/Finland，回车后会在第一个Finland处停下来。 （5）把第一段的“Finland”单词后的内容换行，使其变成三段内容。 插入方式下，将光标移到Finland后，按回车键即可。（vi的换行标志是回车符） （6）将第二段的内容复制到文档的最后。 命令方式下：先用yy命令，然后移到文档最后，再按p键。 （7）删除第三段的内容。 命令方式下，光标移到第三段，用dd命令。（注，这里的段实际上是第3行。） （8）恢复被删除的一段内容。 命令方式下，用u命令。 （9）查找所有的“Minix”单词，并全部改为“MINIX”。 底端命令方式下，:1,$s/Minix/MINIX/g （10）不保存修改，退出vi。 底端命令方式下，：q! （11）使用vi再次打开文件AboutLinux，在第二段后插入“He began his work in 1991 when he released version 0.02 and worked steadily until 1994 when version 1.0 of the Linux Kernel was released.”。 shell命令提示符下输入：vi AboutLinux（打开保存的文件） 上海电力学院 计算机操作系统原理 实验报告 题目：动态链接库的建立与调用 院系：计算机科学与技术学院 专业年级：信息安全2010级 学生姓名：李鑫学号：20103277 同组姓名：无 2012年11 月28 日上海电力学院 实验报告 课程名称计算机操作系统原理实验项目线程的同步 姓名李鑫学号20103277 班级2010251班专业信息安全 同组人姓名无指导教师姓名徐曼实验日期2012/11/28 实验目的和要求： (l)了解Windows内存管理机制，理解页式存储管理技术。 (2)熟悉Windows内存管理基本数据结构。 (3)掌握Windows内存管理基本API的使用。 实验原理与内容 使用Windows系统提供的函数和数据结构显示系统存储空间的使用情况，当内存和虚拟存储空间变化时，观察系统显示变化情况。 实验平台与要求 能正确使用系统函数GlobalMemoryStatus()和数据结构MEMORYSTATUS了解系统内存和虚拟空间使用情况，会使用VirtualAlloc()函数和VirtualFree()函数分配和释放虚拟存储空间。 操作系统：Windows 2000或Windows XP 实验平台：Visual Studio C++ 6.0 实验步骤与记录 1、启动安装好的Visual C++ 6.0。 2、选择File->New，新建Win32 Console Application程序, 由于内存分配、释放及系统存储 空间使用情况均是Microsoft Windows操作系统的系统调用，因此选择An application that support MFC。单击确定按钮，完成本次创建。 3、创建一个支持MFC的工程，单击完成。 操作系统原理及应用试题附答案 第一部分选择题一、单项选择题（本大题共4小题，每小题2分，共8分） 1、从静态角度来看，进程由__________、数据集合、进程控制块及相关表格三部分组成。（）A、JCB B、PCB C、程序段 D、I/O缓冲区 2、请求页式管理方式中，首先淘汰在内存中驻留时间最长的帧，这种替换策略是_____.（）A、先进先出法（FIFO） B、最近最少使用法（LRU） C、优先级调度 D、轮转法 3、文件安全管理中，___________安全管理规定用户对目录或文件的访问权限。（）A、系统级 B、用户级 C、目录级 D、文件级 4、排队等待时间最长的作业被优先调度，这种算法是___________。A、优先级调度 B、响应比高优先 C、短作业优先D、先来先服务第二部分非选择题 二、填空题（本大题共16小题，每小题1分，共16分） 5、常规操作系统的主要功能有：_处理机管理_、存贮管理、设备管理、文件管理以及用户界面管理。 6、操作系统把硬件全部隐藏起来，提供友好的、易于操作的用户界面，好象是一个扩展了的机器，即一台操作系统虚拟机。 7、进程管理的功能之一是对系统中多个进程的状态转换进行控制。 8、逻辑_文件是一种呈现在用户面前的文件结构。 9、操作系统中实现进程互斥和同步的机制称为同步机构_。 10、内存中用于存放用户的程序和数据的部分称为用户区（域）。 11、存贮器段页式管理中，地址结构由段号、段内页号和页内相对地址三部分组成。 12、在操作系统中，通常用户不使用设备的物理名称（或物理地址），而代之以另外一种名称来操作，这就是逻辑设备名。 13、在操作系统中，时钟常有两种用途：报告日历和时间，对资源使用记时。 14、库文件允许用户对其进行读取、执行，但不允许修改. 《操作系统原理》期末考试题 班级学号姓名 一、单项选择题（每题2分，共26分） 1.操作系统是一种()。 A. 系统软件 B. 系统硬件 C. 应用软件 D. 支援软件 2.分布式操作系统与网络操作系统本质上的不同在于（）。 A.实现各台计算机这间的通信 B.共享网络中的资源 C.满足较在规模的应用 D.系统中多台计算机协作完成同一任务 3.下面对进程的描述中，错误的是（）。 A.进程是动态的概念 B. 进程执行需要处理机 C.进程是指令的集合 D. 进程是有生命期的 4.临界区是指并发进程中访问共享变量的（）段。 A.管理信息 B.信息存储 C.数据 D.程序 5.要求进程一次性申请所需的全部资源，是破坏了死锁必要条件中的哪一条（）。 A.互斥 B.请求与保持 C.不剥夺 D.循环等待 6.以下哪种存储管理不可用于多道程序系统中（）。 A.单一连续区存储管理 B.固定式区存储管理 D. 段式存储管理 C.可变分区存储管理7.在可变式分区存储管理 中，某作业完成后要收回其主存空间，该空间可能与 1 / 8 相邻空闲区合并，修改空闲区表，使空闲区数不变且空闲区起始地址不变的 情况是（）。 A.无上邻空闲区也无下邻空闲区 B.有上邻空闲区但无下邻空闲区 C.有下邻空闲区但无上邻空闲区 D.有上邻空闲区也有下邻空闲 区 8.系统“抖动”现象的发生不是由（）引起的。 A.置换算法选择不当 B.交换的信息量过大 C.主存容量不足 D.请求页式管理方案 9.在进程获得所需全部资源，唯却CPU时，进程处于（）状态。 A.运行 B.阻塞 C.就绪 D.新建 10.要页式存储管理系统中，将主存等分成（）。 A.块 B.页 C.段长 D.段 11.系统利用SPOOLING技术实现（）。 A.对换手段 B.虚拟设备 C.系统调用 D.虚拟存储 12.设备从磁盘驱动器中读出一块数据的总时间为（）。 A.等待时间+ 传输时间 B.传输时间 D.延迟时间+ 查找时间+ 传输时间 C.查找时间+ 传输时间 13.如果允许不同用户的文件可以具有相同的文件名，通常采用（） 操作系统原理课程设计 实践报告 题目: 仿真多进程并发环境中死锁的预防、避免、检测与解除 姓名: 学院: 信息科技学院 专业: 计算机科学技术系 班级: 学号: 指导教师: 职称: 20010年4月8日 仿真多进程并发环境中死锁的预防、避免、检测与解除 摘要：在多道程序系统中，多个程序并发执行时可能造成死锁。所谓死锁是指多 个进程在运行过程中因争夺资源而造成的一种僵局。当进程处于这种僵局状态时若无外力作用，它们都将无法再向前推进，造成资源的浪费。该程序将模拟多进程并发时死锁现象的产生、避免、检测与解除。死锁避免用最著名的银行家算法，用银行家安全性算法类似的死锁检测算法来检测进程状况，又用资源剥夺法来实现死锁的解除。该程序实现操作简易，表示清晰并且形象描述多进程并发环境中死锁的预防、避免、检测与解除。 关键字：死锁；避免死锁；安全状态；银行家算法 引言：在操作系统、数据库系统以及网络通信中,由于进程并发和资源共享,当系统中资源分配顺序或者进程推进顺序不当就会造成系统死锁[1]。处于死锁状态的系统中，进程之间互相等待资源而永远不能继续向前推进，严重地影响了系统的可靠性。因而有时需要合理的对资源进行分配必要的时候加以限制保证系统安全、高效、稳定的运行。 1理论分析 1.1 死锁的概念 如果一个进程集合中的每个进程都在等待只能由此集合中的其他进程才能引发的事件，而无限期陷入僵持的局面称为死锁[2]。 1.2 产生死锁的条件： 1、互斥使用（资源独占）：一个资源每次只能给一个进程使用。 2、不可强占（不可剥夺）：资源申请者不能强行的从资源占有者手中夺取资 源，资源只能由占有者自愿释放。 3、请求和保持（部分分配，占有申请）：一个进程在申请新的资源的同时保 持对原有资源的占有（只有这样才是动态申请，动态分配）。 4、循环等待：存在一个进程等待队列{P1，P2，…，Pn}，其中P1等待P2占 有的资源，P2等待P3占有的资源，…，Pn等待P1占有的资源，形成一个进程等待环路[3]。 1.3死锁的预防 在系统设计时确定资源分配算法，保证不发生死锁。具体的做法是破坏产生死锁的四个必要条件之一。 ①破坏“不可剥夺”条件 在允许进程动态申请资源前提下规定，一个进程在申请新的资源不能立即得到满足而变为等待状态之前，必须释放已占有的全部资源，若需要再重新申请。 ②破坏“请求和保持”条件 要求每个进程在运行前必须一次性申请它所要求的所有资源，且仅当该进程所要资源均可满足时才给予一次性分配。 ③破坏“循环等待”条件 采用资源有序分配法：把系统中所有资源编号，进程在申请资源时必须严格按资源编号的递增次序进行，否则操作系统不予分配。 第1章 习题答案 1－1 题1－1图所示信号中，哪些是连续信号？哪些是离散信号？哪些是周期信号？哪些是非周期信号？哪些是有始信号？ 解： ① 连续信号：图（a ）、（c ）、（d ）； ② 离散信号：图（b ）； ③ 周期信号：图（d ）； ④ 非周期信号：图（a ）、（b ）、（c ）； ⑤有始信号：图（a ）、（b ）、（c ）。 1－2 已知某系统的输入f(t)与输出y(t)的关系为y(t)=|f(t)|，试判定该系统是否为线性时不变系统。 解： 设T 为此系统的运算子，由已知条件可知： y(t)=T[f(t)]=|f(t)|，以下分别判定此系统的线性和时不变性。 ① 线性 1）可加性 不失一般性，设f(t)=f 1(t)+f 2(t)，则 y 1(t)=T[f 1(t)]=|f 1(t)|，y 2(t)=T[f 2(t)]=|f 2(t)|，y(t)=T[f(t)]=T[f 1(t)+f 2(t)]=|f 1(t)+f 2(t)|，而 |f 1(t)|＋|f 2(t)|≠|f 1(t)+f 2(t)| 即在f 1(t)→y 1(t)、f 2(t)→y 2(t)前提下，不存在f 1(t)＋f 2(t)→y 1(t)＋y 2(t)，因此系统不具备可加性。 由此，即足以判定此系统为一非线性系统，而不需在判定系统是否具备齐次性特性。 2）齐次性 由已知条件，y(t)=T[f(t)]=|f(t)|，则T[af(t)]=|af(t)|≠a|f(t)|=ay(t) （其中a 为任一常数） 即在f(t)→y(t)前提下，不存在af(t)→ay(t),此系统不具备齐次性，由此亦可判定此系统为一非线性系统。 ② 时不变特性 由已知条件y(t)=T[f(t)]=|f(t)|，则y(t-t 0)=T[f(t-t 0)]=|f(t-t 0)|， 即由f(t)→y(t)，可推出f(t-t 0)→y(t-t 0)，因此，此系统具备时不变特性。 依据上述①、②两点，可判定此系统为一非线性时不变系统。 1－3 判定下列方程所表示系统的性质： )()()]([)()(3)(2)(2)()()2()()(3)(2)()()()()() (2''''''''0t f t y t y d t f t y t ty t y c t f t f t y t y t y b dx x f dt t df t y a t =+=++-+=+++=? 解：（a ）① 线性 1）可加性 由 ?+=t dx x f dt t df t y 0)()()(可得?????→+=→+=??t t t y t f dx x f dt t df t y t y t f dx x f dt t df t y 01122011111)()()()()()()()()()(即即 则 ???+++=+++=+t t t dx x f x f t f t f dt d dx x f dt t df dx x f dt t df t y t y 0212102201121)]()([)]()([)()()()()()( 即在)()()()()()()()(21212211t y t y t f t f t y t f t y t f ＋＋前提下，有、→→→，因此系统具备可加性。 2）齐次性 由)()(t y t f →即?+=t dx x f dt t df t y 0)()()(，设a 为任一常数，可得 )(])()([)()()]([)]([000t ay dx x f dt t df a dx x f a dt t df a dx x af t af dt d t t t =+=+=+??? 即)()(t ay t af →，因此，此系统亦具备齐次性。 由上述1）、2）两点，可判定此系统为一线性系统。 第2章文件管理习题解答 1．什么是文件和文件系统？文件系统有哪些功能？ 【解答】文件是具有符号名而且在逻辑上具有完整意义的信息项的有序序列。 文件系统是指操作系统系统中实现对文件的组织、管理和存取的一组系统程序，它实现对文件的共享和保护，方便用户“按名存取”。 文件系统的功能“ （1）文件及目录的管理。如打开、关闭、读、写等。 （2）提供有关文件自身的服务。如文件共享机制、文件的安全性等。 （3）文件存储空间的管理。如分配和释放。主要针对可改写的外存如磁盘。（4）提供用户接口。为方便用户使用文件系统所提供的服务，称为接口。文件系统通常向用户提供两种类型的接口：命令接口和程序接口。不同的操作系统提供不同类型的接口，不同的应用程序往往使用不同的接口。 2．Linux文件可以根据什么分类？可以分为哪几类？各有什么特点？ 【解答】在Linux操作系统中，文件可以根据内部结构和处理方式进行分类。 在Linux操作系统中，可以将文件分为普通文件、目录文件、特别文件三类。 各类文件的特点是： 普通文件：由表示程序、数据或正文的字符串构成的文件，内部没有固定的结构。这种文件既可以是系统文件，也可以是库文件或用户文件。 目录文件：由文件目录构成的一类文件。对它的处理(读、写、执行)在形式上与普通文件相同。 特别文件：特指各种外部设备，为了便于管理，把所有的输入/输出设备都按文件格式供用户使用。这类文件对于查找目录、存取权限验证等的处理与普通文件相似，而其他部分的处理要针对设备特性要求做相应的特殊处理。 应该指出，按不同的分类方式就有不同的文件系统。 3．什么是文件的逻辑结构？什么是文件的物理结构？Linux文件系统分别采用什么样的结构？有什么优点和缺点? 【解答】文件的逻辑结构：用户对文件的观察的使用是从自身处理文件中数据时采用的组织方式来看待文件组织形式。这种从用户观点出发所见到的文件组织方式称为文件的逻辑组织。 文件的物理结构：从系统的角度考察文件在实际存储设备上的存放形式，又称为文件的存储结构。 在Linux系统中，所有文件的逻辑结构都被看作是流式文件，系统不对文件进行格式处理。 在Linux系统中，文件的物理结构采用的是混合多重索引结构，即将文件所占用盘块的盘块号，直接或间接地存放在该文件索引结点的地址项中。 在Linux系统中，采用混合索引结构的优点是，对于小文件，访问速度快；对于大中 实验4 进程控制 1、实验目的 （1）通过对WindowsXP进行编程，来熟悉和了解系统。 （2）通过分析程序，来了解进程的创建、终止。 2、实验工具 （1）一台WindowsXP操作系统的计算机。 （2）计算机装有Microsoft Visual Studio C++6.0专业版或企业版。 3、预备知识 （3）·CreateProcess（）调用：创建一个进程。 （4）·ExitProcess（）调用：终止一个进程。 4、实验编程 （1）编程一利用CreateProcess()函数创建一个子进程并且装入画图程序(mspaint.exe)。阅读该程序,完成实验任务。源程序如下： # include < stdio.h > # include < windows.h > int main(VOID) ﹛STARTUPINFO si; PROCESS INFORMA TION pi; ZeroMemory(&si,sizeof(si)); Si.cb=sizeof(si); ZeroMemory(&pi,sizeof(pi)); if(!CreateProcess(NULL, “c: \ WINDOWS\system32\ mspaint.exe”, NULL, NULL, FALSE, 0, NULL, NULL, &si,&pi)) ﹛fprintf(stderr,”Creat Process Failed”); return—1; ﹜ WaitForSingleObject(pi.hProcess,INFINITE); Printf(“child Complete”); CloseHandle(pi.hProcess); CloseHandle(pi hThread); ﹜ 第一章思考题及参考答案 １. 无多余约束几何不变体系简单组成规则间有何关系？ 答：最基本的三角形规则，其间关系可用下图说明： 图a 为三刚片三铰不共线情况。图b 为III 刚片改成链杆，两刚片一铰一杆不共线情况。图c 为I 、II 刚片间的铰改成两链杆（虚铰），两刚片三杆不全部平行、不交于一点的情况。图d 为三个实铰均改成两链杆（虚铰），变成三刚片每两刚片间用一虚铰相连、三虚铰不共线的情况。图e 为将I 、III 看成二元体，减二元体所成的情况。 2．实铰与虚铰有何差别？ 答：从瞬间转动效应来说，实铰和虚铰是一样的。但是实铰的转动中心是不变的，而虚铰转动中心为瞬间的链杆交点，产生转动后瞬时转动中心是要变化的，也即“铰”的位置实铰不变，虚铰要发生变化。 3．试举例说明瞬变体系不能作为结构的原因。接近瞬变的体系是否可作为结构？ 答：如图所示AC 、CB 与大地三刚片由A 、B 、C 三铰彼此相连，因为三铰共线，体系瞬变。设该 体系受图示荷载P F 作用，体系C 点发生微小位移 δ，AC 、CB 分别转过微小角度α和β。微小位移 后三铰不再共线变成几何不变体系，在变形后的位置体系能平衡外荷P F ，取隔离体如图所 示，则列投影平衡方程可得 210 cos cos 0x F T T βα=?=∑，21P 0 sin sin y F T T F βα=+=∑ 由于位移δ非常小，因此cos cos 1βα≈≈，sin , sin ββαα≈≈，将此代入上式可得 21T T T ≈=，()P P F T F T βαβα +==?∞+， 由此可见，瞬变体系受荷作用后将产生巨大的内力，没有材料可以经受巨大内力而不破坏，因而瞬变体系不能作为结构。由上分析可见，虽三铰不共线，但当体系接近瞬变时，一样将产生巨大内力，因此也不能作为结构使用。 4．平面体系几何组成特征与其静力特征间关系如何? 答：无多余约束几何不变体系?静定结构（仅用平衡条件就能分析受力） 有多余约束几何不变体系?超静定结构（仅用平衡条件不能全部解决受力分析） 瞬变体系?受小的外力作用，瞬时可导致某些杆无穷大的内力 常变体系?除特定外力作用外，不能平衡 5． 系计算自由度有何作用？ 答：当W >０时，可确定体系一定可变；当W <０且不可变时，可确定第４章超静定次数；W ＝０又不能用简单规则分析时，可用第２章零载法分析体系可变性。 6．作平面体系组成分析的基本思路、步骤如何？ 答：分析的基本思路是先设法化简，找刚片看能用什么规则分析。 《操作系统原理》练习题 一、填空题 1. 每个进程都有一个生命周期，这个周期从__(1)__开始，到__(2)__而结束。 2. 当一个进程独占处理器顺序执行时，具有两个特性：__(3)__和可再现性。 3. 并发进程中与共享变量有关的程序段称为__(4)__。 4. 一个进程或者由系统创建，或者由__(5)__创建。 5. 一个进程的静态描述是处理机的一个执行环境，被称为__(6)__。 6. 信号量的物理意义是：信号量大于0，其值为__(7)__；信号量小于0，其绝对值为__(8)__。 7. 系统有某类资源5个，供3个进程共享，如果每个进程最多申请__(9)__个该类资源，则系统是安全的。 8. 不可中断的过程称为__(10)__。 9. 操作系统中，进程可以分为__(11)__进程和__(12)__进程两类。 10. 操作系统为用户提供两种类型的使用接口，它们是__(13)__接口和__(14)__接口。 11. 批处理操作系统中，操作员根据作业需要把一批作业的有关信息输入计算机系统，操作系统选择作业并根据__(15)__的要求自动控制作业的执行。 12. 在批处理兼分时的系统中，往往由分时系统控制的作业称为前台作业，而由批处理系统控制的作业称为__(16)__作业。 13. 采用SPOOL技术的计算机系统中，操作员只要启动__(17)__程序工作，就可以把作业存放到__(18)__中等待处理。 14. 作业控制方式有__(19)__方式和__(20)__方式二种。 15. 对资源采用抢夺式分配可以防止死锁，能对处理器进行抢夺式分配的算法有__(21)__算法和__(22)__算法。 16. 因争用资源产生死锁的必要条件是互斥、__(23)__、不可抢占和__(24)__。 17. 死锁的形成，除了与资源的__(25)__有关外，也与并发进程的__(26)__有关。 18. 为破坏进程循环等待条件，从而防止死锁，通常采用的方法是把系统中所有资源类进行__(27)__，当任何一个进程申请两个以上资源时，总是要求按对应资源号__(28)__次序申请这些资源。 19. 内存管理的核心问题是如何实现__(29)__的统一，以及它们之间的__(30)__问题。 20. 页式存储管理中，处理器设置的地址转换机构是__(31)__寄存器。 21. 在页式和段式存储管理中，__(32)__存储管理提供的逻辑地址是连续的。 22. 实现地址重定位或地址映射的方法有两种：__(33)__和__(34)__。 23. 在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，__(35)__的作业将得到优先调度；当各个作业要求运行的时间相同时，__(36)__的作业得到优先调度。 24. 确定作业调度算法时应注意系统资源的均衡使用，即使CPU繁忙的作业和__(37)__的作业搭配使用。 25. 按照组织形式分类文件，可以将文件分为普通文件、目录文件和__(38)__。 26. 文件系统为用户提供了__(39)__的功能，以使得用户能透明地存储访问文件。 27. 文件名或记录名与物理地址之间的转换通过__(40)__实现。 28. 文件的__(41)__与文件共享、保护和保密紧密相关。 第2章操作系统的界面 (1) 请说明系统生成和系统引导的过程。 解： 系统的生成过程：当裸机启动后，会运行一个特殊的程序来自动进行系统的生成（安装），生成系统之前需要先对硬件平台状况进行检查，或者从指定文件处读取硬件系统的配置信息，以便根据硬件选择合适的操作系统模块组，比较重要的信息通常有：CPU类型、内存大小、当前关联设备的类型和数量以及操作系统的重要功能选项和参数。按照这些信息的指示，系统生成程序就可以正确地生成所需的操作系统。 系统引导的过程：系统引导指的是将操作系统内核装入内存并启动系统的过程。主要包括初始引导、内核初始化、全系统初始化。初始引导工作由BIOS完成，主要完成上电自检，初始化基本输入输出设备，载入操作系统内核代码等工作。内核被载入内存后，引导程序将CPU控制权交给内核，内核将首先完成初始化功能，包括对硬件、电路逻辑等的初始化，以及对内核数据结构的初始化，如页表(段表)等。全系统初始化阶段要做的就是启动用户接口程序，对系统进行必要的初始化，使系统处于等待命令输入状态。 (2) 操作系统具有哪些接口？这些接口的作用是什么？ 解： 操作系统为用户提供的接口有图形接口、命令接口和程序接口几种形式。 操作系统包括三种类型的用户接口：命令接口（具体又可分为联机命令接口与脱机命令接口）、程序接口及图形化用户接口。其中，命令接口和图形化用户接口支持用户直接通过终端来使用计算机系统，而程序接口则提供给用户在编制程序时使用。 (3) 请说明操作系统具有的共性服务有哪些不同类别，这些类别分别用于完成什么功能？ 解：所有的操作系统都通过一些基本服务来帮助用户简单便捷地使用计算机各类资源，它们包括以下几个类别： 1.控制程序运行：系统通过服务将用户程序装入内存并运行该程序，并且要控制程序 在规定时间内结束。 2.进行I/O操作：用户是不能直接控制设备的，只能通过操作系统与外部设备进行交 互，由系统调用将结果显示在屏幕上或交给用户。 3.操作文件系统：为了保证实现“按名存取”，文件系统应该为用户提供根据文件名 来创建、访问、修改、删除文件的方法，以确保文件数据的安全可靠以及正确存取。 4.实现通信：操作系统需要提供多个程序之间进行通讯的机制，来控制程序的执行顺 序。 5.错误处理：操作系统通过错误处理机制，以便及时发现错误并采取正确的处理步骤， 避免损害系统的正确性和统一性。 (4) 系统调用的用途是什么？ 解： 通常，在操作系统内核设置有一组用于实现各种系统功能的子程序(过程)，并将它们提供给用户程序调用。每当用户在程序中需要操作系统提供某种服务时，便可利用一条系统调用命令，去调用所需的系统过程。这即所谓的系统调用。系统调用的主要类型包括： 1.进程控制类，主要用于进程的创建和终止、对子进程结束的等待、进程映像的替换、 进程数据段大小的改变以及关于进程标识符或指定进程属性的获得等； 2.文件操纵类，主要用于文件的创建、打开、关闭、读/写及文件读写指针的移动和 参考答案 1．简述信息经济的主要标志。 答：信息经济是指以信息为经济活动之基础，以信息产业为国民经济之主导产业的一种社会经济形态。信息经济作为一种新型的社会经济结构，其主要标志有： （1）信息资源成为人类社会的主要经济资源；信息作为一种经济资源，其表现除了参与创造财富外，还表现在对质能资源的替代节约上，因此把信息当作资源来看待，不仅表现在对信息的重视上，还表现在对物质、能源的节约上。 （2）现代信息技术成为经济生活中的主要技术；信息技术是指开发和利用、采集、传输、控制、处理信息的技术手段。信息资源的开发，使信息量剧增，信息的经济功能骤显，如何把握瞬息万变的信息，为人们的经济生活服务，成为人类的一大难题。信息技术的适时出现，解决了人类的一大难题，信息技术的发展水平与应用程度，也就成为信息经济成熟与否的一个指标。 （3）产品中的信息成分大于质能成分；在信息经济社会，产品中的信息含量增加，信息成分大于质能成分。但并不是说每一种产品的信息成分均大于其质能成分，而是就整体而言的，除了增加物质产品中的信息含量外，信息产品日益丰富。也就是说，在信息经济社会中，产品结构以信息密集型物质产品和信息产品为主。 （4）产业部门中信息劳动者人数占总从业人数的比例大于物质劳动者所占比例；就信息劳动者人数而言，将其限制在产业部门，即农业、工业、服务业和信息产业部门的劳动者，不包括非产业部门的信息劳动者，其中信息劳动者人数占总从业人数的比例大于农业、工业、服务业中任何一个部门物质劳动者所占的比例。 （5）信息部门的产值占国民生产总值的比重大于物质部门产值所占的比重；信息部门的产值一般是指产业化了的信息部门的产值，信息部门产值占国民生产总值的比重大于农业、工业、服务业中任何一个部门产值所占比重。 2．简要叙述信息经济形成的时代背景。 答：（1）人类需求的渐进。随着社会的进步，生产力的发展，质能经济的产品已经不能完全满足人类的需要，只有靠增加物质产品中的信息含量，采用现代信息技术，发展信息产业，才有可能较好地满足人们的需要。这就促使质能经济向信息经济转化。 （2）物质经济的滞胀。二战后的经济危机使得资本主义发达国家不得不寻求对策，一方面实行大量资本输出，一方面按照“需求决定论”调整产业结构，使其向着知识、技术、信息密集型方向发展。 （3）质能资源的短缺。随着质能经济的发展，加之世界人口的急剧增长和资源的挥霍浪费，使质能资源频频告急，从1973年起，人类开始自觉主动地利用信息发展经济。 [试题分类]:专科《操作系统原理及应用》_08004260 [题型]:单选 [分数]:2 1.批处理最主要的一个缺点是（）。 A.用户无法与程序交互 B.没有实现并发处理 C.CPU的利用率较低 D.一次只能执行一个程序 答案:A 2.磁盘空闲块常用的组织形式有三种，其中一种为（）。 A.空闲块连续 B.空闲块索引 C.空闲块压缩 D.空闲块链 答案:D 3.常用的文件物理结构有三种，其中的一种形式是（）。 A.记录文件 B.压缩文件 C.索引文件 D.流式文件 答案:C 4.批处理系统中，作业的状态可分为多种，其中一种为（）。 A.提交 B.就绪 C.创建 D.等待 答案:A 5.并发执行的一个特点是（）。 A.计算结果会出错 B.不会顺序执行 C.程序与计算不再一一对应 D.结果可再现 6.下列选项（）不是操作系统关心的。 A.管理计算机资源 B.提供用户操作的界面 C.高级程序设计语言的编译 D.管理计算机硬件 答案:C 7.当CPU执行用户程序的代码时，处理器处于（）。 A.核心态 B.就绪态 C.自由态 D.用户态 答案:D 8.根据对设备占用方式的不同，设备分配技术中的一种是（）。 A.动态分配 B.永久分配 C.静态分配 D.虚拟分配 答案:D 9.评价作业调度的性能时，衡量用户满意度的准确指标应该是（）。 A.周转时间 B.平均周转时间 C.带权周转时间 D.平均带权周转时间 答案:C 10.在手工操作阶段，存在的一个严重的问题是（）。 A.外部设备太少 B.用户使用不方便 C.计算机的速度不快 D.计算机的内存容量不大 答案:B 11.作业的处理一般分为多个作业步，连接成功后，下一步的工作是（）。 地理信息系统2010年考研试题 一名词解释（40分共8个小题每题5分） 1、对象模型：也称要素模型，将研究的整个地 理空间看成一个空域，地理现象和空间实体作为独立对象分布在该空域中。24页 2、关系模型：它是将数据的逻辑结构归结为满 足一定条件的二维表，这种表称为关系。 3、误差：表示数据与其真值之间的差。84页 4、层次分类编码法：是按照分类对象的从属和 层次关系为排列顺序的一种代码。它的优点是能明确表示出分类对象的类别，代码结构有严格的隶属关系。64页 5、网格GIS：网格被称为第三代互联网应用，它是把整个互联网整合成一台巨大的超级计算机，能实现各种资源的全面共享。 6、邻接关系：它是指空间图形中同类元素之间 的拓扑关系。 7、TIN：是专为产生DEM数据而设计的一种采样表示系统 8、ComGIS：是面向对象技术和组件式软件在GIS软件开发中的应用。（186页） 二简答题（70分，每题10分） 1、GIS是解决什么问题的？ 答：“有用的空间信息和知识”可归纳为位置、条件、趋势、模型和模拟等五个基本问题，GIS的价值和作用就是通过地理对象的重建，利 用空间分析工具，实现对这五个基本问题的求解。 地理信息系统包括以下五项基本功能：（1）数据采集与输入（2）数据编辑与更新（3）数据存储与管理 （4）空间查询与分析（5）数据显示与输出2、什么是矢量数据结构？其特点是什么？ 答：适量数据结构：通过记录空间对象的坐标 及空间关系表达空间对象的几何位置。 矢量结构的特点：定位明显，属性隐含。 3、空间数据的获取方式有哪些？ 答：（1）数字化仪矢量化（2）扫描数字化（3）遥感数据获取（4）外业测量数据获取（5）全球定们系统数据获取（6）数字摄影测量数据获取（7）已有数据的获取与转换4、什么是空间数据压缩？空间数据压缩的方 法？ 答：空间数据压缩是指从取得的数据集合中抽取一个子集，这个子集作为一个新的信息源，在规定的精度范围内最好地逼近原集合，而又取得尽可能大的压缩比。 （1）栅格数据压缩：栅格数据压缩是指栅格数据量的减少，这与栅格数据结构密切相关。其压缩方法有游程长度编码、链码、块状编码、四叉树编码等 （2）曲线矢量数据压缩：①间隔取点法：每隔一规定的距离取一点，舍去那些离已选点较近的点，但首末点必须保留。 ②垂距法，垂距法是按垂距的限差选取符合或超过限差的点。 ③偏角法，是按偏角的限差选取符合或超过限差的点。 ④特征点筛选法，是通过筛选抽取曲线特征点，并删除非特征点以实现数据压缩。 5、试述DEM的建立方法？以及包含的模型有哪些？ 答：（1）DEM数据源（2）DEM数据采集方法（3）数据摄影测量获取DEM（4）DEM的空间插值方法 DEM的主要表示模型：规则格网模型、不规则三角网模型、等高线模型。 6、GIS工程的特点？GIS工程的建设过程？（202页） 答：GIS工程的主要特点有以下几个方面： ⑴空间数据的管理在工程中处于核心地 位 ⑵系统体系结构相对复杂 ⑶系统维护工作量大 ⑷系统更新速度快 ⑸应用领域广阔 GIS工程的建设过程： ⑴工程定义阶段 ⑵工程设计阶段 ⑶数据工程阶段 ⑷工程实施阶段 ⑸工程的评价与维护阶段 7、试述ArcCatalog主要功能249页 答：ArcCatalog数据管理功能1.第一章课后习题及答案
第1章课后习题参考答案
操作系统原理答案(张丽芬)
习题答案-Linux操作系统原理实践教程-崔继-清华大学出版社
操作系统原理实验-系统内存使用统计5
操作系统原理及应用试题附答案
操作系统原理考题及答案
操作系统原理课程设计实践报告
信号与系统课后习题答案—第1章
操作系统原理与应用第2章文件管理
操作系统原理实验四
第1章思考题及参考答案
操作系统原理练习题附答案
操作系统原理与实践教程(第二版)第2章习题答案
第一章思考题参考答案
专科《操作系统原理及应用》
河北师大地理信息系统原理与实践考研真题及答案
相关主题
文本预览