Chap 6 in Software

Creating QR Code ISO/IEC18004 in Software Chap 6

ment of probability theory, and Kleinrock75 covers the theory and practice of queuing systems Queuing analysis Hellerman75 and Stone75 consider queuing problems in computer systems; Graham78 and Denning78 provide surveys Kobayashi78 approaches performance issues formally BrinchHansen73 analyzes queuing in time-shared processing, but many of the assumptions do not hold for le systems Allen75 and ibm f20-771 summarize queuing theory for message-processing systems, and Martin72 includes some approximations to queuing results Newell71 applies queuing to rush-hour transients, using a parabolic approximation; the sinewave-based approach presented here was original in Wiederhold77,83 and appears simpler Many of the analyses of scheduling disciplines in the previous section use results from queuing theory Linear Programming Morgan74 describes replacement algorithms for les on mountable diskpacks and uses linear programming (LP) for some solutions Benner67 uses LP to optimize record allocation in an ims-like hierarchical structure, and Stanfel70 uses LP to optimize fetch time in trees Chu69 and Severance72 apply LP to le design A codasyl database is optimized by De78 Ramamoorthy79 , Chen80 , and Ceri82 use OR to design distributed databases Levin78 uses a branch-and-bound method Pelegatti in Bernstein79 and Ceri82 minimize the communication costs Reorganization Analyses The use of techniques developed for inventory control to determine the time interval for le reorganization is due to Shneiderman73 Arora71 , Vold73 , Yao76 , Tuel78 , and Batory82 address the same problem Sockut78 models concurrent reorganization and provides a survey (Sockut79 ) Young74 and Lohman77 use a similar technique to obtain the required interval for writing le backup copies

Redo Exercise 4-100000000000000000000000000000000000000000000000000000000000000000000 given that the text lines are of length 70 with a standard deviation of 30 characters Equation 2-2 is based on uniform track access Redo this result, given that the request rate for tracks has a Poisson distribution over the track numbers with a mean of 05

Sketch a distribution of the access times between blocks on tape Calculate the standard deviation Do Exercise 3 for a disk or other direct-access unit

What queue-scheduling policy is used by the le system that you have been using Do you nd the policy reasonable Which users are being favored and which are being discriminated against Prepare an argument to management for changing the policy In Example 6-4, used to demonstrate the normal distribution, space was saved by placing fewer records into a block When is the technique apt to be e ective in an indexed or in a hashed le

Reevaluate the same example for the case that the distribution was not normal, but symmetric and unimodal

8 Section 6-1-6 stresses understanding of the model when applying transformations What was the model used for the billing data Does it make sense Using this model, what is the expectation of outstanding bills if the hospital doubles size and billings What can cause failure of the model 9

10 Read a scheduling algorithm other than FIFO used for processor scheduling and apply it to a le system Compare the e ectiveness and the validity of the analysis in the le environment 11 During lunch hour a large number of orders for stock purchases are placed at a brokerage, creating a queue within the processor which updates the order le Estimate the earliest time when the entire order le can be tabulated 12 Write a program to simulate the queue management ow of Fig 6-10 Include two selection algorithms and compare the processing of identical workloads Explain the di erences in behavior

Describe how a random-number-generating routine generates a uniform distribution Describe how a normal random-distribution routine generates values which are normally distributed, using a uniform-distribution-generating routine The listings of the programs used can be found in the documentation of your computer service

13 14 Using the Poisson distribution of Example 6-5 as an example, compute the mean and the mode, and use Eq 6-1 to estimate the median from the mean and the mode Apply these to some moderately skewed distributions 15 Recalculate the expected update cost for an indexed le (Chap 3-4-3), given that one attribute only is updated, and that it has been determined that data changes are distributed normally around the current data value, with a relatively small standard deviation, say 100 for n = 10 000

We now will apply some distributions to the les of your application and their use Consider the length of the records Let the records be of variable length and assume the standard deviation of the length to be of at least 30% of the average record length R If you use variable-length and unspanned blocking: a How many records t into a block if consider only the average record length b How many records t into a block if consider only the record length to be normally distributed, and you want to exceed the block less than 1% of the time (t = 232) c How many records t into a block, again with less than 1% over ow, if you cannot predict the distribution, so that you have to use the Chebyshe assumption Write a simulation where variable length records are placed into blocks, up to the estimated Bfr Use the same parameters assigned for Exercise 16