CS 2200 Exam Study Guide Listed below are questions from past final exams. THERE IS NO GUARANTEE THAT THIS LIST IS ANY KIND OF INDICATOR OF EXACTLY WHAT WILL BE ON THE FINAL. In other words, there might be more problems requiring calculations, etc. Also, if you see a question that covers something that you have never seen don't worry about it. [I/O] Q. A disk has 20 surfaces (i.e. 10 double sided platters). Each surface has 1000 tracks. Each track has 128 sectors. Each sector can hold 64 bytes. The disk space allocation policy allocates an integral number of contiguous cylinders to each file, How many bytes are contained in one cylinder? How many cylinders are needed to accommodate a 5-Megabyte file on the disk? How much space is wasted in allocating this 5-Megabyte file? [General] Q. Is a megabyte exactly 1 million bytes? ___ Yes ___ No ___ I'm not sure? ___ I'm changing my major [I/O] Q. What is the difference between program controlled I/O and DMA? [I/O] Q. A disk has the following configuration: The disk has 310 MB Track size: 4096 bytes Sector Size: 64 bytes Mr. Gill Bates a programmer at Macrosoftware has 96 objects each being 50 bytes in size. He decides to save each object as an individual file. How many bytes (in total) are actually written to disk? [I/O] Q. Describe in detail the sequence of operations involved in a DMA data transfer. [I/O] Q. What are the mechanical things that must happen before a disk drive can read data. ___ DMA transfer request must be initiated by processor ___ Heads must be positioned on correct track ___ Thread scheduler must block on I/O call ___ Disk must rotate so that desired sector is under head [I/O] Q. A disk drive has 3 double-sided platters. The drive has 300 cylinders. How many tracks are there? ___ 600 ___ 900 ___ 1800 ___ 3600 [I/O] Q. While a disk unit is performing a DMA transfer what device keeps the processor from having to steal bus cycles? ___ Cache consistency protocol ___ TCP/IP stack ___ Cache ___ Club anti-theft device [I/O] Q. A bus might contain what three kinds of wires or lines? ___ Twisted pair ___ Data ___ Multi-mode ___ Full metal jacket ___ Control ___ Phaser ___ Address [I/O] Q. What is typically the fastest? ___ Program controlled I/O ___ DMA ___ Custom I/O Processor [Threads] Q. Select all choices that apply regarding threads created in the same address space. ___ they share code ___ they share global data ___ they share the stack ___ they share the heap [Threads} Q. From the following sentences regarding threads, select the ones that are True. ___ An operating system that provides no support for threads will block the entire process if one of the (user level) threads in that process makes a blocking system call. ___ In pthreads, a thread that does a pthread_cond_wait will always block. ___ In pthreads, a thread that does a pthread_mutex_lock will always block. ___ In Solaris, all user level threads in the same process compete equally for CPU resources. ___ All the threads within a single process in Solaris share the same page table. [I/O] Q. List two advantages of buses ___ Cheap ___ Throughput bottleneck ___ Flexible ___ Yellow ___ CDSMA ___ Congestion resistant [Networks] Q. How does a device on the Ethernet know that there is a collision? ___ Sound collision warnings ___ Lookout ___ Collision avoidance radar ___ Listening {I/O] Q. What is the normal objective of a disk scheduling algorithm? ___ Minimize rotational latency ___ Control head acceleration ___ Maximize skew ratio ___ Minimize head movement [Distributed Computing] Q. What are the two schemes used to connect nodes on a multiprocessor? ___ PB & J ___ Bus ___ Vampire taps ___ Network ___ Net worth ___ Net BIOS ___ NetBUI ___ Munder NetNet [Distributed Computing] Q. Does snooping work with a network connected computer to keep caches consistent? ___ Yes ___ No [Networks] Q. The use of checksum in a packet is intended to address the following sources of unreliability in networks ___ corrupted or mangled data packets ___ out of order packet arrival ___ loss of packets ___ spurious packets injected into the network [Threads] Q. What is the big advantage of kernel threads? ___ Allow for non-blocking upcalls to TCP/IP ___ Allow O/S to schedule different threads on different processors ___ Abstraction of user level threads into LWP's [Threads] Q. Why use a "while" loop around a pthread_cond_wait() call? ___ Allow us to bypass wait when not necessary ___ Clear consistent programming style ___ Insures that required resource is still available [Threads] Q. With pthreads, do you have any control over thread scheduling? ___ Yes ___ No ___ Only with Solaris V ___ Only with Red Hat Linux 3.6 [Distributed Computing] Q. Select all statements that are True with respect to the remote procedure call mechanism ___ The parameter passing mechanism that is usually allowed is value/result. ___ It guarantees that the call will be executed at least once. ___ It is most efficient to implement without transport layer level ACKS. ___ It blocks the caller until the result comes back from the call. ___ It requires a nameserver [Networks] Q. There is an old network saying: Bandwidth problems can be cured with money. Latency problems are harder because the speed of light is fixed-you can't bribe ____________. ___ Your TA ___ Your instructor ___ God ___ Jim Greenlee [Networks] Q. How does the receiver of a packet verify that the packet arrived correctly, that is without error? (Check all that apply) ___ Parity checking ___ Checksum ___ Handwaving ___ Bit count [Networks *. What allows multiple devices on a network to talk to one another simultaneously? (Check all that apply) ___ Token ring ___ Shared Media ___ Switched Media ___ Virtual LAN's ___ NIC ___ Repeater [Networks] Q. In a token ring network there are typically how many tokens? (Check all that apply) ___ 1 for the sender ___ 1 for the receiver ___ 1 for the bus arbiter ___ 1 for each bridge [Networks] Q. What technique is typically used today to locate a desired service? (Check all that apply) ___ Load time binding ___ IMP Router Tables ___ Domain Name Servers ___ Broadcast Service Request (BSR) [Networks] Q. What are network protocols used for? (Check all that apply) ___ Deal with sources of unreliability ___ Shielding from RF interference ___ ISP Loading ___ Polling [Networks] Q. How do we deal with out of order delivery? (Check all that apply) ___ Timer ___ Attach sequnce number to packet ___ Maintain counter ___ Sliding window ___ Session ID [Networks] Q. How do we deal with Duplicate packets? (Check all that apply) ___ Timer ___ Attach sequnce number to packet ___ Maintain counter ___ Sliding window ___ Session ID [Networks] Q. How do we deal with Lost packets? (Check all that apply) ___ Timer ___ Attach sequnce number to packet ___ Maintain counter ___ Sliding window ___ Session ID [Networks] Q. How do we deal with flow control i.e. Having to wait a long time for acks. (Check all that apply) ___ Timer ___ Attach sequnce number to packet ___ Maintain counter ___ Sliding window ___ Session ID [Distributed Computing] Q. RPC is modeled after (Check all that apply) ___ Circuit switching ___ Stub marshalling ___ Procedural abstraction ___ CSMA/CD [Distributed Computing] Q. Telnet and FTP are examples of services found on a: ___ Network Operating System ___ Distributed OS [Networks] Q. Rank in order of typical distance between nodes (closest to farthest apart) ___ LAN ___ MPP ___ WAN [Networks] Q. What does a sliding window do? (Check all that apply) ___ Allow transmission of multiple packets before receiving an ACK ___ Provide a mechanism for responding to congestion ___ Provide more flexibility when defenestrating ___ Increase performance [Distributed Computing] Q. Where are massively parallel processors typically connected? ___ Memory Bus ___ I/O Bus [Distributed Computing] Q. Where are LAN's and WAN's typically connected? ___ Memory Bus ___ I/O Bus [Networks] Q. What can we do to reduce congestion in a network? (Check all that apply) ___ Log off ISP's ___ Throw away packets ___ Tune bandwidth ___ Pin processors [Networks] Q. Mark all that understand IP addresses ___ Repeaters ___ Bridges ___ Routers ___ Dan Colestock [Networks] *. What happens when you take that little resistor off the end of the ethernet coax cable? (Check all that apply) ___ Refraction ___ Reflection ___ Rarification ___ Reduction ___ Resistance [Distributed Computing] Q. What semantics are used by RPC? (Check all that apply) ___ Only once ___ At least once ___ At most once ___ One ounce [Networks] Q. Here are the 5 layers of the TCP/IP protocol Layer 1: Physical Layer 2: Network Interface Layer 3: Internet Layer 4: Transport Layer 5: Application For the item below specify which layer is responsible ___ Specifies how one application uses an internet ___ Specify forwarding mechanisms used by routers ___ Organize data into frames ___ Specifies how to ensure reliable transfer ___ How to transmit over network ___ Basic network hardware [You should just know this...forever] Q. Write a function in C that will swap two integers. The call will look like this: int a = 10; int b = 20; /* Call to swap occurs here */ printf("%d %d\n", a, b); ----------------------------------------------------------- Output: 20 10 ----------------------------------------------------------- Write the function here: [Distributed Computing] Q. True or False: Synchronization is concerned with ensuring that operations being performed concurrently by different entities are performed in a proper order A. True B. False [Networks] Q. Which of the following are used in modern communication networks (circle all that apply): A. Geo-synchronous satellites B. Low earth orbit satellite arrays C. Fiber optic cable D. Cold fusion [Networks] Q. Which of the following is a function implemented by a transport level protocol such as TCP (circle all that apply): A. Ensuring reliable delivery of data B. Representing a logic '1' as a high voltage, and a '0' as a low voltage C. Framing D. Routing data through the network [Networks] Q. True or False. Sliding windows provide a means to increase throughput over networks with long end-to-end latency A. True B. False [Networks] Q. True of False. A basic problem addressed by Internet addressing schemes is encoding network and host Ids into a fixed number of bits. A. True B. False [Networks] Q. Which of the following are valid reasons for creating layered network protocols (circle all that apply): A. They provide a useful alternative to TCP/IP B. They greatly facilitate the interconnection of heterogeneous computer networks to create systems such as the Internet C. They provide a means to create abstractions to help manage the complexity of communication networks D. They are necessary to maximize the performance of a communication network [Networks] Q. Naming is a basic problem in client server systems. Solution approaches to attacking this problem include (circle all that apply): A. Name server to map names to port numbers. B. Sockets C. Conventions are used to define well-known names D. IP addresses [Mutex] Q. Consider the program below that uses the test and set (TandS) primitive. TandS(L) operates on the Boolean variable L; it returns the value stored in L just prior to when the primitive is invoked, and sets L to true, all as one atomic (indivisible) operation. The program below assumes there are N threads, numbered 0 … N-1 that can access a critical section. Boolean waiting[N]; /* N element array */ Boolean L, Key; int i, j; /* code executed by process i to access a critical section */ waiting[i] = TRUE; Key = TRUE; while (waiting[i] && key) key = TandS (L); waiting[i] = FALSE; < access critical section > j = (i+1)%N; while (j != i) && !waiting[j]) j = (j+1) % N; if (i == j) lock = FALSE; /* STATEMENT 1 */ else waiting[j] = FALSE; (a) Explain the situation where STATEMENT 1 shown above will execute and set lock to FALSE. (b) Explain the purpose of the array "waiting" in the above code, i.e., what problem does it solve? [Virtual Memory] Q. If you were writing the code which decided which page to swap out during a page fault and you were using an operating system that allowed swapping out OS code...What would be the worst choice for a page to swap out? [I/O] Q. A disk drive has 2 platters (4 surfaces). There are 128 tracks with 64 sectors per track. Each sector contains 256 bytes. How many bytes per cylinder? [I/O] Q. Assume we have a mutex variable (critSecLock) and a condition variable (resAvSig) declared and initialized. Consider these code snippets: /* Snippet 1 */ pthread_mutex_lock(critSecLock); ResourceAvailable = false; pthread_mutex_unlock(critSecLock); /* Critical section */ ... /* Snippet 2 */ pthread_mutex_lock(critSecLock); if(!ResourceAvailable) { pthread_cond_wait(resAvSig, critSecLock); } ResourceAvailable = false; pthread_mutex_unlock(critSecLock); /* Now in critical section */ ... /* Snippet 3 */ pthread_cond_lock(critSecLock); while(!ResourceAvailable) { pthread_cond_wait(resAvSig, critSecLock); } ResourceAvailable = false; pthread_mutex_unlock(critSecLock); /* Now in critical section */ ... You should know that Snippet 3 is preferred but why? What's wrong with Snippet 1? What's wrong with Snippet 2? Why don't we worry in Snippet 3 about the following scenario: 1. The while checks and finds that the resource is not available 2. We get context switched out 3. Another thread changes the value of ResourceAvailable to true. 4. We get context switched back in 5. We wait and never get a signal because we are actually supposed to have the resource and no one ever sends us a signal. [Distributed Computing] Q. We discussed multiprocessor cache coherency protocols where a block that was marked shared would get marked exclusive upon a write and at the same time other caches would be told to invalidate their copy. Why didn't we just tell the other caches the new value and keep the block as shared? (Mark all that are correct.) ___ a.) Would require an extra bus cycle ___ b.) Would be inefficient if our processor continued to read and write to that block while others weren't using it. ___ c.) We could have ___ d.) Would cause caches to become incoherent [Mutex] Q. Here is our basic mutex algorithm using atomic swap: loop: while(swap(&lock,RED) == RED) { // spin! } // Critical section here lock = GREEN; // Unlock the mutex goto loop; Why did we modify our basic mutex algorithm for use with multiple processors (each with their own cache) Modified version below: loop: do { while(lock == RED) { // spin } } while(swap(&lock,RED) == RED); // Critical section here lock = GREEN; // Unlock the mutex goto loop; ___ a.) To stop spinning while waiting for the lock ___ b.) Avoid excessive bus traffic ___ c.) Avoid problems caused by being context switched out at an inopportune time. ___ d.) Avoid deadlock [Networks] Q. A knowledgeable CMPE designs a switch (such as the one we discussed in lecture) that was made using bridges. In order to save money he uses repeaters instead of bridges. Would you buy one of these switches? Why or why not? [Networks] Q. Why do we need Network Protocols? (Mark all that are correct) ___ a.) The International Standards Organization (ISO) requires a layered approach to abstraction ___ b.) Networks sometimes don't work very well ___ c.) The TCP/IP suite requires them ___ d.) Allow different manufacturers to use different technologies to make the global Internet work. [Distributed Computing] Q. Remote Procedure Call is modeled after what? [Distributed Computing] Q. Remote Procedure Call guarantees (Mark all that are correct) ___ a.) At most once performance ___ b.) At least once performance ___ c.) One performance ___ d.) Perfomance or notification of failure to perform satisfactorily [Networks] Q. Here is a portion of a router table: Dest Mask NextHop 30.0.0.0 255.0.0.0 40.0.0.7 40.0.0.0 255.0.0.0 deliver direct 128.1.0.0 255.255.0.0 deliver direct 192.4.10.0 255.255.255.0 128.1.0.9 Assume that we are trying to route a packet going to "Addr" Fill in the missing line of pseudocode: for each entry in table if(__________________________________________________) forward to NextHop [Networks] Q. Normally when a router discards a packet it sends a message back to the sender letting it know. When doesn't this happen?