Week 3

Question 1

cmpxchg

Answer 1

Test and set for Intel. Source must be a register and destination is usually a address. Can’t be the A register. Put destination address into eax register. Compare it with dst register. If you get the correct address back, set zero flag to one and destination value to the source value. If not, set zero flag to zero and reset eax with dst register value.

Question 2

ARM

Answer 2

RISC style instruction set. exchange process. If two processes get the value 0, the store lets the process know its not the first one to get a zero. It will loop back and try again.

Question 3

Semaphores for synchronization

Answer 3

Set semaphore number higher.

Question 4

Bounded buffer with semaphores

Answer 4

Have a full = 0, empty = 0, and mutex = 1 semaphore. Full represents slots with data, empty represents buffer without data.

Question 5

Producer semaphore

Answer 5

Wait(empty), wait(mutex), Add to buffer, signal(mutex), signal(full)

Question 6

Consumer

Answer 6

wait(full), wait(mutex), CS, signal(mutex), signal(empty)

Question 7

Synchronizing consumer producer

Answer 7

Consumer wait will depend on producer signal. If empty is zero, will force producer to sleep until buffer empties.

Question 8

Reader Writer problem

Answer 8

Only one process is allowed to write to a resource at a time but more than one is allowed to read from a process. If reading -> no process can write and vice versa.

Question 9

Semaphore solution to read write - writer

Answer 9

wait(wrt), signal(wrt)

Question 10

Semaphore solution to read write - reader

Answer 10

wait(mutex), readcount++, if readcount ==1 wait(wrt), signal mutex, read, wait(mutex), readcount–, if readcount ==0 signal(wrte), signal(mutex)

Question 11

Critical Regions

Answer 11

High level solution to CS problem that removes programmer overhead.

Question 12

Shared keyword

Answer 12

Critical region that allows for only one process to access the shared resource at a time

Question 13

region v when B do S

Answer 13

region name when (boolean) do CS. If there is a simultaneous access the compiler will throw an error. When process leave S, all other programs reevaluate B.

Question 14

region v when B do S for Consumer-Producer

Answer 14

B is space in the array (producer) and data to read (consumer)

Question 15

Monitor

Answer 15

High level synchronization construct that allows for the safe sharing of data. Singleton class. Shared variables are set inside the monitor. Contains code to initialize variable, and procedure that represent to CS of various processes.

Question 16

Condition variables

Answer 16

Cues declared in shared variable section. Operations of wait and signal are applied to the queues. x.wait means put on queue, sleep, and yield lock. It will not affect variable y

Question 17

Signal in condition variables

Answer 17

When process executes x.signal and another process is waiting on x. First process goes to sleep until second process exits or waits. First process continues and executes. If another process wakes you up, you put that code to sleep, execute code, and then wake up another process.

Question 18

Explain producer-consumer model for monitor

Answer 18

See picture

Question 19

Prioritized waiting for monitor

Answer 19

X.wait(x) where x is an integer that will give priority on the queue for X

Question 20

Java Synchronized methods

Answer 20

Synchronized keyword applied to method. Makes the method become a monitor. Must specify the object that acts as the lock in the parameters. Java’s synchronization does not explicitly require you to declare the shared variable within the block. Instead, the block synchronizes on the object instance specified in the synchronized keyword. Every object has an intrinsic lock

Question 21

Java Producer Consumer

Answer 21

Notify -> signal but it wakes up everyone who was sleeping. One will wake up and the others will go back to sleep. Does not ensure priority over the latest to wait (no bounded wait). Only one condition variable is necessary because the buffer cannot be full and empty.

Question 22

Processing Bursts

Answer 22

Most are short I/O, few are long CPU

Question 23

Hyper exponential distribution

Answer 23

Length of bursts vs occurrences. Really short and long bursts are rare. See picture

Question 24

Preemptive Scheduler

Answer 24

Takes itself off the CPU other than for I/O or finishing. Does not get switched at every interrupt

Question 25

Dispatcher

Answer 25

Part of scheduler responsible for performing context switch and resuming process

Question 26

Dispatch latency

Answer 26

Time for dispatcher to run

Question 27

CPU utilization - sched criteria

Answer 27

Keep CPU as busy as possible

Question 28

throughput - sched criteria

Answer 28

of jobs per unit of time

Question 29

turnaround - sched criteria

Answer 29

Time of submission to completion

Question 30

Wait time - sched criteria

Answer 30

Average amount of time in ready queue

Question 31

Response - sched criteria

Answer 31

Submit time to output request (keystroke to terminal)

Question 32

Simulation vs Implementation

Answer 32

Simulation involves trying out the different scheduling, which is hard to do. Implementation is try and find out which is expensive

Question 33

Multiple processor queues

Answer 33

Usually a common queue for all processors. However, not every board has access to every I/O device.