viewing paste Chapter 7-11 Answer | Text

Posted on the
  1. Chapter 7 Exercises and Answers 
  2. For Exercises 1–15, mark the answers true and false as follows: 
  3.  
  4. A. True 
  5. B. False 
  6. 1. Arithmetic can be performed in the instruction register. 
  7. B 
  8.  
  9. 2. Arithmetic can be performed in the A register. 
  10. A 
  11.  
  12. 3. Arithmetic can be performed in the accumulator. 
  13. A 
  14.  
  15. 4. The Z bit is 1 if the accumulator is 0. 
  16. A 
  17.  
  18. 5. The N bit is 0 of the accumulator is negative. 
  19. B 
  20.  
  21. 6. The program counter and the instruction register are two names for 
  22. the same place. 
  23. B 
  24.  
  25. 7. The A register and the accumulator are two names for the same place. 
  26. A 
  27.  
  28. 8. The instruction register is three bytes long. 
  29. A 
  30.  
  31. 9. The program counter is three bytes long. 
  32. B 
  33.  
  34. 10. The status bits are each one byte long. 
  35. B 
  36.  
  37. 11. The instruction specifier is two bytes long. 
  38. B 
  39.  
  40. 12. If the data to be loaded into the accumulator is stored in the operand, the instruction specifier is 00. 
  41. A 
  42.  
  43. 13. If the data in the accumulator is to be stored in the place named in the operand, the instruction specifier is 00. 
  44. B 
  45.  
  46. 14. All Pep/7 instructions occupy three bytes. 
  47. B 
  48.  
  49. 15. The branching instructions test the status bits. 
  50. A 
  51.  
  52. Given the following state of memory (in hexadecimal), answer Exercises 16–20 by matching the problem to the solution shown. 
  53.  
  54. 0001 A2
  55. 0002 11
  56. 0003 FF
  57. 0004 00
  58.  
  59. A. 10100010 00010010 
  60. B. 11111111 00000000 
  61. C. 00000000 00000011 
  62. D. 11101101 00000001 
  63. E. 00010010 00000000 
  64.  
  65. 16. What are the contents of the A register after the execution of this instruction? 
  66. 00001000 00000000 00000011 
  67. C 
  68.  
  69. 17. What are the contents of the A register after the execution of this instruction? 
  70. 00001001 00000000 00000011 
  71. B 
  72.  
  73. 18. What are the contents of the A register after the execution of the following two instructions? 
  74. 00001001 00000000 00000001 
  75. 00011000 00000000 00000001 
  76. A 
  77.  
  78. 19. What are the contents of the A register after the execution of the following two instructions? 
  79. 00001000 00000000 00000001 
  80. 00011001 00000000 00000010 
  81. E 
  82.  
  83. 20. What are the contents of the A register after the execution of the following two instructions? 
  84. 00001001 00000000 00000011 
  85. 00100001 00000000 00000010 
  86. D 
  87.  
  88. Exercises 21–53 are programs or short-answer questions. 
  89.  
  90. 21. What does it mean when we say that a computer is a programmable device? 
  91. Programmable means that data and instructions are logically the same and are stored in the same place. The consequence of
  92.  this fact is that the program the computer executes is not wired into the hardware but entered from outside.
  93.  
  94. 22. List five operations that any machine language must include. 
  95. There must be machine-language instructions to store, retrieve, and process data, to input data and to output data. These 
  96. instructions mirror the operations of the von Neumann machine. 
  97.  
  98. 23. The distinction between concrete and abstract steps in algorithms is not always clear-cut. Discuss this dilemma and give
  99.  concrete examples to support your discussion. 
  100. Algorithms are eventually coded in a programming language. 
  101. Different programming languages represent different levels of abstraction. What takes a single step in one language may take 
  102. many steps in another language. Thus, a concrete step in one language may be an abstract step in another. 
  103.  
  104. 24. What is a virtual machine? Discuss this definition in terms of the Pep/7 computer. 
  105. A virtual machine is a hypothetical machine designed to illustrate 
  106. important features of a real computer. The Pep/7 computer is a virtual 
  107. machine designed to illustrate the features of the von Neumann architecture. It has instructions to store, retrieve, and process 
  108. data as well as instructions to input and output data. 
  109.  
  110. 25. We said that you should have guessed that a Pep/7 instruction would use 5 bits when we said that there were 32 
  111. instructions. Explain. 
  112. It takes exactly 5 bits to represent 32 different things, instructions in this case. 
  113.  
  114. 26. Describe the features of the Pep/7 CPU that we covered in this chapter. 
  115. There is one register for arithmetic and logical operations: the A register (the accumulator). There is a Program Counter that 
  116. contains the address of the next instruction to be executed and the Instruction Register that contains the instruction being 
  117. executed. There are two status bits: N and Z which are one if the accumulator is negative or zero respectively. Memory is byte 
  118. addressable. 
  119.  
  120. 27. We covered only two of the four addressing modes. If we had not stated this explicitly, could you have deduced that this 
  121. was true? Explain. 
  122. If there were only two addressing modes, one bit would have been used instead of two. Because two bits are used, there 
  123. must be four modes. 
  124.  
  125. 28. Where is the data (operand) if the address mode specifier is: a. 00 
  126. If the address mode specifier is 00, the data is in the operand specifier. 
  127. b. 01 
  128. If the address mode specifier is 01, the data is stored in the place named in the operand specifier.
  129.  
  130. 29. Distinguish between the IR (instruction register) and the PC (program counter). 
  131. The IR contains an instruction (the one being executed); the PC contains an address (the address of the next instruction to 
  132. be executed).
  133.  
  134. 30. How many bits are required to address the Pep/7 memory? 
  135. The Pep/7 memory contains 4096 bytes, so 12 bits are required to address each one.
  136.  
  137. 31. How many more cells could be added to memory without having to change the instruction format? Justify your answer. 
  138. The operand specifier is 16 bits long. Therefore 216 different bytes could be addressed without changing the instruction 
  139. format. Thus, 61440 more bytes could be added.
  140.  
  141. 32. Some Pep/7 instructions are unary, taking only one byte. Other instructions require three bytes. Given the instructions that 
  142. we have covered in this chapter, would it be useful to define instructions that require only two bytes? 
  143. The instructions we have covered, other than the Stop instruction, use the operand specifier of the instruction. The operand 
  144. specifier is two bytes long, so three bytes are required for the instruction: the instruc tion specifier and the operand specifier. 
  145. Therefore, two-byte instruc tions would not be useful.
  146.  
  147. 33. If the input character is A, what is the result of executing the following two instructions? 
  148. 0001 11011001 00000000 00000110 
  149. 0004 11100000 00000000 00001010 
  150. A is written on the screen. 
  151.  
  152. 34. If the input character is A, what is the result of executing the following two instructions? 
  153. 0001 11011001 00000000 00000110 
  154. 0004 11100001 00000000 00001010 
  155. What ever is stored in location 01000001 is written on the screen. 
  156.  
  157. 35. Write the algorithm for writing out your name, given that the implementation language is Pep/7 machine code. 
  158. Write “Nell” 
  159.  
  160. Write “Nell” 
  161. Write “N” 
  162. Write “e” 
  163. Write “l” 
  164. Write “l” 
  165.  
  166. Write “N” 
  167.  
  168. Write 4E (hex)
  169. Write “e”
  170. Write 65 (hex)
  171. Write “l”
  172. Write 6C (hex)
  173. Write “l”
  174. Write 6C (hex)
  175.  
  176.  
  177. 36. Write the machine-language program to implement the algorithm in Exercise 35. 
  178. E0 00 4E E0 00 65 E0 00 6C E0 00 6C zz 
  179.  
  180. 37. Write the algorithm for writing out your name, given that the implementation language is Pep/7 assembly language. 
  181. Write “Nell” 
  182.  
  183. Write “Nell” 
  184. Write “N” 
  185. Write “e” 
  186. Write “l” 
  187. Write “l” 
  188.  
  189. 38. Write the assembly-language program to implement the algorithm in Exercise 37. 
  190. CHARO h#0010,d ;Output ‘N’
  191. CHARO h#0011,d ;Output ‘e’
  192. CHARO h#0012,d ;Output ‘l’
  193. CHARO h#0013,d ;Output ‘l’
  194. STOP
  195. .ASCII /Nell/ ;Store ‘Hello’ into proper places
  196. .END
  197.  
  198.  
  199. 39. Rewrite the machine language program in 7.4, using direct addressing. 
  200. E1 00 10 E1 00 11 E1 00 12 E1 00 13 E1 00 14 00 48 65 6C
  201. 6C 6F zz
  202.  
  203.  
  204. 40. Distinguish between the Pep/7 menu options Load, Load/Execute, and Execute. 
  205. Load puts the program in memory ready to execute. Load/Execute loads the program into memory and executes it. If a 
  206. program is loaded, an Execute command executes the program. If the active window contains a machine language program 
  207. and there is no loaded program, the Execute command loads and executes it.
  208.  
  209. 41. The following program seems to run, but does strange things with certain input values. Can you find the bug? 
  210. BR Main
  211. sum: .WORD d#0
  212. num1: .BLOCK d#1
  213. num2: .BLOCK d#1
  214. num3: .BLOCK d#1
  215. Main: LOADA sum,d
  216.  
  217. DECI num1,d
  218. DECI num2,d
  219. DECI num3,d
  220. ADDA num3,d
  221. ADDA num2,d
  222. ADDA num1,d
  223. STOREA sum,d
  224. DECO sum,d
  225. STOP
  226. .END
  227.  
  228. One byte of storage is set up for each input value. If the value that is read is grater than one byte, the excess spills over to 
  229. the byte above giving the wrong answer. 
  230.  
  231. 42. Correct the code in Exercise 41 and run the test plan outlined in the chapter. 
  232. BR Main 
  233. sum: .WORD d#0 
  234. num1: .BLOCK d#2 
  235. num2: .BLOCK d#2 
  236. num3: .BLOCK d#2 
  237. Main: LOADA sum,d 
  238. DECI num1,d 
  239. DECI num2,d 
  240. DECI num3,d 
  241. ADDA num3,d 
  242. ADDA num2,d 
  243. ADDA num1,d 
  244. STOREA sum,d 
  245. DECO sum,d 
  246. STOP 
  247. .END 
  248. The test plan gives the correct answers with this code. 
  249.  
  250. 43. Finish executing the test plan for the algorithm in the text that reads and sums three values. 
  251. The answers are correct. 
  252.  
  253. 44. Write an algorithm that reads in three values and writes out the result of subtracting the second value from the sum of the 
  254. first and the third values. 
  255. Read num1
  256. Read num2
  257. Read num3
  258. Load num1
  259. Add num3
  260. Sub num2
  261. Store in answer
  262. Write answer
  263.  
  264. 45. Implement the algorithm in Exercise 44 as an assembly-language program. 
  265. BR Main 
  266. answer: .WORD d#0 
  267. num1: .BLOCK d#2 
  268. num2: .BLOCK d#2 
  269. num3: .BLOCK d#2 
  270. Main: DECI num1,d 
  271. DECI num2,d 
  272. DECI num3,d 
  273. LOADA num1,d 
  274. ADDA num3,d 
  275. SUBA num2,d 
  276. STOREA answer,d 
  277. DECO answer,d 
  278. STOP 
  279. .END 
  280.  
  281. 46. Write and implement a test plan for the program in Exercise 45. 
  282. Reason for Test Case Input Values Expected Output Observed Output 
  283. Assumption: Input values are no greater than 215 –1 or less than – 215. 
  284. Input three positive numbers 4, 6, 1 –1 –1 
  285. Input three negative numbers –4, –6, –1 1 1 
  286. Input mixed numbers 4, 6, –1 –3 –3 
  287. 4, –6, 1 11 11 
  288. 4, –6, –1 –9 –9 
  289. –4, 6, 1 –9 –9 
  290. –4, 6, –1 –11 –11 
  291. –4, –6, 1 3 –3 
  292. Large numbers 32767, –1, +1 overflows overflows 
  293. 32767, 1, –1 32767 
  294.  
  295. 47. Design and implement, in assembly language, an algorithm that reads four values and prints the sum. 
  296. Set count to 0 
  297. Set sum to 0 
  298. While count < 4 
  299.  
  300. Read num 
  301. Add num to sum 
  302. Increment count 
  303.  
  304. Write sum 
  305.  
  306. BR Read ;branch to location Read 
  307. sum: .WORD d#0 ;set zero word 
  308. count: .WORD d#0 ;set up a two byte block for count 
  309. limit: .WORD d#4 ;set up a block for value 4 
  310. number:.WORD d#0 ;set up word for value read 
  311.  
  312. Read: LOADA sum,d ;load a copy of sum into accumulator 
  313. DECI number,d ;read and store a decimal number 
  314. ADDA number,d ;add the number to the accumulator 
  315. STOREA sum,d ;store accumulator in sum 
  316. LOADA count,d ;load a copy of limit in accumulator 
  317. ADDA d#1,i ;add 1 to the accumulator 
  318. STOREA count,d ;store contents in count 
  319. SUBA limit,d ;subtract 4 
  320. COMPA d#0,i ;compare accumulator to 0 
  321. BREQ Quit ;branch to Quit if accumulator is 0 
  322. BR Read ;go back to read in another number 
  323.  
  324. Quit: DECO sum,d ;output contents of sum 
  325. STOP ;end of the program 
  326. .END 
  327.  
  328. 48. Is the test plan for a machine-language program valid for the same solution written in assembly language? Explain your 
  329. answer. 
  330. A data-coverage plan is written without looking at the code, so the 
  331. same test plan would be valid. A code-coverage plan looks at the code, 
  332. but because there is a one to one relationship between a machine code 
  333. instruction and an assembly language instruction, the same test plan 
  334. would be valid. 
  335.  
  336.  
  337. 49. Distinguish between the pseudo-code instructions .BLOCK and .WORD. 
  338. The pseudo-code instruction .BLOCK takes a decimal argument and
  339. sets aside that many bytes of storage and set them to zero. A .WORD
  340. pseudo-code instruction takes a decimal argument and generates one
  341. word of storage with the decimal value stored in it.
  342.  
  343.  
  344. 50. Distinguish between assembly-language pseudocode instructions and mnemonic instructions. 
  345. Pseudo-code instructions are instructions to the assembler; mnemonic instructions are to be translated by the assembler.
  346.  
  347.  
  348. 51. Distinguish between test plans based on code coverage and data coverage. 
  349. A code-coverage test plan is based on examining and covering the
  350. statements in the code. A data-coverage test plan is based on the input
  351. data to the program.
  352.  
  353. 52. Explain the meaning of the Pep/7 menu option Execution Input. 
  354. The Execution Input menu asks if you want the input data to come
  355. from the current window for from the keyboard.
  356.  
  357.  
  358. 53. Write the Pep/7 assembly-language statement for the following instructions: a. Branch to location Branch1 if the 
  359. accumulator is zero. 
  360. BREQ Branch1 
  361.  
  362. b. Branch to location Branch1 if the accumulator is negative. 
  363. BRLT Branch1 
  364.  
  365. c. Branch to location Branch1 if the accumulator is negative and to
  366. Branch2 if the accumulator is not negative.
  367. BRLT Branch1
  368. Branch2:
  369. That is, go to location Branch1 if the accumulator is negative. If the
  370. accumulator is not negative, the next instruction is executed, so it
  371. must be labeled Branch2.
  372.  
  373. Chapter 8
  374. ====================================================
  375. For Exercises 1–14, match the question with the appropriate translation or 
  376. execution system. 
  377.  
  378. A. Interpreter 
  379. B. Assembler 
  380. C. Compiler 
  381. D. Machine code 
  382. 1. What translates a high-level language into machine code? 
  383. C 
  384.  
  385. 2. What translates a Java program into Bytecode? 
  386. C 
  387.  
  388. 3. What executes Bytecode? 
  389. A 
  390.  
  391. 4. What translates an assembly-language program? 
  392. B 
  393.  
  394. 5. What is the output of an assembler? 
  395. D 
  396.  
  397. 6. What takes input in a high-level language and directs the computer to 
  398. perform the actions specified in each statement? 
  399. A 
  400.  
  401. 7. What executes the Java Virtual Machine? 
  402. D 
  403.  
  404. 8. What is used to translate a program in ALGOL? 
  405. C 
  406.  
  407. 9. What is used to translate a program in APL? 
  408. A 
  409.  
  410. 10. What is used to translate a program in COBOL? 
  411. C 
  412.  
  413. 11. What is used to translate a program in FORTRAN? 
  414. C 
  415.  
  416. 12. What is used to translate a program in Lisp? 
  417. A 
  418.  
  419. 13. What is used to translate a program in SNOBOL4? 
  420. A 
  421.  
  422. 14. Which translator runs the slowest? 
  423. A 
  424.  
  425. For Exercises 15–36, match the language paradigm and the language or 
  426. the language description. 
  427.  
  428. A. Imperative or procedural 
  429. B. Functional 
  430. C. Logic 
  431. D. Object oriented 
  432. E. Procedural language with some object-oriented features 
  433. F. Object-oriented language with some procedural features 
  434. 15. Which paradigm most accurately describes FORTRAN? 
  435. A 
  436.  
  437. 16. Which paradigm most accurately describes C++? 
  438. E 
  439.  
  440. 17. Which paradigm most accurately describes PASCAL? 
  441. A 
  442.  
  443. 18. Which paradigm most accurately describes Java? 
  444. F 
  445.  
  446. 19. Which paradigm most accurately describes Lisp? 
  447. B 
  448.  
  449. 20. Which paradigm most accurately describes BASIC? 
  450. A 
  451.  
  452. 21. Which paradigm most accurately describes PROLOG? 
  453. C 
  454.  
  455. 22. Which paradigm most accurately describes SIMULA? 
  456. D 
  457.  
  458. 23. Which paradigm most accurately describes ALGOL? 
  459. A 
  460.  
  461. 24. Which paradigm most accurately describes ML? 
  462. B 
  463.  
  464. 25. Which paradigm most accurately describes Scheme? 
  465. B 
  466.  
  467. 26. Which paradigm most accurately describes Ada? 
  468. A 
  469.  
  470. 27. Which paradigm most accurately describes C? 
  471. A 
  472.  
  473. 28. Which paradigm most accurately describes Smalltalk? 
  474. D 
  475.  
  476. 29. The dominant languages used in industry throughout the history of 
  477. computing software come from which paradigm? 
  478. A 
  479.  
  480. 30. Which paradigm did Japanese researchers choose for the fifth-generation computer? 
  481. C 
  482.  
  483. 31. Which paradigm allows the programmer to express algorithms as a 
  484. hierarchy of objects? 
  485. D 
  486.  
  487. 32. Which paradigm allows the programmer to express algorithms as a 
  488. hierarchy of tasks? 
  489. A 
  490.  
  491. 33. Which paradigm allows the programmer to express algorithms as 
  492. mathematical functions? 
  493. B 
  494.  
  495. 34. Which paradigm has no assignment statement? 
  496. B 
  497.  
  498. 35. Which paradigm uses recursion exclusively to express repetition? 
  499. B 
  500.  
  501. 36. Which paradigm has no variables? 
  502. B 
  503.  
  504. Exercises 37–82 are problems or short-answer questions. 
  505.  
  506. 37. What is the hallmark of an assembly language? 
  507. The hallmark of an assembly language is that each assembly language 
  508. instruction is translated into one machine language instruction. 
  509.  
  510. 38. Distinguish between an assembler and a compiler. 
  511. An assembler translates assembly-language instructions into machine 
  512. code. A compiler translates high-level language instructions into 
  513. machine code. The translation of an assembler is one to one: One 
  514. statement in assembly language is translated into one statement in 
  515. machine code. The translation of a compiler is one to many: One high-
  516. level language instruction is translated into many machine language 
  517. instructions. 
  518.  
  519. 39. Distinguish between a compiler and an interpreter. 
  520. The output from a compiler is a machine-language program. That 
  521. program may be stored for later use or immediately executed, but the 
  522. execution is a distinct process from the translation. The output from 
  523. an interpreter is a solution to the original problem, not a program that 
  524. when executed gives you the solution. 
  525.  
  526. 40. Compare and contrast an assembler, a compiler, and an interpreter. 
  527. All three are translators. They differ in the complexity of the 
  528. languages they translate and in the output from the translator. Assemblers and compilers 
  529. produce machine-language programs, which when run solve the original problem; 
  530. interpreters produce solutions to the original problem. Assemblers translate very simple languages; 
  531. compilers and interpreters can translate very complex languages. 
  532.  
  533. 41. Describe the portability provided by a compiler. 
  534. A program written in a high-level language that is compiled can be 
  535. translated and run on any machine that has a compiler for the 
  536. language. 
  537.  
  538. 42. Describe the portability provided by the use of Bytecode. 
  539. Bytecode is the output from (usually) a Java compiler. There is a 
  540. virtual machine for which Bytecode is the machine language. A 
  541. program compiled into Bytecode can be executed on any system that 
  542. has a simulator for the virtual machine. The Java Virtual Machine 
  543. (JVM) executed Bytecode. 
  544.  
  545. 43. Describe the process of compiling and running a Java program. 
  546. A Java program is compiled into Bytecode, which can be executed on 
  547. any system with a JVM. 
  548.  
  549. 44. Discuss the word paradigm as it relates to computing. 
  550. Programming languages reflect differing views of reality, which we call 
  551. paradigms. We use these views (paradigms) to classify the languages. 
  552.  
  553. 45. Name four programming language paradigms and give an example 
  554. language in each. 
  555. Imperative or procedural paradigm: Fortran, Basic, Cobol, C, C++ 
  556. Functional paradigm: Lisp, Scheme, ML, FP 
  557. Logic paradigm: PROLOG 
  558. Object-oriented paradigm: Simula, Smalltalk, Java 
  559.  
  560. 46. What are the characteristics of the imperative paradigm? 
  561. Programs describe the processes necessary to solve the problem. 
  562.  
  563. 47. What are the characteristics of the functional paradigm? 
  564. Programs are expressed as the evaluation of functions. 
  565.  
  566. 48. What are the characteristics of the logic paradigm? 
  567. Rules of logic are used to deduce answers from facts and rules. 
  568.  
  569. 49. How does the view of an object-oriented program differ from the view 
  570. of an imperative program? 
  571. An object-oriented view of a program is that of interacting objects; the 
  572. imperative view of a program is that of interacting tasks. 
  573.  
  574. 50. How do you ask questions in a programming language? 
  575. To ask a question in a programming language, you make an assertion. 
  576. If the assertion is true, the answer is true. If the assertion is false, the 
  577. answer is false. 
  578.  
  579. 51. What is a Boolean variable? 
  580. A Boolean variable is a place in memory, referenced by an identifier, 
  581. that can contain true or false. 
  582.  
  583. 52. What is a Boolean expression? 
  584. A Boolean expression is a sequence of identifiers, separated by 
  585. compatible operators, that evaluates to true or false. 
  586.  
  587. 53. Given Boolean variables one, two, and three, write an assertion for 
  588. each of the following questions. 
  589. a. Is one greater than both two and three? 
  590. (one> two) AND (one> three) 
  591.  
  592. b. Is one greater than two, but less than three? 
  593. (one > two) AND (one < three) 
  594.  
  595. c. Are all three variables greater than zero? 
  596. (one > 0) AND (two > 0) AND (three > 0) 
  597.  
  598. d. Is one less than two or one less than three? 
  599. (one < two) OR (one < three) 
  600.  
  601. e. Is two greater than one and three less than two? 
  602. (two > one) AND (three < two) 
  603.  
  604. 54. Write the operation table for Boolean operation AND. 
  605. AND 0 1 
  606. 0 0 0 
  607. 1 0 1 
  608.  
  609. 55. Write the operation table for Boolean operation OR. 
  610. OR 0 1 
  611. 0 0 1 
  612. 1 1 1 
  613.  
  614. 56. Write the operation table for Boolean operation NOT. 
  615. NOT 
  616. 0 1 
  617. 1 0 
  618.  
  619. 57. What is a data type? 
  620. A data type is the description of a set of values and the basic set of
  621. operations that can be applied to values of the type.
  622.  
  623. 58. What is strong typing? 
  624. Strong typing means that each variable is assigned a data type and
  625. only values of that type can be stored in the variable.
  626.  
  627.  
  628. 59. Define the following data types. 
  629. a. integer 
  630. The range of integer values that a machine can represent. 
  631.  
  632. b. real 
  633. The range of rational numbers that a machine can represent. 
  634.  
  635. c. character 
  636. The characters in the character set that the machine supports. 
  637.  
  638. d. Boolean 
  639. The values true and false. 
  640.  
  641. 60. Is the string data type an atomic data type? Justify your answer. 
  642. A string can be output like an atomic data type, but it is made up of
  643. characters, each of which can be accessed separately. Thus, you can
  644. argue either side.
  645.  
  646. 61. If the same symbol is used for both single characters and strings, how 
  647. can you distinguish between a single character and a one-character 
  648. string? 
  649. If the same symbol is used, a character cannot be distinguished from a 
  650. one-character string. 
  651.  
  652. 62. What is a declaration? 
  653. A declaration is an instruction to the compiler that associates an identifier with a variable, 
  654. an action, or some other entity within the language that can be given a name. The programmer 
  655. can then refer to that entity by name. 
  656.  
  657. 63. Fill in the following table showing the appropriate syntactic marker or 
  658. reserved word for the language shown based on your observations of 
  659. the tables in this chapter. 
  660.  See the Answers as book.
  661.  
  662. 64. How do the .WORD and .BLOCK assembler directives in the Pep/7 
  663. assembly language differ from the declarations in high-level 
  664. languages? 
  665. .WORD allows us to associate an identifier with a word in storage
  666. and specify what should go into that word. .BLOCK allows us to asso
  667. ciate an identifier with a specified number of bytes. In each case the
  668. programmer knows the actual address associated with the identifier.
  669. Declarations in high-level languages give you the same functionality,
  670. but the programmer does not need to worry about the actual address.
  671.  
  672.  
  673. 65. Distinguish be between instructions to be translated and instructions 
  674. to the translating program. 
  675. Instructions to the translating program tell the program to associate
  676. identifiers with objects, and if the objects are data, tell the program
  677. the data type of what can be stored in that place.
  678.  
  679.  
  680. 66. Consider the following identifiers: Address, ADDRESS, AddRess, 
  681. Name, NAME, NamE 
  682. a. How many different identifiers are represented if the language is
  683. Ada?
  684. 2 
  685.  
  686. b. How many different identifiers are represented if the language is
  687. VB.NET?
  688. 6 
  689.  
  690. c. How many different identifiers are represented if the language is
  691. C++ or Java?
  692. 6 
  693.  
  694. 67. Explain the operation of the sequence control structure. 
  695. The sequence control structure say to execute the statements in
  696. sequence, one after the other.
  697.  
  698.  
  699. 68. Explain the flow of control of the if statement. 
  700. If the Boolean expression is true, execute the first statement. If the
  701. Boolean expression in false, execute the second statement. In either
  702. case continue with the statement following the second statement.
  703.  
  704. 69. Explain the difference between the then branch and the else branch in 
  705. the if statement. 
  706. An if statement is based on an expression being true or false. A case
  707. statement matches the contents of an expression with a series of values
  708. to find the statement to execute next.
  709.  
  710. 70. What is the flow of control in a while statement? 
  711. The statements within the while statement are repeated as long as the 
  712. while expression is true. When the expression becomes false, the statement following the end of the loop body is executed. 
  713.  
  714. 71. What is recursion? 
  715. Recursion is the ability of a subprogram to call itself. 
  716.  
  717. 72. How does recursion act as a repetition structure? 
  718. The program uses a selection statement to determine whether to repeat 
  719. the code by calling the subprogram again or to stop the process. 
  720.  
  721. 73. A looping structure uses a __while (loop)____________ statement; a 
  722. recursive structure uses a ___if (selection)_________ statement. 
  723. 74. Explain the statement, “Subprograms are a powerful tool for abstraction.” 
  724. A subprogram is a named task. The calling program can be designed 
  725. and written using the subprogram name without knowing how the 
  726. subprogram is implemented. 
  727.  
  728. 75. Describe how a parameter list is used to communicate information 
  729. from the calling unit to the subprogram. 
  730. A parameter list is a list of identifiers, separated by commas. These 
  731. identifiers are just place holders. When the subprogram is called, the 
  732. calling program sends the actual data the subprogram is to use. The 
  733. variables in the argument list replace the identifiers in the parameter 
  734. list. 
  735.  
  736. 76. Distinguish between a parameter and an argument. 
  737. A parameter is a dummy name listed on the subprogram’s heading. An 
  738. argument is the data the calling program sends to the subprogram to 
  739. use. 
  740.  
  741. 77. Distinguish between a value parameter and a reference parameter. 
  742. The calling program sends a copy of the data to the subprogram if the 
  743. parameter is a value parameter. If the subprogram’s parameter is a 
  744. reference parameter, the calling program sends the address of the data. 
  745.  
  746. 78. Which three elements must be present in the definition of a record? 
  747. The record name, the names of the individual data items and their 
  748. respective data types. 
  749.  
  750. 79. Ada uses a range of index values to define an array, but VB.NET and 
  751. C++ specify the number of places in the array. Explain. 
  752. Ada lets the user explicitly define how the values in the array are to be 
  753. indexed; the number of items is determined from this range. VB.NET 
  754. and C++ specify the number of elements in the array, and accessing is 
  755. always from [0] through [number of elements - 1] 
  756.  
  757.  
  758. 80. Examine the following three array declarations: 
  759. type Index is range –1..10; — Ada 
  760. type Data_Array is array (Index) of Integer; 
  761.  
  762. Data : Data_Array; — Ada 
  763. Dim data(11) As Integer ‘ VB.NET 
  764. int data[11]; // C++ 
  765.  
  766. Are the arrays declared the same? Justify your answer. 
  767. The Ada array contains 12 slots, indexed from (-1)..(10).
  768. The VB.NET and C++ arrays contain 11 slots, indexed from (0)..(10)
  769. in VB.NET and [0]..[10] in C++.
  770.  
  771. 81. Distinguish between the definition of an object in the design phase and 
  772. in the implementation phase. 
  773. An object in the design phase is an entity that has meaning within the 
  774. context of the problem. An object in the implementation phase is an 
  775. instance of a class. 
  776.  
  777. 82. Distinguish between the definition of a class in the design phase and in 
  778. the implementation phase. 
  779. A class in the design phase is a description of a group of objects with 
  780. similar properties and behaviors. A class in the implementation phase 
  781. is a pattern for an object. 
  782.  
  783. Chapter 9 Exercises and Answers 
  784. =====================================================
  785.  
  786. For exercises 1–10, match the class of operation with the operation 
  787. described. 
  788.  
  789. A. Constructor: Creates a new instance of a container. 
  790. B. Transformer: Changes the contents of a container. 
  791. C. Iterator: Allows access to each item in a container one at a time. 
  792. D. Observer: Asks information about a container without changing it. 
  793. 1. Add into a container. 
  794. B 
  795.  
  796. 2. Create a new container. 
  797. A 
  798.  
  799. 3. How many objects are in the container? 
  800. D 
  801.  
  802. 4. Is the container empty? 
  803. D 
  804.  
  805. 5. Get the next item in the container. 
  806. C 
  807.  
  808. 6. Have we looked at all the items in the container? 
  809. D 
  810.  
  811. 7. Delete an item from the container. 
  812. B 
  813.  
  814. 8. Is the item in the container? 
  815. D 
  816.  
  817. 9. Set the container to empty. 
  818. B 
  819.  
  820. 10. Is the container full? 
  821. D 
  822.  
  823. For exercises 11–20, match the type of list implementation with the given 
  824. implementation step. 
  825.  
  826. A. Array-based 
  827. B. Linked 
  828. C. Either 
  829. D. Neither 
  830. 11. Initialize by setting length to zero. 
  831. A 
  832.  
  833. 12. In an unsorted container, put the item into the beginning of the list. 
  834. B 
  835.  
  836. 13. In a sorted container, put the item at the end of the list. 
  837. D 
  838.  
  839. 14. To insert in a sorted list, first find the appropriate position. 
  840. C 
  841.  
  842. 15. Initialize by setting pointer to null. 
  843. B 
  844.  
  845. 16. Get next item involves incrementing a counter. 
  846. A 
  847.  
  848. 17. Get next item involves moving a pointer. 
  849. B 
  850.  
  851. 18. more items involves comparing length to a counter. 
  852. A 
  853.  
  854. 19. more items involves comparing something to null. 
  855. B 
  856.  
  857. 20. Find the item involves searching the list. 
  858. C 
  859.  
  860. For Exercises 21–37, mark the answers true or false as follows: 
  861.  
  862. A. True 
  863. B. False 
  864. 21. A binary search cannot be applied to a linked list. 
  865. A 
  866.  
  867. 22. A linear search cannot be applied to an array-based list. 
  868. B 
  869.  
  870. 23. A binary search cannot be applied to an array-based list. 
  871. B 
  872.  
  873. 24. A binary search is always faster than a linear search. 
  874. B 
  875.  
  876. 25. A binary search cannot be applied to an unsorted list. 
  877. A 
  878.  
  879. 26. A stack exhibits LIFO behavior. 
  880. A 
  881.  
  882. 27. A queue exhibits FIFO behavior. 
  883. A 
  884.  
  885. 28. A stack and a queue are different versions of the same abstract data 
  886. type. 
  887. B 
  888.  
  889. 29. A binary search tree allows log2N searching in a linked structure. 
  890. A 
  891.  
  892. 30. In a graph, the vertices represent the objects being modeled. 
  893. A 
  894.  
  895. 31. The bubble sort algorithm involves finding the smallest item in the 
  896. unsorted portion of the array and swapping it with the current item. 
  897. B 
  898.  
  899. 32. The selection sort algorithm involves finding the smallest item in the 
  900. unsorted portion of the array and swapping it with the current item. 
  901. A 
  902.  
  903. 33. The bubble sort algorithm swaps every out-of-order pair it sees. 
  904. A 
  905.  
  906. 34. The Quicksort algorithm swaps every out-of-order pair encountered 
  907. from different ends of the array. 
  908. A 
  909.  
  910. 35. The Quicksort algorithm is always quick. 
  911. B 
  912.  
  913. 36. The shape of a binary search tree depends on the order in which the 
  914. items are inserted. 
  915. A 
  916.  
  917. 37. The edges in a graph represent relationships. 
  918. A 
  919.  
  920. Exercises 38–58 are problems or short-answer questions. 
  921.  
  922. 38. Abstract data types, data structures, and containers: 
  923. a. Define these terms 
  924. Abstract data types are data types whose properties (domains and
  925. operations) are specified independently of any particular implemen
  926. tation.
  927.  
  928. A data structure is the implementation of the composite data fields of an abstract data type.
  929. A container is an object whose role is to hold and manipulate other objects.
  930.  
  931. b. What do they have in common? 
  932. Each represents the concept of collections of data objects. 
  933.  
  934. c. What distinguishes each from the others? 
  935. Each represents a different level. An ADT is the logical view of the
  936. properties of a class of data. A data structure is the implementation
  937. level of this logical view. A container is the description given to all
  938. logical views of this type of object; it represents how an application
  939. program might view the ADT at a higher level.
  940.  
  941. 39. Name and describe the three views of data. 
  942. Application, logical, and implementation are the three views of data.
  943. The application is the view of the data within a particular problem.
  944. The logical is the view that sees the data as objects with similar prop
  945. erties and behaviors and specifies them at an abstract level. The imple
  946. mentation view is a specific representation of the data and the actions
  947. to manipulate them.
  948.  
  949. 40. Array-based implementation and linked implementation: 
  950. a. Define these terms. 
  951. An array-based implementation is one that uses an array to hold
  952. the data items. Each item is accessed by its place in the structure. A
  953. linked implementation is one that uses a structure made up of
  954. nodes in which the nodes are explicitly linked one to another.
  955.  
  956. b. What do they have in common? 
  957. They are both storage structures to hold collections of homoge
  958. neous items.
  959.  
  960. c. What distinguishes one from the other? 
  961. They are distinguished by how the items are stored. In the array-
  962. based implementation data items are stored in contiguous locations
  963. in memory and accessed by position. In a linked implementation
  964. data items are stored in nodes along with the information of where
  965. to find the next node in the structure.
  966.  
  967. 41. Draw the unsorted list containing the following strings: blue, black, 
  968. green, yellow, red, purple, white, and violet. 
  969. a. In an unsorted array-based list. 
  970. b. In a sorted array-based list. 
  971. c. In an unsorted linked list. 
  972. d. In a sorted linked list. 
  973. a. An unsorted array-based list. 
  974. 8 
  975.  
  976. blue 
  977. black 
  978. green 
  979. red 
  980. purple 
  981. white 
  982. violet 
  983. yellow 
  984. [0] 
  985. [1] 
  986. [2] 
  987. [3] 
  988. [4] 
  989. [5] 
  990. [6] 
  991. [7] 
  992. b. A sorted array-based list. 
  993. 8 
  994.  
  995. black 
  996. blue 
  997. green 
  998. red 
  999. violet 
  1000. white 
  1001. yellow 
  1002. purple 
  1003. [0] 
  1004. [1] 
  1005. [2] 
  1006. [3] 
  1007. [4] 
  1008. [5] 
  1009. [6] 
  1010. [7] 
  1011. c. An unsorted linked list. 
  1012. blue black green yellow 
  1013. red 
  1014. purple violetwhite 
  1015. 
  1016. d. A sorted linked list. 
  1017. blue black green redpurple 
  1018. violent yellowwhite 
  1019. 42. Give the meaning of the following expressions in an array-based 
  1020. implementation: 
  1021. a. Put item 
  1022. Put item means that given an index shift the items that follow 
  1023. down one slot in the array and store the item at the index position. 
  1024.  
  1025. b. Remove the item 
  1026. Remove the item means that given an index shift the items that 
  1027. follow up one slot in the array. 
  1028.  
  1029. c. Get next item 
  1030. Get next item means to increment the value used as an index and 
  1031. access that indexed position. 
  1032.  
  1033. d. more items 
  1034. More items means that the variable used as an index is less than 
  1035. length – 1. 
  1036.  
  1037. 43. Give the meaning of the following expressions in a linked implementation: 
  1038. a. Put item 
  1039. Get next item means given current insert a new node with item in 
  1040. the info part of the node between current and next(current). 
  1041.  
  1042. b. Remove the item 
  1043. Remove the item means given current remove the next(current). 
  1044.  
  1045. c. Get next item 
  1046. Get next item means to set current to next(current). 
  1047.  
  1048. d. more items 
  1049. More items means that current does not contain null. 
  1050.  
  1051. Questions 44–46 use the following list of values. 
  1052.  
  1053. length 
  1054. 11 
  1055. list 
  1056. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 
  1057. 23 41 66 20 2 90 9 34 19 40 99 
  1058.  
  1059. 44. Show the state of the list when current is first set equal to the fourth 
  1060. item in the selection sort. 
  1061. Array when current is first set to 4th item. 
  1062.  
  1063. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 
  1064. 2 9 19 20 23 90 41 34 66 40 99 
  1065.  
  1066. 45. Show the state of the list when current is first set equal to the fifth 
  1067. item in the bubble sort algorithm. 
  1068. Array when current is first set to 5th item. 
  1069.  
  1070. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 
  1071. 2 9 19 20 23 41 66 34 40 90 99 
  1072.  
  1073.  
  1074. 46. Show the state of the list when the first recursive call is made in 
  1075. Quicksort using list[0] as the split value. 
  1076. Array when first recursive call is made. 
  1077.  
  1078. [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 
  1079. 2 19 9 20 23 90 66 34 41 40 99 
  1080.  
  1081. Questions 47 and 48 use the following list of values. 
  1082.  
  1083. length [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 
  1084. 11 5 7 20 33 44 46 48 99 101 102 105 
  1085.  
  1086. 47. How many comparisons does it take using a sequential search to find 
  1087. the following values or determine that the item is not in the list? 
  1088. a. 4 
  1089. 11 
  1090.  
  1091. b. 44 
  1092. 5 
  1093.  
  1094. c. 45 
  1095. 11 
  1096.  
  1097. d. 105 
  1098. 11 
  1099.  
  1100. e. 106 
  1101. 11 
  1102.  
  1103. 48. How many comparisons does it take using a binary search to find the 
  1104. following values or determine that the item is not in the list? 
  1105. a. 4 
  1106. 4 
  1107.  
  1108. b. 44 
  1109. 4 
  1110.  
  1111. c. 45 
  1112. 4 
  1113.  
  1114. d. 105 
  1115. 4 
  1116.  
  1117. e. 106 
  1118. 4 
  1119.  
  1120. 49. Write the algorithm for Enque in an array-based implementation. 
  1121. There are several solutions. The easiest is to keep the front of the
  1122. queue always in the [0] position.
  1123. // rear is index of last element put on the structure
  1124. Increment rear
  1125. Set items[rear] to newItem
  1126.  
  1127. 50. Write the algorithm for Pop in a linked implementation. 
  1128. Set current to stack
  1129. Set outItem to info(current)
  1130. Remove item
  1131.  
  1132. 51. Write the algorithms for Deque in a linked implementation. 
  1133. Set current to front 
  1134. Set outItem to info(front) 
  1135. Remove item 
  1136.  
  1137. Exercises 52–57 use the following tree 
  1138.  
  1139. 52. Name the content of each of the leaf nodes. 
  1140. alex, christopher, john robert june, kit, nell, susy 
  1141.  
  1142. 53. List the contents of each node that has just a right child. 
  1143. al, chris, mari, sarah 
  1144.  
  1145. 54. List the contents of each node that has just a left child. 
  1146. There are none. 
  1147.  
  1148. 55. What is the height of the tree? 
  1149. 5 
  1150.  
  1151. 56. Name the content of the nodes that are the ancestors of the node 
  1152. containing kit. 
  1153. kate, lila, phil, john 
  1154.  
  1155. 57. How many descendents does the node containing jim have? 
  1156. 3 
  1157.  
  1158. 58. Draw the tree that results from inserting the following value in this 
  1159. order: 
  1160. 25 
  1161. 15 30 
  1162. 7 26 40 
  1163. 2 8 35 
  1164.  
  1165.  
  1166. Chapter 10 Exercises and Answers 
  1167. =================================================================
  1168.  
  1169. For Exercises 1–18, mark the answers true or false as follows: 
  1170.  
  1171. A. True 
  1172. B. False 
  1173. 1. An operating system is an example of application software. 
  1174. B 
  1175.  
  1176. 2. An operating system provides a basic user interface that allows the
  1177. user to use the computer.
  1178. A 
  1179.  
  1180. 3. A computer can have more than one operating system, but only one is
  1181. in control at any given time.
  1182. A 
  1183.  
  1184. 4. Multiprogramming is the technique of using multiple CPUs to run
  1185. programs.
  1186. B 
  1187.  
  1188. 5. In the 1960s and 70s, a human operator would organize similar
  1189. computer jobs into batches to be run.
  1190. A 
  1191.  
  1192. 6. Batch processing implies a high level of interaction between the user
  1193. and the program.
  1194. B 
  1195.  
  1196. 7. A timesharing system allows multiple users to interact with a
  1197. computer at the same time.
  1198. A 
  1199.  
  1200. 8. A dumb terminal is an I/O device that connects to a mainframe
  1201. computer.
  1202. A 
  1203.  
  1204. 9. A logical address specifies an actual location in main memory. 
  1205. B 
  1206.  
  1207. 10. An address in a single contiguous memory management system is 
  1208. made up of a page and an offset. 
  1209. B 
  1210.  
  1211. 11. In a fixed partition system, main memory is divided into several partitions of the same size. 
  1212. B 
  1213.  
  1214. 12. The bounds register contains the last address of a partition. 
  1215. B It contains the length of the partition. 
  1216.  
  1217. 13. The first page in a paged memory system is page 0. 
  1218. A 
  1219.  
  1220. 14. A process in the running state is currently being executed by the CPU. 
  1221. A 
  1222.  
  1223. 15. The process control block (PCB) is a data structure that stores all 
  1224. information about a process. 
  1225. A 
  1226.  
  1227. 16. CPU scheduling determines which programs are in memory. 
  1228. B 
  1229.  
  1230. 17. The first-come, first-served scheduling algorithm is probably optimal. 
  1231. B 
  1232.  
  1233. 18. A time slice is the amount of time each process is given before being 
  1234. preempted in a round-robin scheduler. 
  1235. A 
  1236.  
  1237. For Exercises 19–23, match the operating system with information about 
  1238. it. 
  1239.  
  1240. A. Mac OS 
  1241. B. UNIX 
  1242. C. Linux 
  1243. D. DOS 
  1244. E. Windows 
  1245. 19. Which is the operating system of choice for Apple Computers? 
  1246. A 
  1247.  
  1248. 20. Historically, which is the operating system of choice for serious 
  1249. programmers? 
  1250. B 
  1251.  
  1252. 21. Which is the PC version of UNIX? 
  1253. C 
  1254.  
  1255. 22. What is the Microsoft operating system family provided on PCs 
  1256. called? 
  1257. E 
  1258.  
  1259. 23. What is the original PC operating system called? 
  1260. D 
  1261.  
  1262. For Exercise 24–26, match the following software type with its definition. 
  1263.  
  1264. A. Systems software 
  1265. B. Operating system 
  1266. C. Application software 
  1267. 24. Programs that help us solve real-world problems. 
  1268. C 
  1269.  
  1270. 25. Programs that manage a computer system and interact with hardware. 
  1271. A 
  1272.  
  1273. 26. Programs that manage computer resources and provide interfaces for 
  1274. other programs 
  1275. B 
  1276.  
  1277. Exercises 27–72 are problems or short-answer questions. 
  1278.  
  1279. 27. Distinguish between application software and system software. 
  1280. Systems software are tools to help others write programs; they manage
  1281. a computer system and interact with hardware. Application software
  1282. are programs to solve specific problems.
  1283.  
  1284. 28. What is an operating system? 
  1285. An operating system is a piece of software that manages a computer’s
  1286. resources and provides an interface for system interaction.
  1287.  
  1288. 29. Explain the term multiprogramming. 
  1289. Multiprogramming is the technique of keeping multiple programs in
  1290. main memory at the same time, each competing for time on the CPU.
  1291.  
  1292. 30. The following terms relate to how the operating system manages 
  1293. multiprogramming. Describe the part each plays in this process. 
  1294. a. Process 
  1295. A process is a program in execution. 
  1296.  
  1297. b. Process management 
  1298. Process management is keeping track of necessary information for
  1299. active processes.
  1300.  
  1301. c. Memory management 
  1302. Memory management is keeping track of how and where programs 
  1303. are loaded into main memory. 
  1304.  
  1305. d. CPU scheduling 
  1306. CPU scheduling is determining which process in memory is given 
  1307. access to the CPU so that it may execute. 
  1308.  
  1309. 31. What constitutes a batch job? 
  1310. A batch job was made up of the program and the instructions 
  1311. regarding the system software and other resources needed to execute 
  1312. the job. 
  1313.  
  1314. 32. Describe the evolution of the concept of batch processing from the 
  1315. human operator in the 1960s and 1970s to the operating systems of 
  1316. today. 
  1317. Originally the instructions regarding the system software needed for a 
  1318. program were given to the human operator. Today the instructions are 
  1319. given directly to the computer through OS commands that are part of 
  1320. the file containing the program. Today, batch processing has come to 
  1321. mean a system in which programs and system resources are coordinated and 
  1322. executed without interaction between the user and the program. 
  1323.  
  1324. 33. Define timesharing. 
  1325. Timesharing is a technique by which CPU time is shared among 
  1326. multiple interactive users at the same times. 
  1327.  
  1328. 34. What is the relationship between multiprogramming and timesharing? 
  1329. Multiprogramming allows multiple processes to be active at once. 
  1330. Timesharing allows the multiple processes to be interactive ones. 
  1331.  
  1332. 35. Why do we say that users in a timesharing system have their own 
  1333. virtual machine? 
  1334. Users have the illusion of having the computer all to themselves. 
  1335.  
  1336. 36. In Chapter 7, we defined a virtual machine as a hypothetical machine 
  1337. designed to illustrate important features of a real machine. In this 
  1338. chapter, we define a virtual machine as the illusion created by a timesharing 
  1339. system that each user has a dedicated machine. Relate these two definitions. 
  1340. The illusion created in a timesharing situation is that the user owns a 
  1341. single hypothetical machine. The hypothetical machine illustrates the 
  1342. important features of the single machine the user needs. 
  1343.  
  1344.  
  1345. 37. How does the timesharing concept work? 
  1346. Each user is represented by a login process that runs on the main
  1347. frame. When the user runs a program, another process is created that
  1348. competes for CPU time with other processes. The rationale is that the
  1349. computer is so fast that it can handle multiple users without anyone
  1350. having to wait.
  1351.  
  1352. 38. What is a real-time system? 
  1353. A real-time system is a system in which the speed of an answer is
  1354. crucial.
  1355.  
  1356. 39. What is response time? 
  1357. Response time is how long it takes to get an answer. The expression
  1358. comes from the delay between receiving a stimulus (asking a question)
  1359. and producing a response (answering the question).
  1360.  
  1361. 40. What is the relationship between real-time systems and response time? 
  1362. Time is critical in many real-time situations, so the response time must
  1363. be kept to a minimum.
  1364.  
  1365. 41. In a multiprogramming environment, many processes may be active. 
  1366. What are the tasks that the operating system must accomplish to 
  1367. manage the memory requirements of active processes? 
  1368. The OS must keep track of where and how a program resides in
  1369. memory and convert logical program addresses into actual memory
  1370. addresses.
  1371.  
  1372. 42. Distinguish between logical addresses and physical addresses. 
  1373. A physical address is an actual address in the computer’s main
  1374. memory device. A logical address is an address relative to the
  1375. program. A logical address is sometimes called a relative address for
  1376. obvious reasons.
  1377.  
  1378. 43. What is address binding? 
  1379. Address binding is the mapping of a logical address into a physical
  1380. address.
  1381.  
  1382. 44. Name three memory-management techniques and describe the general 
  1383. approach taken in each. 
  1384. Single contiguous memory management: Only the OS and one applica
  1385. tion program are loaded into memory at the same time.
  1386. Static and dynamic partitions: More than one program is loaded into
  1387. memory with the OS at the same time. Each application program is
  1388. given its own partition of memory.
  1389. Paging: Main memory is divided into fixed-sized blocks called frames 
  1390. and processes are divided into fixed-sized blocks called pages. Any 
  1391. number of programs can be loaded with the OS, but a process does 
  1392. not necessarily have to be in contiguous memory and not all of a 
  1393. process need be in memory at the same time. 
  1394.  
  1395. 45. When is a logical address assigned to a variable? 
  1396. When the program is compiled. 
  1397.  
  1398. 46. When does address binding occur? 
  1399. When the program is loaded into memory. 
  1400.  
  1401. 47. How is memory divided in the single contiguous memory management 
  1402. approach? 
  1403. Memory is divided into two sections, one for the operating system and 
  1404. one for the application program. 
  1405.  
  1406. 48. When a program is compiled, where is it assumed that the program 
  1407. will be loaded into memory? That is, where are logical addresses 
  1408. assumed to begin? 
  1409. At location 0. 
  1410.  
  1411. 49. If, in a single contiguous memory management system, the program is 
  1412. loaded at address 30215, compute the physical addresses (in decimal) 
  1413. that correspond to the following logical addresses: 
  1414. a. 9223 
  1415. 39438 
  1416.  
  1417. b. 2302 
  1418. 32517 
  1419.  
  1420. c. 7044 
  1421. 37259 
  1422.  
  1423. 50. In a single contiguous memory management approach, if the logical 
  1424. address of a variable is L and the beginning of the application 
  1425. program is A, what is the formula for binding the logical address to 
  1426. the physical address? 
  1427. L + A 
  1428.  
  1429. 51. If, in a fixed-partition memory management system, the current value 
  1430. of the base register is 42993 and the current value of the bounds 
  1431. register is 2031, compute the physical addresses that correspond to the 
  1432. following logical addresses: 
  1433. a. 104 
  1434. 43097 
  1435.  
  1436. b. 1755 
  1437. 44748 
  1438.  
  1439. c. 3041 
  1440. Address out of bounds of partition. 
  1441.  
  1442. 52. If more than one partition is being used (either fixed or dynamic), 
  1443. what does the base register contain? 
  1444. The base register contains the beginning address of the current parti
  1445. tion.
  1446.  
  1447.  
  1448. 53. Why is the logical address compared to the bounds register before a 
  1449. physical address is calculated? 
  1450. The bounds register contains the length of the current partition. If the
  1451. logical address is greater than the bounds register, then the physical
  1452. address is not within the current partition.
  1453.  
  1454.  
  1455. 54. If, in a dynamic partition memory management system, the current 
  1456. value of the base register is 42993 and the current value of the bounds 
  1457. register is 2031, compute the physical addresses that correspond to the 
  1458. following logical addresses: 
  1459. a. 104 
  1460. 43097 
  1461.  
  1462. b. 1755 
  1463. 44748 
  1464.  
  1465. c. 3041 
  1466. Address out of bounds of partition. 
  1467.  
  1468. Exercises 55 and 56 use the following state of memory. 
  1469. Operating system 
  1470. Process 1 
  1471. Process 2 
  1472. Process 3 
  1473. Empty 60 blocks 
  1474. Empty 52 blocks 
  1475. Empty 100 blocks 
  1476. 
  1477. 55. If the partitions are fixed and a new job arrives requiring 52 blocks of 
  1478. main memory, show memory after using each of the following partition selection approaches: 
  1479. a. First fit 
  1480. b. Best fit 
  1481. c. Worst fit 
  1482. a. first fit 
  1483. Operating system 
  1484. Process 1 
  1485. Process 2 
  1486. Process 3 
  1487. New process 
  1488. Empty 52 blocks 
  1489. Empty 100 blocks 
  1490. b. best fit 
  1491. Operating system 
  1492. Process 1 
  1493. Process 2 
  1494. Process 3 
  1495. New process 
  1496. Empty 60 blocks 
  1497. Empty 100 blocks 
  1498. 
  1499.  
  1500. c. worst fit 
  1501. Operating system 
  1502. Process 1 
  1503. Process 2 
  1504. Process 3 
  1505. New process 
  1506. Empty 60 blocks 
  1507. Empty 52 blocks 
  1508.  
  1509. 56. If the partitions are dynamic and a new job arrives requiring 52 blocks 
  1510. of main memory, show memory after using each of the following 
  1511. partition selection approaches: 
  1512. a. First fit 
  1513. b. Best fit 
  1514. c. Worst fit 
  1515. a. first fit 
  1516. New process 
  1517. Empty 52 blocks 
  1518. Empty 100 blocks 
  1519. Empty 8 blocks 
  1520. Operating system 
  1521. Process 1 
  1522. Process 2 
  1523. Process 3 
  1524. 
  1525. b. best fit 
  1526. Empty 60 blocks 
  1527. Empty 100 blocks 
  1528. Operating system 
  1529. Process 1 
  1530. Process 2 
  1531. New process 
  1532. Process 3 
  1533. c. worst fit 
  1534. Empty 60 blocks 
  1535. Empty 52 blocks 
  1536. Empty 48blocks 
  1537. Operating system 
  1538. Process 1 
  1539. Process 1 
  1540. New process 
  1541. Process 3 
  1542. 57. If a logical address in a paged memory management system is <2, 
  1543. 133>, what do the values mean? 
  1544. This address means the 133 byte on page 2. 
  1545. Page Frame 
  1546.  
  1547. 0 5 
  1548. 1 2 
  1549. 2 7 
  1550. 3 3 
  1551.  
  1552.  
  1553. 58. If the frame size of 1024, what is the physical address associated with 
  1554. the logical address <2, 85>? 
  1555. 7253 
  1556.  
  1557. 59. If the frame size of 1024, what is the physical address associated with 
  1558. the logical address <3, 555>? 
  1559. 3627 
  1560.  
  1561. 60. If the frame size of 1024, what is the physical address associated with 
  1562. the logical address <3, 1555>? 
  1563. Illegal address. The offset is larger than the page size. 
  1564.  
  1565. 61. What is virtual memory and how does it apply to demand paging? 
  1566. Virtual memory is the illusion that memory is limitless and thus there 
  1567. is no limit on the size of a program. Demand paging is the technique 
  1568. where pages are brought into memory only when they are referenced 
  1569. (needed). Demand paging allows programs of any size, thus giving the 
  1570. illusion of infinite memory. 
  1571.  
  1572. 62. What are the conceptual stages through which a process moves while 
  1573. being managed by the operating system? 
  1574. new, ready, running, waiting, and terminated 
  1575.  
  1576. 63. Describe how a process might move through the various process 
  1577. states. Create specific reasons why this process moves from one state 
  1578. to another. 
  1579. A new process begins in the new state. When the process has no bars 
  1580. to its execution, it moves into the ready state. It waits in the ready 
  1581. state until it gets time in the running state. It runs for a while and 
  1582. issues a command for file input. The process is moved into the waiting 
  1583. state until the I/O has been completed, at which time it moves into the 
  1584. ready state to await another turn in the running state. Eventually it 
  1585. gets back to the CPU and runs until it needs access to a part of the 
  1586. program that is on secondary storage. It moves into the waiting state 
  1587. until the needed pages are brought in; then it moves back to the ready 
  1588. state. It gets its third shot at the CPU and finishes, and moves into the 
  1589. terminated state. 
  1590.  
  1591. 64. What is a process control block? 
  1592. A process control block (PCB) is a data structure that contains information about a process. A PCB is created for each new process. When 
  1593. a process moves from one state to another, its PCB is moved with it. 
  1594.  
  1595. 65. How is each conceptual stage represented in the operating system? 
  1596. Each conceptual stage is represented by a list of the PCBs in that stage. 
  1597.  
  1598. 66. What is a context switch? 
  1599. When a process is moved out of the CPU, the current contents of the 
  1600. registers including the program counter must be saved in the process’s 
  1601. PCB. When a new process moves into the CPU, the contents of the 
  1602. registers from this process’s PCB are restored. This process of saving 
  1603. and restoring registers is called a context switch. 
  1604.  
  1605. 67. Distinguish between preemptive scheduling and nonpreemptive scheduling. 
  1606. With nonpreemptive scheduling, once a process is in the running state 
  1607. it remains there until it voluntarily leaves. With preemptive scheduling, the OS can move a process from the running state to the waiting 
  1608. state or ready state. 
  1609.  
  1610. 68. Name and describe three CPU scheduling algorithms. 
  1611. First-come, first-served: The processes are moved into the running 
  1612.  
  1613. state in the order in which they arrive in the ready. 
  1614. Shortest job next: When the CPU is ready for anther job, the process 
  1615. in the ready state that takes the shortest time is moved into the 
  1616. running state. The estimated length of time that a process needs the 
  1617. CPU may or may not be accurate. 
  1618.  
  1619. Round robin: Each process stays in the running state for a predetermined amount of time, called a time slice. When a process’s time slice 
  1620. is over, it is moved back into the ready state, where it stays until it is 
  1621. its turn again for the CPU. 
  1622.  
  1623. Use the following table of processes and service time for Exercises 69 
  1624. through 72. 
  1625.  
  1626.  
  1627. Process 
  1628. p1 
  1629. p2 
  1630. p3 
  1631. p4 
  1632. p5 
  1633. Service time 
  1634. 120 
  1635. 60 
  1636. 180 
  1637. 50 
  1638. 300 
  1639.  
  1640. 69. Draw a Gantt chart that shows the completion times for each process 
  1641. using first-come, first-served CPU scheduling. 
  1642. p1 p2 p3 p4 p5 
  1643. 0 120 410 710180 360 
  1644. 70. Draw a Gantt chart that shows the completion times for each process 
  1645. using shortest job next CPU scheduling. 
  1646. 0 50 110 230 410 710 
  1647. p1p2 p3p4 p5 
  1648. 71. Draw a Gantt chart that shows the completion times for each process 
  1649. using round robin CPU scheduling with a time slice of 60. 
  1650. 0 60 120 180 230 290 350 410 470 530 590 650 710 
  1651. p1 p2 p3 p4 p5 p1 p3 p3p5 p5 p5 p5 
  1652. The answer is the same in all three partition selection approaches. 
  1653.  
  1654. 72. Distinguish between fixed partitions and dynamic partitions. 
  1655. The sizes of the partitions are fixed in a fixed partition scheme, 
  1656. although they are not necessarily the same size. In a dynamic partition 
  1657. scheme, the partitions are allocated as needed. 
  1658.  
  1659. Chapter 11 Exercises and Answers 
  1660. ==========================================================
  1661.  
  1662. For Exercises 1–15, mark the answers true or false as follows: 
  1663.  
  1664. A. True 
  1665. B. False 
  1666. 1. A text file stores binary data that is organized into groups of 8 or 16 
  1667. bits that are interpreted as characters. 
  1668. A 
  1669.  
  1670. 2. A program written in a high-level language is stored in a text file that 
  1671. is also called a source file. 
  1672. A 
  1673.  
  1674. 3. The type of a file determines what kinds of operations can be 
  1675. performed on it. 
  1676. A 
  1677.  
  1678. 4. The current file pointer indicates the end of a file. 
  1679. B 
  1680.  
  1681. 5. Sequential access and direct access take about the same amount of 
  1682. time to retrieve data. 
  1683. B 
  1684.  
  1685. 6. Some operating systems maintain a separate read pointer and write 
  1686. pointer for a file. 
  1687. A 
  1688.  
  1689. 7. Unix file permissions allow a group of users to access a file in various 
  1690. ways. 
  1691. A 
  1692.  
  1693. 8. In most operating systems, a directory is represented as a file. 
  1694. A 
  1695.  
  1696. 9. Two files in a directory system can have the same name if they are in 
  1697. different directories. 
  1698. A 
  1699.  
  1700. 10. A relative path is relative to the root of the directory hierarchy. 
  1701. B 
  1702.  
  1703. 11. An absolute path and a relative path will always be the same length. 
  1704. B 
  1705.  
  1706. 12. An operating system is responsible for managing the access to a disk 
  1707. drive. 
  1708. A 
  1709.  
  1710. 13. The seek time is the amount of time it takes for the heads of a disk to 
  1711. reach a particular cylinder. 
  1712. A 
  1713.  
  1714. 14. The shortest-seek-time-first disk-scheduling algorithm moves the 
  1715. heads the minimum amount it can to satisfy a pending request. 
  1716. A 
  1717.  
  1718. 15. The first-come, first-served disk-scheduling algorithm moves the heads 
  1719. the minimum amount it can to satisfy a pending request. 
  1720. B 
  1721.  
  1722.  
  1723. For Exercises 16–20, match the file extensions with the appropriate file. 
  1724.  
  1725. A. txt 
  1726. B. mp3, au, and wav 
  1727. C. gif, tiff, and jpg 
  1728. D. doc and wp3 
  1729. E. java, c, and cpp 
  1730. 16. Audio file 
  1731. B 
  1732.  
  1733. 17. Image file 
  1734. C 
  1735.  
  1736. 18. Text data file 
  1737. A 
  1738.  
  1739. 19. Program source file 
  1740. E 
  1741.  
  1742. 20. Word processing file 
  1743. D 
  1744.  
  1745. For Exercises 21–23 , match the symbol with its use. 
  1746.  
  1747. A. / 
  1748. B. \ 
  1749. C. .. 
  1750. 21. Symbol used to separate the names in a path in a Windows environment 
  1751. B 
  1752.  
  1753. 22. Symbol used to separate the names in a path in a UNIX environment 
  1754. A 
  1755.  
  1756. 23. Symbol used to represent the parent directory in a relative path name 
  1757. C 
  1758.  
  1759. Exercises 24 –57 are problems or short answer questions. 
  1760.  
  1761. 24. What is a file? 
  1762. A file is the smallest amount of information that can be written to
  1763. secondary memory. It is a named collection of data, used for organ
  1764. izing secondary memory.
  1765.  
  1766.  
  1767. 25. Distinguish between a file and a directory. 
  1768. A file is a named collection of data. A directory is a named collection 
  1769. of files. 
  1770.  
  1771. 26. Distinguish between a file and a file system. 
  1772. A file is a named collection of data. A file system is the operating 
  1773. system’s logical view of the files it manages. 
  1774.  
  1775. 27. Why is a file a generic concept and not a technical one? 
  1776. A file is just a named collection of bits (data) in storage. Because there 
  1777. are different operating systems, there are different technical views of a 
  1778. file. Because we are talking from the user’s view not the implementation view, the concept is generic. 
  1779.  
  1780. 28. Name and describe the two basic classifications of files. 
  1781. Text files: Files that contain text. Each byte is an ANSII character or 
  1782.  
  1783. each 2 types is a Unicode character.
  1784. Binary files: The bytes in a binary file do not necessarily contain char
  1785. acters. These files require a special interpretation.
  1786.  
  1787.  
  1788. 29. Why is the term binary file a misnomer? 
  1789. All files ultimately are just a collection of bits, so why call one file type 
  1790. “binary?” In a binary file, the bits are not interpreted at text. A binary 
  1791. file would just be a stream of uninterpreted bits unless there is an 
  1792. interpretation provided. If a binary file is printed without interpretation, it looks like garbage. 
  1793.  
  1794. 30. Distinguish between a file type and a file extension. 
  1795. A file type is a description of the information contained in the file. A 
  1796. file extension is a part of the file name that follows a dot and identifies 
  1797. the file type. 
  1798.  
  1799. 31. What would happen if you give the name myFile.jpg to a text file? 
  1800. It depends on what application program you use to open the file. If 
  1801. you use a program that expects an image file, you would get an error. 
  1802. If you use a program that expects a text file, there would be no 
  1803. problem. 
  1804.  
  1805. 32. How can an operating system make use of the file types that it recognizes? 
  1806. If you click on a file on your desktop and the OS recognizes the file 
  1807. type, then the appropriate application program can be called to open 
  1808. the file. If you are writing Java programs using an integrated environment, then the files saved in the IDE are tagged and clicking on a file 
  1809. automatically opens the file in the IDE. 
  1810.  
  1811. 33. How does an operating system keep track of secondary memory? 
  1812. The OS maintains a table indicating which blocks of memory are free.
  1813. The OS also maintains a table for each directory that contains infor
  1814. mation about the files in that directory.
  1815.  
  1816.  
  1817. 34. What does it mean to open and close a file? 
  1818. Operating systems keep a table of currently open files. The open oper
  1819. ation enters the file into this table and places the file pointer at the
  1820. beginning of the file. The close operation removes the file from the
  1821. table of open files.
  1822.  
  1823.  
  1824. 35. What does it mean to truncate a file? 
  1825. Truncating a file means that all the information on the file is erased
  1826. but the administrative entries remain in the file tables. Occasionally,
  1827. the truncate operation removes the information from the file pointer
  1828. to the end.
  1829.  
  1830.  
  1831. 36. Compare and contrast sequential and direct file access. 
  1832. Both sequential and direct file access find and access a record. In
  1833. sequential access the file pointer begins at the beginning of the file and
  1834. can only move in one direction. Thus sequential access is linear: The
  1835. only record that can be accessed is the first or the one immediately
  1836. following the last one accessed. In direct access the file pointer can be
  1837. moved to any specific record and the data accessed from that place.
  1838.  
  1839.  
  1840. 37. File access is independent of any physical medium. 
  1841. a. How could you implement sequential access on a disk? 
  1842. Sequential access always accesses the next record. You implement
  1843. sequential access on a disk by not giving the user an access
  1844. command that takes a record address as a parameter.
  1845.  
  1846.  
  1847. b. How could you implement direct access on a magnetic tape? 
  1848. Each record on a magnetic tape is conceptually numbered from the
  1849. first to the last. Keep a counter of which record was read last.
  1850. When a user gives an access command to read a specific record, if
  1851. the record number is beyond the last record read, then records are
  1852. read and skipped until the correct record is found. If the record
  1853. number comes before the last record read, the tape is rewound and
  1854. records are read and skipped until the correct record is found.
  1855.  
  1856.  
  1857. 38. What is a file protection mechanism? 
  1858. A file protection mechanism is one that an operating system imple
  1859. ments that ensures the only valid users can access a particular file.
  1860.  
  1861. 39. How does UNIX implement file protection? 
  1862. Unix implements file protection by associating with each file a 3x3 
  1863. table in which the rows are Owner, Group, and World and the 
  1864. columns are Read, Write/Delete, and Execute. The contents of each 
  1865. cell in the table are boolean values meaning yes and no. For example, 
  1866. a yes in the cell (Owner, Execute) means that the owner of the file can 
  1867. execute it. A no in the cell (World, Write/Delete) means that permission to write or delete a file is not granted to anyone that is not the 
  1868. owner of the file or within a specified group. (Group is a list of those 
  1869. considered part of the group.) 
  1870.  
  1871. 40. Given the following file permission, answer these questions. 
  1872. Read Write/Delete Execute 
  1873. Owner 
  1874. Group 
  1875. World 
  1876. Yes Yes Yes 
  1877. Yes Yes No 
  1878. Yes No No 
  1879. a. Who can read the file? 
  1880. Any one can read the file. 
  1881.  
  1882. b. Who can write or delete the file? 
  1883. The owner and members of the group can write or delete the file. 
  1884.  
  1885. c. Who can execute the file? 
  1886. Only the owner can execute the file. 
  1887.  
  1888. d. What do you know about the content of the file? 
  1889. Because the owner has permission to execute the file, it must 
  1890. contain an executable program. 
  1891.  
  1892. 41. What is the minimum amount of information a directory must contain 
  1893. about each file? 
  1894. A directory must contain the file name, the file type, the address on 
  1895. disk where the file is stored, the current size of the file, and permission 
  1896. information. 
  1897.  
  1898. 42. How do most operating systems represent a directory? 
  1899. As a file. 
  1900.  
  1901. 43. Answer the following questions about directories. 
  1902. a. A directory that contains another directory is called what? 
  1903. parent directory 
  1904.  
  1905. b. A directory contained within another directory is called what? 
  1906. subdirectory 
  1907.  
  1908. c. The directory that is not contained in any other directory is called
  1909. what?
  1910. root directory 
  1911.  
  1912. d. The structure showing the nested directory organization is called
  1913. what?
  1914. directory tree 
  1915.  
  1916. e. Relate the structure in (d) to the binary tree data structure exam
  1917. ined in Chapter 9.
  1918. A directory tree and a binary tree are both hierarchical structures in
  1919. which there is only one way to reach any subtree. The root direc
  1920. tory is equivalent to the root of the binary tree. In a binary tree,
  1921. each node can have none, one, or two child nodes. In a directory
  1922. tree, each node can have any number of subdirectories.
  1923.  
  1924.  
  1925. 44. What is the directory called in which you are working at any one 
  1926. moment? 
  1927. working directory 
  1928.  
  1929. 45. What is a path? 
  1930. A path is a text string that specifies the location of a file or subdirec
  1931. tory.
  1932.  
  1933.  
  1934. 46. Distinguish between an absolute path and a relative path. 
  1935. An absolute path is a path that begins at the root directory and
  1936. includes all successive subdirectories. A relative path is a path that
  1937. begins at the current working directory and includes all successive
  1938. subdirectories.
  1939.  
  1940.  
  1941. 47. Show the absolute path to each of the following files or directories 
  1942. using the directory tree shown in Figure 11.4: 
  1943. a. QTEffects.qtx 
  1944. C:\WINDOWS\System\QuickTime\QTEffects.qtx 
  1945.  
  1946. b. brooks.mp3 
  1947. C:\My Documents\downloads\brooks.mp3 
  1948.  
  1949. c. Program Files 
  1950. C:\Program Files 
  1951.  
  1952. d. 3dMaze.scr 
  1953. C:\WINDOWS\System\3dMaze.scr 
  1954.  
  1955. e. Powerpnt.exe 
  1956. C:\Program Files\MS Office\Powerpnt.exe 
  1957.  
  1958. 48. Show the absolute path to each of the following files or directories 
  1959. using the directory tree shown in Figure 11.5: 
  1960. a. tar 
  1961. /bin/tar 
  1962.  
  1963. b. access.old 
  1964. /etc/mail/access.old 
  1965.  
  1966. c. named.conf 
  1967. /etc/named.conf 
  1968.  
  1969. d. smith 
  1970. /home/smith 
  1971. e. week3.txt 
  1972. /home/smith/reports/week1.txt 
  1973. f. printall 
  1974. /home/jones/utilities/printall 
  1975.  
  1976. 49. Assuming the current working directory is C:\WINDOWS\System, give 
  1977. the relative path name to the following files or directories using the 
  1978. directory tree shown in Figure 11.4: 
  1979. a. QTImage.qtx 
  1980. QuickTime\QTImage.qtx 
  1981.  
  1982. b. calc.exe 
  1983. ..\calc.exe 
  1984.  
  1985. c. letters 
  1986. ..\..\My Documents\letters 
  1987.  
  1988. d. proj3.java 
  1989. ..\..\My Documents\csc101\proj3.java 
  1990.  
  1991. e. adobep4.hlp 
  1992. adobep4.hlp 
  1993.  
  1994. f. WinWord.exe 
  1995. ..\..\Program Files\MS Office\Winword.exe 
  1996.  
  1997. 50. Show the relative path to each of the following files or directories 
  1998. using the directory tree shown in Figure 11.5. 
  1999. a. localtime when working directory is the root directory 
  2000. /etc/localtime 
  2001.  
  2002. b. localtime when the working directory is etc 
  2003. localtime 
  2004.  
  2005. c. printall when the working directory is utilities 
  2006. printall 
  2007.  
  2008. d. week1.txt when the working directory is man2 
  2009. ../reports/week1.txt 
  2010.  
  2011. 51. What is the worst bottleneck in a computer system? 
  2012. Transferring data to and from secondary memory is the worst bottle
  2013. neck.
  2014.  
  2015.  
  2016. 52. Why is disk scheduling concerned more with cylinders than with 
  2017. tracks and sectors? 
  2018. Seek time (the time to find the right cylinder) is more time consuming
  2019. than locating which track or which sector, so seek time is the time to
  2020. minimize.
  2021.  
  2022.  
  2023. 53. Name and describe three disk-scheduling algorithms. 
  2024. First-come, first-serve (FCSC): The requests are handled in the order in 
  2025.  
  2026. which they are generated.
  2027. Shortest seek time first (SSTF): The request closest to the read/write
  2028. heads is handled next.
  2029.  
  2030.  
  2031. SCAN: The read/write heads move back and forth handling the closest
  2032. in the direction in which they are moving.
  2033.  
  2034.  
  2035. Use the following list of cylinder requests in Exercises 54–56. They are 
  2036. listed in the order in which they were received. 
  2037.  
  2038. 40, 12, 22, 66, 67, 33, 80 
  2039.  
  2040. 54. List the order in which these requests are handled if the FCFS algorithm is used. Assume that the disk is positioned at cylinder 50. 
  2041. 40, 12, 22, 66, 67, 33, 80 
  2042.  
  2043. 55. List the order in which these requests are handled if the SSTF algorithm is used. Assume that the disk is positioned at cylinder 50. 
  2044. 40, 33, 22, 12, 66, 67, 80 
  2045.  
  2046. 56. List the order in which these requests are handled if the SCAN algorithm is used. Assume that the disk is positioned at cylinder 50 and the 
  2047. read/write heads are moving toward the higher cylinder numbers. 
  2048. 66, 67, 80, 40, 33, 22, 12 
  2049.  
  2050. 57. Explain the concept of starvation. 
  2051. In the SSTF algorithm, it is possible for some requests never to be serv
  2052. iced because requests closer to the read/write heads keep being issued.
Viewed 13989 times, submitted by Guest.