click below
click below
Normal Size Small Size show me how
CS240 MiniExam4
Question | Answer |
---|---|
True or False: Concurrency has multiple applications | true |
what type of applications apply concurrency? | structured |
how is concurrency related to the operating system | operating system is a set of processes or threads and therefore tend to operate using this |
critical section | a section of code within a process that requires access to shared resources and which may not be executed while another process is in a corresponding section of code |
dead lock | a situation in which two or more processes are unable to proceed because each is waiting for one of the others to do something |
livelock | a situation in which two or more processes continuously change their state in response to changes in the other process(es) without doing any useful work |
mutual exclusion | the requirement that when one process is in the critical section that accesses shared resources no other processes may be in the critical section that access any of the above shared resources |
race condition | a situation in which multiple threads or processes read and write to a shared data item and the final result depends on the relative timing of their execution |
starvation | a situation in which a run-able process is overlooked by the scheduler ; although it is able to proceed it is never choosen |
what are some of the difficulties of concurrency? | >Sharing of global resources >Operating system managing the allocation of resources optimally >Difficult to locate programming errors |
why is sharing of global resources difficult ? | overwriting |
why is it difficult to locate programing errors in concurrency? | results are non-deterministic and not really reproducible |
why is operating system managing the allocation of resources optimally an issue in concurrency? | dependent on the non-deterministic execution of processes which cause allocation to be an issue |
what are main features of concurrency? | >Communication among processes >Sharing resources >Synchronization of multiple processes >Allocation of processor time |
What is an application for concurrency? | multi-programming |
what is an example of a structured application | Application can be a set of concurrent processes |
what is a simple example of a concurrency program? | void echo(){chin = getchar(); chout = chin; putchar(chout);} ran on 2 processors Issues:both processes value will print based on the last getchar executed |
what are some of the operating system concerns? | >Keep track of various processes >Allocate and deallocate resources >Protect data and resources >Output of process must be independent of the speed of execution of other concurrent processes |
what are some allocation and de-allocation of resources that are concerns regarding the operating system | Processor time Memory Files I/O devices |
what are the ways concurrent processes interact? | >Processes unaware of each other >Processes indirectly aware of each other >Process directly aware of each other |
if a process has a degree of awareness where the processes are unaware of each other describe the relationship between the processes | competition |
if a process has a degree of awareness where the processes are unaware of each other what is the influence that one process has on the other? | >results of one process independent of the action of others >timing of process may be affected |
if a process has a degree of awareness where the processes are unaware of each other what are some potential control problems? | >mutual exclusion >deadlock (renewable resource) >starvation |
if a process has a degree of awareness where the processes are indirectly aware of each other describe the relationship between the processes | cooperation by sharing |
if a process has a degree of awareness where the processes are indirectly aware of each other what is the influence that one process has on the other | >results of one process may depend on information obtained from others >timing of processes may be affected |
if a process has a degree of awareness where the processes are indirectly aware of each other what are potential control problems? | >mutual exclusion >deadlock (renewal resource) >starvation >data coherence |
what causes processes to be indirectly aware of each other | shared object |
if a process has a degree of awareness where the processes are directly aware of each other describe the relationship between the processes | cooperation by communication |
if a process has a degree of awareness where the processes are directly aware of each other describe the influence that one process has on the other? | >results of one process may depend on information obtained from the others >timing of processes may be affected |
if a process has a degree of awareness where the processes are directly aware of each other what are some potential control problems? | >deadlock (consumable resource) >starvation |
what causes processes to be directly aware of each other | have communication primitives available to them |
how do we handle competition among processes for resources | mutual exclusion through critical sections |
what does mutual exclusion mean | only on program at a time is allowed in the critical section |
what can happen when processes are in competition for resources? | >mutual exclusion may occur >deadlock >starvation |
what are the requirements for mutual exclusion | >only 1 process at a time is allowed in the critical section for a resource >a process that halts in its non-critical section must do so without interfering with other processes >no deadlock/starvation |
what are some more requirements for mutual exclusion? | >a process must not be delayed access of a critical section when there is no other processes using it >no assumption are made about relative process speeds or number of processes >a process remains inside its critical section for a finite time only |
how is mutual exclusion supported through hardware? | >interrupt disabling >special machine instructions |
what happens during interrupt disabling | a process runs until it invokes and operating system service or until it is interrupted |
how does interrupt disabling relate to mutual exclusion on a uni processor? | processor is limited in its ability to interweave programs- thus disabling interrupts guarantees mutual exclusion |
how does interrupt disabling relate to mutual exclusion during multiprocessing? | disabling interrupts on one processor will not guarantee mutual exclusion |
how do special machine instructions execute and provide mutual exclusion? | >preformed in a single instruction cycle >access to the memory location is blocked for any other instructions |
what is an example of special machine instructions for mutual exclusion | >test and set instruction >exchange instruction |
how does test and set instruction work (sudo code) | boolean testset(int i){ if(i==0){ i=1; return true; }else{ return false; }} |
how does the exchange instruction work (Sudo code) | void exchange(int register, int memory){ int temp; temp= memory; memory = register; register = temp; } |
what is parbegin | initiate all processes and resume program after all Pi's have terminated- run all programs in parallel |
example program using mutual exclusion and test and set | const int n; //#processes int bolt; void P(int i){ while(true){ while(!testset(bolt)) /*do nothing*/ /*critsect*/ bolt=0; /*remainder*/}} void main(){ bolt=0; parbegin(P(1)...P(n));} |
example program using mutual exclusion for exchange instruction | int const n = /*num of processes*/ int bolt; voidP(int i){ int keyi; while(true){ keyi=1; while (keyi!=0){ exhange(keyi, bolt); /*crit sect*/ exchange(keyi, bolt); /*remainder*/}} void main(){ bolt=0; parbegin(P(1)..P(n));} |
what are the advantages of mutual exclusion machine instructions? | >applicable to nay number of processes on either a single processor or multiple processors sharing main memory >it is simple and therefore easy to verify >it can be used to support multiple critical sections |
what are the disadvantages of mutual exclusion machine instructions | >busy waiting consumes processor time >starvation >dead lock |
how does starvation happen with mutual exclusion machine instructions | when a process leaves critical section and more than one process is waiting |
how does deadlock happen with mutual exclusion machine instructions | if a low priority process has the critical section and a higher priority process needs it the higher priority process will obtain the process to wait for the critical section which will not be returned |
what is bakerys algorithm also called | lamports bakery algorithm |
who created bakery algorithm | leslie lamport |
what is bakerys algorithm | this is a mutual exclusion algorithm to prevent concurrent threads from entering critical sections currently |
explain the anaolgy for bakerys algorithm | bakery with a numbering machine. each customer receives unique number. (increments by 1) global counter displays number being served. after baker is done serving next number is displayed. served customer leaves |
how do threads work in bakerys algorithm | >threads want to enter critic sect it has to make sure it has the smallest # (it may not be true that only on the thread gets the same #) >1+ threads has the smallest #then the thread with the lowest id goes n pair(#,ID) (a,b)<(c,d)=(a<c)or(a==c)&(b<d) |
what does petersons algorithm do? | solves critical section problem based on shared memory for communication |
what is a semaphore? | special variable used for signaling |
if a process is waiting for a semaphore signal what happens? | it is suspended until that signal is sent |
what type is a semaphore | variable that has an integer value |
what is a semaphore initialized too? | a non-negative number |
what happens during the wait operation to the semaphore value? | decrements it |
what happens during the signal operation to the semaphore value? | increments it |