1/305
Looks like no tags are added yet.
Name | Mastery | Learn | Test | Matching | Spaced |
---|
No study sessions yet.
What are the lessons of the sleepy barber problem?
Initialize semaphore to 0
Semaphores coordinate two threads
T1: sem.down() causes T1 to wait
T2: sem.up() lets T1 proceed
Use a mutex using a semaphore to protect its shared variables
T1: mutex.down() gets the lock
T2: mutex.down() must wait for T1 to release the lock with mutex.up()
Semaphore’s up and down are atomic and you can make an atomic operation using mutexes (initialize semaphore mutex to 1)
Up and down pairs must match
How many semaphores does each hungry philosopher use?
two (one semaphore for each chopstick)
What are the three cases with solution 1: semaphores for each chopstick in the hungry philosophers issue?
No contention
Need to wait. P0 needs to wait for P1 to put C[1] down down (P1 - C[1].up) before it can have it.
Deadlock. All 5 philosophers pick up one chopstick but cannot pick up the other and everyone is waiting on everyone
what is a resource?
something a process/thread uses; usually limited and thread needs exclusive access
(types of resources) can be taken away from a process with no ill effects
preemptable resource(ty
(types of resources) causes the process to fail if taken away
nonpreemptable resources
What kind of resource causes deadlock?
nonpreemptable resource
What is an infeasible region?
region to prevent t1 and t2 from accessing the same resource at the same time
what is the consequence of two infeasible regions?
unsafe regions; causes the progress of both tasks to permanently stop if thread progress enters it; deadlock— t1 has r2, wants r1, t2 has r1, wants r2
what are the four conditions of deadlock?
mutual exclusions- tasks claim exclusive control over resources
non-preemption- resource cannot be taken away
hold and wait- task holds a resource while waiting for another to release
circular wait - circular chain of 2 or more processes where each resource is held by the next member of the chain
how do you deal with deadlock?
ignore the problem
detect deadlock and recover from it
prevent deadlock (avoid one of the four necessary conditions)
What is circular wait?
assign the order of resources and always acquire resources in that order
What does solution 2: grab the lower chopstick then wait for the higher numbered chopstick solve for the hungry philosophers?
deadlock
How do you do a resource graph?
Vertex per resource
Arrow per thread/task
Tail for held resource
Arrowhead for wanted resource
what is the ostrich algorithm?
Pretend there’s no problem; good if deadlocks are rare
How do you detect and recover from deadlock?
Preemption - take resource from some other process
Rollback - periodic checkpoints, restart a process if it is in deadlock
Kill one process in the deadlock cycle, choose one that can be rerun from the start
How do you prevent deadlock?
ensure that at least one of the conditions for deadlock never occurs
(Preventing Deadlock) eliminate mutual exclusion
spooling
(Preventing Deadlock) eliminate hold and wait
require processes to request resources before starting
What is livelock?
Processes still run, but don’t make progress
(Preventing Deadlock) eliminate “non-preemptive resources”
take resources away if there’s not a complete set and it won’t break the processes
Who holds and who wants? Who is deadlocked?
2, 4, 5, 7 are in deadlock
How can you see which resources are in deadlock in a resource graph?
They’re in a cycle and any process that wants a resource in the cycle is also deadlocked
(Preventing Deadlock) eliminating circular wait
order resources numerically
What is a high-level construct that implements locks/synchronization implicitly?
monitors
How do monitors work
One monitor has multiple entry points
Only one thread may be in the monitor at a time (no manual locking/unlocking)
How do you implement monitors
language/compiler, or use semaphores
How do condition variables work in monitors?
They have two operations — wait() and signal(). Only usable within monitors
What are the advantages and disadvantages of monitors?
Adv: better than locks, condition variables, and semaphores
Dis: not many programming languages support monitors
(Mutex Alternatives) Strict Alternation. What is its issue?
only two threads; take turns and use a shared variable to keep track of whose turn it is. Problem: if one of the processes no longer needed the CR, it wouldn’t access the CR to give the turn variable to the other process
(Mutex Alternatives) Dekker’s Algorithm
Threads express “interest” in the critical region, which alerts other threads; gives lock to thread only if the other thread is not interested and its the thread’s turn(Mutex Alternatives)
(Mutex Alternatives) Lamport’s Algorithm
allows multiple processes or threads to access a shared resource without conflicts. It works by assigning each process a number (ticket) when it wants to enter the critical section, and the process with the lowest number gets access first.
A pthreads condition variable is always associated with
another condition variable
a semaphore
a mutex
a mutex
Which of the following is not a way to prevent deadlock?
Avoid giving threads exclusive access to a shared resource
Require all threads to acquire resources in the same order
Require threads to release held resources before acquiring more
Require threads to tolerate having their held resources taken away by the operating system
None of the above
None of the above
(T/F) In the dining philosopher problem, we associate one semaphore with each philosopher
false
Which if the following is not a mutual exclusion property?
Any number of threads should be supported
Only one thread can access a shared resource at a time
The algorithm cannot busy wait
Threads should not wait forever to enter a critical section
Threads that are outside of a critical section cannot block other threads
The algorithm cannot busy wait
A thread enters a “zombie state” when…
it exits but has no value to return
it exits before a call to pthread_join()
it exits directly from the running state
it cannot run for some reason
it exits before a call to pthread_join()
my answers are not fully correct lol
1
S.down()
S.up()
S.down()
S.up()
my answers are not fully correct lol
N
T.down()
nothing
nothing
T.up()
stacks grow _____
memory grows _______
upwards
downwards
What does stack do? What is stored on the stack?
Stack “passes messages;” arguments, return address, local variables, saved registers
What is soft modularity?
Divide code into named procedures (like function calls) that “pass messages” from procedure to procedure
What is soft modularity’s issue?
Caller and callee share the same memory and interpreter, which creates security issues. This causes error propagation, which we do not want
What are constrained languages, and why are they not a good solution to soft modularity?
Constrained languages (ex: Java) are a solution to limiting error propagation. But they are difficult to implement system code with and can still have error propagation.
What is enforced modularity, and why is it not a good solution to soft modularity?
A stronger form of modularity. It is very difficult to implement (nearly impossible for system-level languages)
What is the solution to soft modularity?
hard modularity. Memory of the client is protected from server misbehavior
What is hard modularity?
Stricter separation of modules; client sends a request and the server sends a response over a network connection; connected by a wire (which may or may not be real); separate memories and interpreters
What are the components of a “LAMP” web server?
Operating system (Linux)
HTTP Server (Apache)
Database management system (MySQL)
Programming Language (PHP, Perl, Python)
All of these components can run on the same server hardware
What if the server crashes?
Have a load balancer and multiple servers
What if the load is mostly static (little PHP and MySQL)?
Have more Apache/PHP instances than MySQL instances
What if we want high reliability?
Have redundant database instances
What are the advantages of hard modularity?
No way to violate modularity (messages are the only communication)
Error propagation is limited (no side effects)
Error of commission - message has “bad” contents
Error of omission - error because message doesn’t arrive.
Attackers can only use messages
Interchangeability - any module that handles messages properly should work
What are some paradigms of client/server models?
message-based protocols, remote procedure calls, delayed/buffered asynchronous communication
What is a remote procedure call (RPC)?
Calling a function over a network so the server executes the function, uses stubs. A type of client/server model
Remote procedure call steps
Client calls the procedure
Stub builds message (function body)
Message is sent across the network
Stub makes local call to any library functions
Stub unpacks message
Server OS hands message to server stub
Stub builds response
Response is sent over network
Client OS hands message to client stub
Stub unpacks message
Client call returns
What do stubs do in RPCs?
Make the RPC process easier; marshal arguments to the server, send messages, wait for response, and unpack results
What is the main advantage of RPCs?
RPCS reduce fate sharing — a crashed or hung RPC will not crash the caller
What are the main disadvantage of RPCs?
New failure modes (what happens if there’s no response to an RPC?) and less efficient than procedure calls
How do we solve the “New failure mode” issue with RPCs?
Use “___ Once” error handling
Error handling in RPCs — at least once
Keep retrying until you get a positive acknowledgement (might time out). Use an idempotent request— no side effect from repeating the call. Duplicated network packet looks like another request.
Error handlng in RPCs — at most once
Send a request and wait for a response (or it times out). Either succeed or fail, but don’t respond
Error handling in RPCs — exactly once
Send a request to a specific location because it expects an acknowledgement (typically to a specific ID). Duplicated network packet is detected by tracking requests. Most reliable, but more complex.
How do we solve RPC’s "inefficiencies” issue?
asynchronous RPC, marshalling, network transmission, round trip
What is an Asynchronous RPC and how does it help with RPC’s inefficiencies?
Eliminate wait for an RPC (wait doesn’t mean constantly running) by reducing the delay at the client
What is marshaling (AKA serialization) and how does it help with RPC’s inefficiencies?
Adjusts data representation when sent from source to destination. Agrees on a following format and one side converts data to/from a byte stream. Used on client-server models like RPCs
What are some examples of marshaling?
Little endian to big endian
Size of integers (Ex: 16 to 32 bit)
Floating point format
Pointers
Why are pointers hard to marshal? What’s the solution?
It’s very hard to transfer addresses from source to destination. Swizzling is the solution— converts addresses to identifiers
What is the solution if the client or server is down?
An intermediary — buffers messages by downloading them onto its server and sending them when the server/client is no longer down. The notification can be brought through push (initiator sends message) or pull (initiator asks other side to send message)
What are the pros of client/server organization?
Limits interaction
Messages are sent over a wire
Good security
What are the cons of client/server organization?
Lots of separate modules
Expect modularity (separate computers
Inefficient
Lots of overhead
What is the solution to client/server organization?
virtualization
What is virtualization?
software-based representations of hardware, allows multiple modules to run on one computer
Why is virtualization a middle ground between hard and soft modularity?
Has separate virtual interpreters and memory
With a flaw, attackers can hack the system
Power failure brings down all computers
What are the three virtualization techniques?
multiplexing, aggregation, and emulation
virtualization techniques - multiplexing
create multiple virtual objects from one underlying physical object
virtualization techniques - aggregation
create one virtual object from multiple underlying physical objects
virtualization techniques - emulation
create a new type of virtual object from underlying physical objects
Multiplexing, aggregation, or emulation? Logical volumes (partitions) on a disk
Multiplexing
Multiplexing, aggregation, or emulation? RAID disk arrays
aggregation
Multiplexing, aggregation, or emulation? Linux logical volume manager
aggregation, multiplexing
Multiplexing, aggregation, or emulation? Virtual memory
All three
Multiplexing, aggregation, or emulation? sockets across a network (use network link for several connections)
multiplexing
Multiplexing, aggregation, or emulation? Channel bonding (multiple links that look like one faster link)
aggregation
Multiplexing, aggregation, or emulation? sockets on a local computer
emulation
Multiplexing, aggregation, or emulation? virtual hosts on a Web server (multiple sites from one Web server)
multiplexing
Multiplexing, aggregation, or emulation? RAM disk
emulation
Multiplexing, aggregation, or emulation? content distribution network
aggegation
Multiplexing, aggregation, or emulation? Virtual Box / DOSBox
multiplexing, emulation
Multiplexing, aggregation, or emulation? YouTube, Hulu, or other streaming service
aggregation
Multiplexing, aggregation, or emulation? Linux VMs
emulation
Virtual memory history - before virtual memory
8-bit or 16-bit microprocessors
Virtual memory history - sort of virtual memory
Virtual memory through software — like MS-DOS .EXE files with a fixup table that lists microprocessor instructions that need to be fixed
Virtual memory history - actual virtual memory
Microprocessor has a memory management unit that translates virtual addresses into physical addresses
what is a thread?
one fundamental unit of execution and control flow; multiple threads allow computers to perform multiple tasks at the same time
What are the benefits of virtual memory?
Enforces modularity and separation can be relaxed
What is a bounded buffer?
a fixed-size buffer that facilitates communication between multiple concurrent threads (specifically producers and consumers)
What manages the bounded buffer?
The operation system; ensures threads can send and receive data, but not have direct access to shared memory
What are the four functions of threads?
Allocate
Deallocate
Send
Receive
Where does in point to in a bounded buffer?
The next empty location
Where does out point to in a bounded buffer?
The first filled location (FIFO!)