CSE 130 FINAL

What is system

Set of interconnected components that has an expected behavior observed at the interface with its environment

Four issues of complexity

1. Emergent properties

2. Propagation of effects

3. Incommensurate scaling

4. Tradeoffs

5 signs of complexity

1. Large # of components

2. Large # of interconnections

3. Lots of irregularities

4. Long description

5. Large team of designers, implementers, or maintainers

2 sources of system complexity

1. Interaction of requirements

2. Increasing efficiency, utilization, or other measures of “goodness”

What increases complexity? (3)

1. Principle of escalating complexity

2. Principle of excessive generality

   1. Law of diminishing returns

How can we manage complexity? (5) Explain each.

1. Modularity: break big things into smaller pieces

2. Abstraction: break into components at logical points

3. Layering: build new layer from (already existing) lower layer

4. Hierarchy: combine smaller groups into one larger group

5. Naming: controls and manages all of the above

What is robustness principle?

Tolerant on inputs, Strict on outputs

Difference between char *s; and char t[10];

s is a pointer to a char; t is an array of 10 chars

Can a string “abc” in char *s = “abc”; be modified?

No

Can a string “abc” in char t[10] = “abc”; be modified?

Yes

What is sizeof(t) for char t[10] = “abc”;

10

What is sizeof(s) for char *s = “abc”;

4

What is strlen(s) for char *s = “abc”;

3

What is strlen(t) for char t[10]= “abc”;

3

What is sizeof(t) for char t[] = “abc”;

4

Can s be set to NULL after char *s;

Yes

Can t be set to NULL after char t[] = “abc”;

No

How can a program tell apart between a pointer to char and a pointer to an array of chars for char *s?

It cannot. It is a programmer’s duty.

Local variable vs Global variable— Where is it created?

Local variable: Stack

Global variable: Separate memory for global variables

Local variable vs Global variable— What is it initialized to?

Local variable: Unknown

Global variable: Zero

Explain a static variable

It is a variable that acts like a global variable (initialized to zero, persists in the memory) but has a local scope (can only be called within its function)

Explain strtok()— parameters and behavior

Parameters: char* str, const char* delim

Behavior:

• strtok() starts from a str and moves along str until finding delim, on which it replaces delim with null char

• If str == NULL, then it starts off from where the last strtok() left off

Explain read()— parameters and behavior

Parameters: int fd, char* buf, size_t count

Behavior:

• Reads from fd up to count bytes and stores it in buf

• Returns 0 when EOF, -1 on error, positive number for # of bytes read

Explain write()— parameters and behavior

Parameters: int fd, char* buf, size_t count

Behavior:

• Writes up count bytes from buf to fd

• Returns -1 on error, nonnegative for # of bytes actually written

What are some flags for open()?

O_RDONLY, O_WRONLY, O_RDWR, O_TRUNC, O_CREAT

What are some modes for open()?

0 for no access, 0644 or 0666 to enable writing to the file after creating

What does open() return?

int fd of the file on success

-1 on error

What is the equivalent of int creat(fd, mode);

open(fd, O_WRONLY | O_CREAT |O_TRUNC , mode)

What does unlink(); do?

Deletes a file

Explain lseek()— parameters and behavior

Parameters: fd, offset: # bytes to move from origin, origin: SEEK_SET, SEEK_CUR, SEEK_END

Like moving a cursor

Behavior: “

• Readies” a read/write by moving the cursor

• Returns where you place the cursor

Fundamental Abstractions— Three parts of a system

1. Memory

2. Interpreter

3. Communication links

Memory is modeled as a ___ between a space of names and a space of values

Map

Name 6 memories in a hierarchy shown in lectures

1. Registers

2. Caches (L1, L2, L3)

3. DRAM

4. SSDs

5. HDDs

6. Tape

List 7 memory properties

Volatility

Abundance

Cost

Performance

Granularity

Failure rate

Coherency and atomicity

Where does volatility/non-volatility split between the 6 memory examples?

DRAM and SSDs

How are abundance and cost related?

Less abundance => More cost

What are two measures of performance of memory?

Bandwidth and latency

What is more important, read latency or write latency? Why?

Read latency, because writes can be asynchronous, meaning writes can be processed later/in the background, whereas usually a user/system waits on read

How fast is a program when it’s bound by synchronous read/write?

Latency

How fast is a program when it’s bound by asynchronous read/write?

Bandwidth

What are the types of granularity in memory?

Registers: one-to-one map

Byte-addressable: Cache/RAM

Block-addressable: SSD/HDD

File systems are software that provide a ______ interface from a _____ interface

stream, block

In flash memory, writing 1 happens on _____ and writing 0 happens on _____.

an entire bank, an individual bit

What is read size for NOR flash memory?

Words (2-4 bytes)

What is read size for NAND flash memory?

Pages (2-16KB)

What is more important for a small block size read/write— latency or bandwidth?

Latency

What are some ways to mitigate frequent fails in block devices?

Redundancy, checksum, etc.

Is duplication for DRAM or registers feasible?

No, too expensive

Explain read/write coherency

Result of a read => Result of the last write

Explain read/write atomicity

Result of a read => Result of a write completely before OR completely after the read (i.e., no half-and-half read)

What are the three parts of an interpreter?

1. Instruction reference

2. Repertoire

3. Environment reference

What are the three steps of an interpreter?

1. Fetch instruction from memory (PC)

2. Execute

3. Check for need to service an interrupt

Provide one example of using layers of interpreters

Windows— One (higher-layer) interface accepts various inputs such as key presses and clicks. This interpreter sends messages down to lower layer interpreters, which process actions to be done

How can local procedure call misbehave?

Can read/write to out-of-scope local variables

Define soft modularity

Pass messages/data from one function to a second one by calling it

What is one error caused by soft modularity?

Propagation of errors

Define hard modularity

Pass messages/data over a network connection

Why is hard modularity safer from propagation of effects?

No shared memory or interpreter → failure in one system does not affect the other

What does LAMP stand for in a web server model?

Linux, Apache, MySQL, PHP

How would you alter LAMP to deal with static load/infrequent DB access?

Increase AP + load balancer, while keeping M minimal

How would you alter LAMP if you needed high reliability?

Use multiple M (redundancy)

What is a core issue with messages? What is one way we could address this?

They may not reach the other party, and we need a way to know what happened.

Use acknowledgements.

What are the three types of ____ once in RPC?

• Which one(s) uses unique id?

• Which requires a request to be idempotent?

At Least once: needs to be idempotent

At Most once: needs unique id (duplication in the network)

Exactly once: needs unique id

Why can we not guarantee 100% accurate implementation of exactly once RPC?

Set of unique ids/results cannot grow indefinitely

What is asynchronous RPC?

Client sends the request, but it doesn’t wait for the return. It continues with other works and later processes the results.

What is marshaling/serialization in RPC?

Agreeing that data on the two end systems have the same meaning (e.g. converting to ensure same endian-ness, size of int, pointers)

Is virtualization soft modularity or hard modualrity?

Neither, it’s in between

Three basic virtualization techniques and their definitions

1. Multiplexing: one physical object → multiple virtual objects

2. Aggregation: many physical objects → one virtual object

3. Emulation: physical object(s) → a new type of virtual object

Which of the three virtualization technique is “Sockets across a network”?

Multiplexing— one physical network interface → many sockets

Which of the three virtualization technique is “RAM disk”?

Emulation— OS uses RAM as if it’s a disk to store things

Which of the three virtualization technique is “RAID”?

Aggregation— combining multiple physical disks into one logical volume

Which of the three virtualization technique is “Content distribution network”?

Aggregation— many servers disguised as one server

Which of the three virtualization technique is “Logical volume manager“?

Multiplexing & Aggregation— Can combine multiple disks as one as well as partition one volume into many

Define virtual memory

Memory that processes can use as if they each have their private own memory

_______ allows two processes to read/write to same physical address

Inter-process communication

How can a bounded buffer act as a communication link?

Threads cannot communicate with each other directly— they communicate through the OS using bounded buffer

4 OS-provided functions for bounded buffers

1. allocate

2. deallocate

3. send

4. receive

Why should a bounded buffer be bounded?

Back pressure— sender should not send too much data at start

What is a problem with this code? (Find 2)

1. Busy wait (line 2)

2. Race condition (line 5)

Define race condition

Behavior of a system depends on timing or order of uncontrollable events

Define data race

Two unordered memory operations (one of which is write) act on the same variable

Is multiple reads on the same memory OK? (Does it have a race condition?)

Yes, it is OK

4 steps to fix race conditions

1. Critical regions

2. Mutual exclusion

3. Condition variables

4. Semaphores

Define critical region

Region that must be executed by only one thread at a time

What is mutual exclusion?

Ensuring only one thread is in its critical region at a time

4 requirements to achieve mutual exclusion

1. No two threads may be simultaneously inside their critical regions

2. Any number of threads

3. No thread running outside its critical region may block another thread

4. No thread can wait forever to enter its critical region

Why should a while loop be included in a critical region?

If you lock after checking the loop condition, an OS may allow multiple threads to enter the loop

How do you prove possible outcomes?

1. Choose a “vocabulary” (e.g. Load, Add, Store)

2. Find an order of operations that shows the outcome

What is deadlock?

One thread acquires the lock and waits for a condition (e.g. push waits for the buffer to be pop()-ed) but another thread cannot fulfill that condition because of the lock

What is one inefficient way to resolve deadlock? What is another issue caused by this method?

Strategic release()/acquire() pairs, causing spinlock (wasting CPU resources)

Explain pthread_create(1,2,3,4)

1. Pointer to pthread_t

2. NULL (we don’t use in class)

3. Pointer to a thread function

4. Arguments to be passed to 3 as (void *)

Explain pthread_join(1,2)

pthread_join() waits/blocks until the thread function returns

1. pthread_t (not a pointer!)

2. Pointer to return val

Say we want to pass in a thread_id to the thread function. How do we do it?

Use intptr_t to cast int to void *

int thread_id = i; (using for loop)

intptr_t intptr = thread_id;

pthread_create(…, (void *) intptr);

What functions do we use to lock and unlock mutex?

pthread_mutex_lock(1) and pthread_mutex_unlock(1)

• 1: pointer to pthread_mutex_t

Three functions used to wake thread(s) and release lock using condition variable

1. wait(): release lock and reacquires it once released by another

2. signal(): wakes one thread waiting on a condition variable

3. broadcast(): wakes all threads waiting on a condition variable

Functions for creating and destroying a mutex lock

// static initialization
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

// dynamic initialization
pthread_mutex_t mutex;

int rc = pthread_mutex_init(&mutex, NULL);
assert(rc == 0);


int rc = pthread_mutex_destroy(&mutex, NULL);
assert(rc == 0);

(T/F) Mutex prevents suspension of the thread by the OS.

False, mutex only requires other threads to honor the lock, so that only one thread enters the critical system at a time

When does a thread enter a zombie state?

When thread finishes but parent has not joined

What function do we use to collect zombie threads?

pthread_join()

______ overflows if we don’t call pthread_join() on zombie threads

Thread table