CSE 130 Final

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/305

encourage image

There's no tags or description

Looks like no tags are added yet.

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

306 Terms

1
New cards

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

2
New cards

How many semaphores does each hungry philosopher use?

two (one semaphore for each chopstick)

<p>two (one semaphore for each chopstick)</p>
3
New cards

What are the three cases with solution 1: semaphores for each chopstick in the hungry philosophers issue?

  1. No contention

  2. Need to wait. P0 needs to wait for P1 to put C[1] down down (P1 - C[1].up) before it can have it.

  3. Deadlock. All 5 philosophers pick up one chopstick but cannot pick up the other and everyone is waiting on everyone

<ol><li><p>No contention </p></li><li><p>Need to wait. P0 needs to wait for P1 to put C[1] down down (P1 - C[1].up) before it can have it.</p></li><li><p>Deadlock. All 5 philosophers pick up one chopstick but cannot pick up the other and everyone is waiting on everyone</p></li></ol><p></p>
4
New cards

what is a resource?

something a process/thread uses; usually limited and thread needs exclusive access

5
New cards

(types of resources) can be taken away from a process with no ill effects

preemptable resource(ty

6
New cards

(types of resources) causes the process to fail if taken away

nonpreemptable resources

7
New cards

What kind of resource causes deadlock?

nonpreemptable resource

8
New cards

What is an infeasible region?

region to prevent t1 and t2 from accessing the same resource at the same time

9
New cards

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

10
New cards

what are the four conditions of deadlock?

  1. mutual exclusions- tasks claim exclusive control over resources

  2. non-preemption- resource cannot be taken away

  3. hold and wait- task holds a resource while waiting for another to release

  4. circular wait - circular chain of 2 or more processes where each resource is held by the next member of the chain

11
New cards

how do you deal with deadlock?

  • ignore the problem

  • detect deadlock and recover from it

  • prevent deadlock (avoid one of the four necessary conditions)

12
New cards

What is circular wait?

assign the order of resources and always acquire resources in that order

13
New cards

What does solution 2: grab the lower chopstick then wait for the higher numbered chopstick solve for the hungry philosophers?

deadlock

<p>deadlock</p>
14
New cards

How do you do a resource graph?

  • Vertex per resource

  • Arrow per thread/task

  • Tail for held resource

  • Arrowhead for wanted resource

<ul><li><p>Vertex per resource</p></li><li><p>Arrow per thread/task</p></li><li><p>Tail for held resource</p></li><li><p>Arrowhead for wanted resource</p></li></ul><p></p>
15
New cards

what is the ostrich algorithm?

Pretend there’s no problem; good if deadlocks are rare

16
New cards

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

17
New cards

How do you prevent deadlock?

ensure that at least one of the conditions for deadlock never occurs

18
New cards

(Preventing Deadlock) eliminate mutual exclusion

spooling

19
New cards

(Preventing Deadlock) eliminate hold and wait

require processes to request resources before starting

20
New cards

What is livelock?

Processes still run, but don’t make progress

<p>Processes still run, but don’t make progress</p>
21
New cards

(Preventing Deadlock) eliminate “non-preemptive resources”

take resources away if there’s not a complete set and it won’t break the processes

<p>take resources away if there’s not a complete set and it won’t break the processes</p>
22
New cards
<p>Who holds and who wants? Who is deadlocked?</p>

Who holds and who wants? Who is deadlocked?

2, 4, 5, 7 are in deadlock

<p>2, 4, 5, 7 are in deadlock</p>
23
New cards

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

24
New cards

(Preventing Deadlock) eliminating circular wait

order resources numerically

<p>order resources numerically</p>
25
New cards

What is a high-level construct that implements locks/synchronization implicitly?

monitors

26
New cards

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)

27
New cards

How do you implement monitors

language/compiler, or use semaphores

28
New cards

How do condition variables work in monitors?

They have two operations — wait() and signal(). Only usable within monitors

29
New cards

What are the advantages and disadvantages of monitors?

Adv: better than locks, condition variables, and semaphores

Dis: not many programming languages support monitors

30
New cards

(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

31
New cards

(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)

32
New cards

(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.

33
New cards

A pthreads condition variable is always associated with

  • another condition variable

  • a semaphore

  • a mutex

a mutex

34
New cards

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

35
New cards

(T/F) In the dining philosopher problem, we associate one semaphore with each philosopher

false

36
New cards

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

37
New cards

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()

38
New cards
<p>my answers are not fully correct lol</p>

my answers are not fully correct lol

1

S.down()

S.up()

S.down()

S.up()

39
New cards
<p>my answers are not fully correct lol</p>

my answers are not fully correct lol

N

T.down()

nothing

nothing

T.up()

40
New cards

stacks grow _____

memory grows _______

upwards

downwards

41
New cards

What does stack do? What is stored on the stack?

Stack “passes messages;” arguments, return address, local variables, saved registers

42
New cards

What is soft modularity?

Divide code into named procedures (like function calls) that “pass messages” from procedure to procedure

43
New cards

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

44
New cards

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.

45
New cards

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)

46
New cards

What is the solution to soft modularity?

hard modularity. Memory of the client is protected from server misbehavior

47
New cards

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

48
New cards

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

49
New cards

What if the server crashes?

Have a load balancer and multiple servers

<p>Have a load balancer and multiple servers</p>
50
New cards

What if the load is mostly static (little PHP and MySQL)?

Have more Apache/PHP instances than MySQL instances

<p>Have more Apache/PHP instances than MySQL instances</p>
51
New cards

What if we want high reliability?

Have redundant database instances

<p>Have redundant database instances</p>
52
New cards

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

53
New cards

What are some paradigms of client/server models?

message-based protocols, remote procedure calls, delayed/buffered asynchronous communication

54
New cards

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

55
New cards

Remote procedure call steps

  1. Client calls the procedure

  2. Stub builds message (function body)

  3. Message is sent across the network

  4. Stub makes local call to any library functions

  5. Stub unpacks message

  6. Server OS hands message to server stub

  7. Stub builds response

  8. Response is sent over network

  9. Client OS hands message to client stub

  10. Stub unpacks message

  11. Client call returns

56
New cards

What do stubs do in RPCs?

Make the RPC process easier; marshal arguments to the server, send messages, wait for response, and unpack results

57
New cards

What is the main advantage of RPCs?

RPCS reduce fate sharing — a crashed or hung RPC will not crash the caller

58
New cards

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

59
New cards

How do we solve the “New failure mode” issue with RPCs?

Use “___ Once” error handling

60
New cards

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.

61
New cards

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

62
New cards

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.

63
New cards

How do we solve RPC’s "inefficiencies” issue?

asynchronous RPC, marshalling, network transmission, round trip

64
New cards

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

65
New cards

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

66
New cards

What are some examples of marshaling?

  • Little endian to big endian

  • Size of integers (Ex: 16 to 32 bit)

  • Floating point format

  • Pointers

67
New cards

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

68
New cards

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)

69
New cards

What are the pros of client/server organization?

  • Limits interaction

  • Messages are sent over a wire

  • Good security

70
New cards

What are the cons of client/server organization?

  • Lots of separate modules

  • Expect modularity (separate computers

  • Inefficient

  • Lots of overhead

71
New cards

What is the solution to client/server organization?

virtualization

72
New cards

What is virtualization?

software-based representations of hardware, allows multiple modules to run on one computer

73
New cards

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

74
New cards

What are the three virtualization techniques?

multiplexing, aggregation, and emulation

75
New cards

virtualization techniques - multiplexing

create multiple virtual objects from one underlying physical object

<p>create multiple virtual objects from one underlying physical object</p>
76
New cards

virtualization techniques - aggregation

create one virtual object from multiple underlying physical objects

<p>create one virtual object from multiple underlying physical objects</p>
77
New cards

virtualization techniques - emulation

create a new type of virtual object from underlying physical objects

<p>create a new type of virtual object from underlying physical objects</p>
78
New cards

Multiplexing, aggregation, or emulation? Logical volumes (partitions) on a disk

Multiplexing

79
New cards

Multiplexing, aggregation, or emulation? RAID disk arrays

aggregation

80
New cards

Multiplexing, aggregation, or emulation? Linux logical volume manager

aggregation, multiplexing

81
New cards

Multiplexing, aggregation, or emulation? Virtual memory

All three

82
New cards

Multiplexing, aggregation, or emulation? sockets across a network (use network link for several connections)

multiplexing

83
New cards

Multiplexing, aggregation, or emulation? Channel bonding (multiple links that look like one faster link)

aggregation

84
New cards

Multiplexing, aggregation, or emulation? sockets on a local computer

emulation

85
New cards

Multiplexing, aggregation, or emulation? virtual hosts on a Web server (multiple sites from one Web server)

multiplexing

86
New cards

Multiplexing, aggregation, or emulation? RAM disk

emulation

87
New cards

Multiplexing, aggregation, or emulation? content distribution network

aggegation

88
New cards

Multiplexing, aggregation, or emulation? Virtual Box / DOSBox

multiplexing, emulation

89
New cards

Multiplexing, aggregation, or emulation? YouTube, Hulu, or other streaming service

aggregation

90
New cards

Multiplexing, aggregation, or emulation? Linux VMs

emulation

91
New cards

Virtual memory history - before virtual memory

8-bit or 16-bit microprocessors

92
New cards

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

93
New cards

Virtual memory history - actual virtual memory

Microprocessor has a memory management unit that translates virtual addresses into physical addresses

94
New cards

what is a thread?

one fundamental unit of execution and control flow; multiple threads allow computers to perform multiple tasks at the same time

95
New cards

What are the benefits of virtual memory?

Enforces modularity and separation can be relaxed

96
New cards

What is a bounded buffer?

a fixed-size buffer that facilitates communication between multiple concurrent threads (specifically producers and consumers)

97
New cards

What manages the bounded buffer?

The operation system; ensures threads can send and receive data, but not have direct access to shared memory

98
New cards

What are the four functions of threads?

  1. Allocate

  2. Deallocate

  3. Send

  4. Receive

99
New cards

Where does in point to in a bounded buffer?

The next empty location

<p>The next empty location</p>
100
New cards

Where does out point to in a bounded buffer?

The first filled location (FIFO!)

<p>The first filled location (FIFO!)</p>