Systems and Networks
Systems and Networks CS 2200
Popular in Course
Popular in ComputerScienence
This 0 page Class Notes was uploaded by Alayna Veum on Monday November 2, 2015. The Class Notes belongs to CS 2200 at Georgia Institute of Technology - Main Campus taught by Staff in Fall. Since its upload, it has received 15 views. For similar materials see /class/234116/cs-2200-georgia-institute-of-technology-main-campus in ComputerScienence at Georgia Institute of Technology - Main Campus.
Reviews for Systems and Networks
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 11/02/15
Multiprocessors and Multithreading What is multithreading technique allowing program to do multiple tasks is it a new technique has existed since the 7 0 s concurrent Pascal Ada tasks etc why now emergence of SMPs in particular time has come for this technology What is an SMP multiple CPUs in a single box sharing all the resources such as memory and IO Is an SMP more cost effective than two uniprocessor boxes yes roughly 20 more for a dual processor SMP compared to a uni modest speedup for a program on a dual processor SMP over a uni will make it worthwhile Programming Support for Threads creation pthreadcreatetoplevel procedure args termination return from toplevel procedure explicit kill rendezvous creator can wait for children pthreadjoinchildtid synchronization muteX condition variables Programming with Threads 0 synchronization for coordination of the threads communication for interthread sharing of data threads can be in different processors how to achieve sharing in SMP software accomplished by keeping all threads in the same address space by the OS hardware accomplished by hardware shared memory and coherent caches Synchronization Primitives lock and unlock mutual exclusion among threads busywaiting Vs blocking pthreadmuteXtrylock no blocking pthreadmuteXlock blocking pthreadmuteXunlock condition variables pthreadcondwait block for a signal pthreadcondsignal signal one waiting thread pthreadcondbroadcast signal all waiting threads example lockcsmuteX T1gt While resstate busy do nothing resstate busy unlockcsmuteX use resource T2gt lockcsmuteX resstate free unlockcsmuteX example With condvar lockcs muteX whileres state busy T1gt W3 00nd39Vaf implicitly give up muteX implicitly reacquire muteX resstate busy unlockcs mutex use resource lockcs muteX resstate free unlockcs mutex T2gt wakeupcondVar will wake up Tl Example Threads Program Producer repeat produce item pthreadmuteXlockm While full pthreadcondwaitnonfull m add item to buffer if no more bufferspace full true empty false pthreadcondsignalnonempty pthreadmuteXunlockm until false Consumer repeat pthreadmuteXlockm While empty pthreadcondwait n0nempty m remove item from buffer full false if no more items empty true pthreadcondsignalnonfull pthreadmutexunlockm consumeitem until false Using Threads Servers dispatcher model dispatcher E E IE Ill workers mail bOX team model Q 55 pipelined model gt gt gtI mail bOX Clients software simplicity exception handling terminal 10 0 signal handling FILE fp startr0utine string fname fname self fp openfname ltWrite legt print le print le char ch ch readfp printch mainO t1 createthread startr0utine t2 createthread startr0utine joint1 t2 Threads and OS Traditional OS DOS memory layout kernel protection between user and kernel Unix memory layout P1 P2 process process user code and code and data data PPR ppR kernel kernel code and data protection between user and kernel PCB programs in these traditional OS are single threaded one PC per program process one stack one set of CPU registers if a process blocks say disk IO network communication etc then no progress for the program as a Whole MT Operating Systems How Widespread is support for threads in OS Digital Unix Sun Solaris Win95 Win NT Process Vs Thread in a single threaded program the state of the executing program is contained in a process in a MT program the state of the executing program is contained in several concurrent threads Process Vs Thread a 6 gu user code data code data PCB PCB kernel kernel code and data computational state PC regs for each thread how different from process state Memory Layout static static heAap heap y A A A A v v v staCk stkl stk2 stk3 code code ST program MT program MT program has a perthread stack heap static and code are common to all threads threads share address space of process cooperate to get job done threads concurrent may be if the box is a true multiprocessor share the same CPU on a uniprocessor threaded code different from nonthreaded protection for data shared among threads synchronization among threads threads in a uniprocessor process io O allows concurrency between 10 and user processing even in a uniprocessor box Threads Implementation user level threads OS independent scheduler is part of the runtime system thread switch is cheap save PC SP regs scheduling customizable ie more app control blocking call by thread blocks process solution to blocking problem in user level threads nonblocking version of all system calls polling wrapper in scheduler for such calls switching among user level threads yield voluntarily how to make preemptive timer interrupt from kernel to switch Kernel level expensive thread switch makes sense for blocking calls by threads kernel becomes complicated process vs threads scheduling thread packages become nonportable problems common to user and kernel level threads libraries solution is to have threadsafe wrappers to such library calls Solaris Threads Three kinds user lwp kernel user any number can be created and attached to lwp s one to one mapping between lwp and kernel threads kernel threads known to the OS scheduler if a kernel thread blocks associated lwp and user level threads block as well Multiprocessor First Principles processors memories interconnection network Classi cation SISD SIMD MIMD MISD message passing MPs eg IBM SP2 shared address space MPs cache coherent CC SMP a busbased CC MIMD machine several vendors Sun Compaq Intel CCNUMA SGI Origin 2000 noncache coherent NCC Cray T3DT3E Caches and Consistency in SMP IE Shared Bus l cache cache with each processor to hide latency for memory accesses miss in cache gt go to memory to fetch data multiple copies of same address in caches caches need to be kept consistent CS 2200 Fig Fall 2000 Part A Closed Book and Notes Multiple multiple choice questions 140 Points 30 Minutes NAME NOTE J Part A is multiple multiple choice ie 1 or more choices may be correct You have to SELECT ALL CHOICES THAT APPLY for a question You select a choice by circling the letter associated with the selection Zero weight for missing a correct selection one positive weight for each correct selection and half negative weight for each incorrect selection The credit you get for a question is the weighted fraction of the total credit for that question For example if a question is worth 10 points and if there are 5 selections 2 of which are correct and you make 2 correct selections and 2 wrong selections the credit you get for that question is 10 2 12 5 You are sworn to keeping the questions in this exam a secret Please do not discuss this exam with any other students in the class This is for your own security in getting a good grade in the course 1 point The President of the United States is elected in direct proportion to one or more of the following criteria Select all that apply a The number of times he she says the word recount b Hisher ignorance of world geography c Hisher claims to having invented things or concepts d The number of courses in which heshe got poor grades in college e The number of times he she got stopped for DUI i The number of lawyers heshe is able to hire g The number of people who DO NOT want himher to be President h All of the above i None of the above 4 points pthreadcondsignal on a condition variable results in a blocking the calling thread b a noop if no thread is waiting on this condition variable c unblocking all the threads that are waiting on this condition variable d the signal being buffered and delivered to a thread that does a pthreadcondwait in the future on this condition variable even if there is no thread currently waiting on this condition variable 3 A U 0 5 points Select all statements that apply The memory layout of a multithreaded process a has one separate stack for each thread b has one separate heap for each thread c has all the threads in the process sharing the globals ie static data d gives a copy of the code ie the text to each thread 5 points Select all statements that apply In a uniprocessor constructing a process with multiple threads a has no apparent merit since there is only one processor b allows exploiting concurrency between processing and IO c will always result in slower execution time overall for the process as a whole d will always block the process as a whole if one of the threads makes a blocking system call 5 points From the following sentences regarding threads select the ones that are True a In Solaris there is a onetoone mapping between a user level thread and a kernel thread b One main advantage of a user level threads package is that thread switching time can be greatly minimized compared to OS supported thread switching c In pthreads a thread that does a pthreadmutexlock may not always block d In pthreads a thread that does a pthreadcondwait may not always block 5 points Select all statements that apply Protocol layering a allows changing the implementation of a layer without affecting other layers b allows functionally partitioning the responsibilities among the different layers c requires error checking to be done between the levels of abstractions represented by the layers d requires copying to be done between the levels of abstractions represented by the layers 7 5 points The following statements have to be answered with respect to a 9 0 faithful implementation of RFC that preserves all the semantics of RFC we discussed in class During an RPC session a client crashes and is restarted Select all statements that are True with respect to the interaction between the restarted client and the server a The server is given a new id referred to as uniqueid or serverid upon the first RPC call from the restarted client b The restarted client gets a new id referred to as clientid c The restarted client has to rebind to the server before being able to make any RPC call 1 There is a chance that a call from the restarted client may be rejected by the server as a duplicate of a call from the original crashed client 5 points From the following sentences regarding caches select ones that are True a The cache that is closest to the processor has a higher cycle time than the ones that are farther from the processor b For a given total cache size and for a given blocksize increasing the associativity leads to a lesser miss rate since several noncontiguous regions of a program can be simultaneously present in the cache c The reason for using an interleaved memory system is to reduce the time penalty that is experienced by the processor that has a miss in the cache d In a writeback cache with multiple words in a single block if there is a writemiss the missing block need not be brought from the memory into the cache 5 points Select all statements that apply to RTP protocol in Project 5 a It assumes that the network is reliable b It cannot handle arbitrary sized messages from the application level c The send and receive calls from the application have blocking semantics d It guarantees the order of message delivery to a specific receiver from a specific sender NAME CS 2200 Final Fall 2000 Part B Open Book and Notes 160 Points 90 Minutes Legible Writing is a Requirement NOT an option 1010 points This question is with respect to the disk space allocation strategy referred to as FAT Assume there are 20 data blocks numbered 1 through 20 There are three les currently on the disk foo occupies disk blocks 1 2 and 3 bar occupies disk blocks 10 13 15 17 18 and 19 gag occupies disk blocks 4 5 7 and 9 Show the contents of the FAT clearly show the free blocks and allocated blocks per convention discussed in class for this style of allocation