University of Otago COSC243 Computer Science Exam 2019 PDF

# UNIVERSITY OF OTAGO EXAMINATIONS 2019 ## COMPUTER SCIENCE ### COSC243 ### COMPUTER ARCHITECTURE & OPERATING SYSTEMS #### Semester One #### (TIME ALLOWED: THREE HOURS) - This examination comprises 14 pages. - Candidates should answer questions as follows: - Candidates must answer all question...

# UNIVERSITY OF OTAGO EXAMINATIONS 2019 ## COMPUTER SCIENCE ### COSC243 ### COMPUTER ARCHITECTURE & OPERATING SYSTEMS #### Semester One #### (TIME ALLOWED: THREE HOURS) - This examination comprises 14 pages. - Candidates should answer questions as follows: - Candidates must answer all questions. - Questions are worth various marks and are shown thus: (5) - The total number of marks for this exam is 100. ## Instructions - Answers must be written in the boxes or lines provided on this examination paper. - If you run out of space, use the answer book. - The following material is provided: Nil. - Use of calculators: - Calculator models as specified by the University of Otago in List A of approved calculators (scientific calculators): Casio FX82, Casio FX100; Sharp EL531; Casio FX570; Casio FX95. - Candidates are permitted copies of: Nil. ## Other Instructions: - Please write your Student ID at the top of each page in the space provided. - At the end of the exam, hand in your completed paper attached to the green attendance receipt and your answer book (if you have used one). ## 1. Logic - Name the gates and complete the truth tables. - **(a)** This gate is called: - The truth table for this gate is: | A | B | A op B | | - | - | - | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 1 | - **(b)** This gate is called: - The truth table for this gate is: | A | B | A op B | | - | - | - | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 0 | - **(c)** This gate is called: - The truth table for this gate is: | A | B | A op B | | - | - | - | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | - **(d)** This gate is called: - The truth table for this gate is: | A | B | A op B | | - | - | - | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 | - **(e)** This gate is called: - The truth table for this gate is: | A | B | A op B | | - | - | - | | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 0 | | 1 | 1 | 1 | ## 2. Circuits - The game Centipede is remarkably similar to Snakes and Ladders, except that it uses a 2-sided coin (with sides labelled 0 and 1) rather than dice. You start at square 0 and each turn you flip the coin and move either one square (on a roll of 0) or two squares (on a roll of 1). The object is to get to square 8 without overshooting (if you roll a 1 from square 7 you stay on square 7). Rather than having snakes and ladders, it only uses centipedes: If you land on the head of a centipede then you are transported to the tail of the centipede. The game is a kind of solitaire the objective is to get from square 0 to square 8 in as few moves as possible. The game board looks like this: <br> - **(a)** Complete the state transition diagram for the given board. <br> - **(b)** A 3-bit parity generator adds an extra bit to the data such that the number of 1s output is always odd. There are three inputs (A, B, C) and one output bit (P). Complete the truth table for this function. <br> | Integer | A | B | C | P | | -------- | - | - | - | - | | 0 | 0 | 0 | 0 | 1 | | 1 | 0 | 0 | 1 | 0 | | 2 | 0 | 1 | 0 | 0 | | 3 | 0 | 1 | 1 | 1 | | 4 | 1 | 0 | 0 | 0 | | 5 | 1 | 0 | 1 | 1 | | 6 | 1 | 1 | 0 | 1 | | 7 | 1 | 1 | 1 | 0 | <br> - **(c)** Without simplifying, write the Boolean equation for P in sum of products form. ## 3. Computer Architecture - **(a)** Name the three busses the CPU uses to communicate with the memory. - **(b)** Name three functions of the Control Unit. - **(c)** Name the three key concepts of the von Neumann Architecture. - **(d)** Which architecture is designed to have one instruction per cycle and register to register operations? - **(e)** Name the 4 cycles of a CPU operation. ## 4. Peripherals - **(a)** Explain how to encode a 0 using Frequency Modulation (FM) encoding. - **(b)** Explain how to encode a 1 using Frequency Modulation (FM) encoding. - **(c)** Explain how to encode a 0 using Modified Frequency Modulation (MFM) encoding. - **(d)** Explain how to encode a 1 using Modified Frequency Modulation (MFM) encoding. - **(e)** What is the name of the concentric rings on a hard disk platter? - **(f)** What is the name of a wedge of one of those concentric rings? - **(g)** Name the part of the computer that copies data from (or to) a peripheral device freeing up the CPU to perform other actions while the transfer occurs. - **(h)** Name the alternative method, where the CPU performs the copy of data from (or to) a peripheral device by running a loop that checks a status register before each word is copied. - **(i)** Give one disadvantage of port mapped I/O. - **(j)** Give one disadvantage of memory mapped I/O. ## 5. Assembly Language - The state and memory of the 6502 computer is represented by this diagram: | Register | Value | Memory Address | Memory Value | | -------- | ----- | --------------- | -------------- | | A | $11 | $0011 | $88 | | X | $01 | $0010 | $00 | | Y | $33 | $000F | $OD | | PC | $F000 | $000E | $55 | | S | $01E0 | $000D | $44 | | Flag (P) | NV1 BDI ZC | Value | | -------- | -------- | ----- | | | 00100011 | | - **(a)** Which addressing mode does the LDA #$0D instruction use? - **(b)** What is the value of A after the CPU executes LDA #$0D? - **(c)** Which addressing mode does the LDY $0D instruction use? - **(d)** What is the value of Y after the CPU executes LDY $0D? - **(e)** Which addressing mode does the LDY $(000F), X instruction use? - **(f)** What is the value of Y after the CPU executes LDY $(000F), X? - **(g)** Explain when you would do a CLC before an ADC, and when you would not. ## 6. Fill the following blanks with proper concepts. - **(a)** An Operating System (OS) manages _[blank]_. - **(b)** Usually the CPU can execute code from two spaces. In the _[blank]_ space, the CPU _[blank]_ has the privilege to access any special registers and hardware devices. In the _[blank]_ space, the CPU _[blank]_ cannot access those special registers and hardware devices directly unless permitted or helped by the OS. - **(c)** Processes issue requests to the OS kernel by making _[blank]_. - **(d)** In a process memory layout, it has three sections for _[blank]_, _[blank]_, and _[blank]_ respectively. - **(e)** The OS manages a process via a data structure called _[blank]_. - **(f)** A thread shares the _[blank]_ section and the _[blank]_ section with the other threads of the same process. - **(g)** If you want to terminate a process, you can send a _[blank]_ to the process. - **(h)** A terminated child process with a live parent process that is not WAITING for the child is called _[blank]_ process. - **(i)** When multiple processes/threads are accessing the same data/memory location at the same time and at least one of them is modifying the data, this situation is called _[blank]_. - **(j)** A high-level language construct to make synchronisation easier for programmers is called _[blank]_. - **(k)** The necessary conditions for deadlocks are _[blank]_, _[blank]_, and _[blank]_. - **(l)** The unit in CPU that is responsible for the translation between logical addresses and physical addresses is called _[blank]_. - **(m)** A situation in the memory system where there is enough memory in total but no individual free contiguous memory block is big enough for use is called _[blank]_. - **(n)** If a process wishes to launch another program, the standard procedure for doing this on a typical UNIX system is using two system calls: _[blank]_ and _[blank]_. - **(o)** The cache of page table entries is a special set of associative registers for speeding up the search of page tables. This cache in CPU is called _[blank]_. - **(p)** If a page is not accessible, its entry in the page table is set invalid. Accessing such a page will result a trap in CPU. Such a trap is often called _[blank]_. - **(q)** When you want to access a file in a file system via programming, you can use system calls like _[blank]_ etc to retrieve and modify the data of the file. - **(r)** To speed up I/O processing, CPU can delegate I/O tasks to a special-purpose processor which can move data from the device memory to the main memory (RAM). This method is called _[blank]_. - **(s)** A device _[blank]_ is a kernel module that understands the hardware of the device and translates system calls into device-specific commands. ## 7. You are programming on a system that provides semaphores for process synchronization. - The system calls provided are init(s, initialValue), wait(s), and signal(s). The operating system uses a wait queue internally for the wait(s) call. Add these system calls to the following pseudo-code so that the counter is only accessed by one process at a time. Make sure you get the initialValue correct when init(s, initialValue) is called so that mutual exclusion is guaranteed by the semaphore. ```c // setup. This is guaranteed to be run exactly once, before anything else. void setup() { // YOUR CODE HERE } int counter = 0; void incrementCounter() { // YOUR CODE HERE counter = counter + 1; } void decrementCounter() { // YOUR CODE HERE counter = counter - 1; } ``` ## 8. Describe the function of the Compare-And-Swap instruction, CAS(o, a, n), which is used to implement spin locks and semaphores in OS. ## 9. Assume a tiny computer system using binary has 32 bytes physical memory. It has a paging system shown below, which has a page size of 4 bytes. A process P has a logical address space of 16 bytes. It has a page table (blank at the moment) as below. According to the page table, we find the following mappings between the logical addresses and the physical addresses (all in binary): logical address 0010 mapped to physical address 01010, logical address 1001 mapped to physical address 11101, logical address 0111 mapped to physical address 10111, and logical address 1110 mapped to physical address 11010. Figure out the content of the page table and fill the blank entries in the table below. Note you should fill the table with page and frame numbers in binary. | Logical address | Physical address | | | --------------- | --------------- | ---- | | | | F0 | | | | F1 | | | | F2 | | | | F3 | | | | F4 | | | | F5 | | | | F6 | **CPU** | address | P off | f off | | -------- | ----- | ----- | | | | | | | | | | | | | **Page table** | page | frame | | ---- | ----- | | | | | | | | | | | | | **memory** ## 10. Consider the following reference string: 27, 14, 20, 30, 27, 14, 60, 39, 27, 14, 21, 39 Assume a memory of four physical frames, and all entries of the page table are initially empty. How many page faults would result from this sequence of references - **(a)** using a first-in-first-out (FIFO) page replacement algorithm? - **(b)** using a least-recently-used (LRU) page replacement algorithm? ## 11. Suppose a file system uses indexed allocation, i.e. inode, for retrieving the data blocks of a file. Assuming that the inode has 12 direct pointers and one indirect pointer to an index data block which contains 1024 pointers and that the size of each data block in the file system is 4096 bytes, what is the largest possible file that can be stored in the file system? Note that you only need to show how you calculate the result but the final resulting number is not required. ## 12. Consider a disk with 100 tracks numbered 0-99, whose read-write head has just completed reads at tracks 20 and 80 (in that order). The queue of outstanding track requests is as shown below: 18, 76, 50, 85, 95, 10, 25, 38 In what sequence will these requests be served - **(a)** under shortest-seek-time-first (SSTF) disk scheduling? - **(b)** under SCAN disk scheduling? ## COSC243 - PLEASE DO NOT TURN OVER YOUR EXAMINATION PAPER UNTIL INSTRUCTED TO DO SO | | | | ----------- | ----- | | TOTAL | | | Q1 | | | Q2 | | | Q3 | | | Q4 | | | Q5 | | | Q6 | | | Q7 | | | Q8 | | | Q9 | | | Q10 | | | Q11 | | | Q12 | |