Purdue CS 252 Final Study Guide

thread

Path of execution. By default, each program has a main thread that executes main().

Every thread has its own...

Stack

PC - Program Counter

Set of registers

State

What are some of the application of threads?

Threads help divide up the work, can be used in applications like servers. This leads to a faster overall completion time if they are doing independent tasks.

What are the advantages of threads? (versus processes)

Fast thread creation - creating a new path of execution is easier.

Fast context switch - context switch across threads is faster than across processes.

Faster communication - fast & easy to talk between threads. (processes require pipes, etc).

What are the disadvantages of threads? (versus processes)

Threads are less robust - if one thread crashes, the entire application will crash. If one process crashes, all other processes remain running.

More sync problems - Since threads modify the same global variables at the same time, they may corrupt data structures. Synchronization is required.

What is an atomic section of code?

A portion of code that only one thread should execute at a time, while the other threads wait. Sometimes called a "critical section".

What are mutex locks?

Mutex locks are software mechanisms that enforce atomicity. They enforce mutal exclusion of two or more sections of code if the same lock is used.

What are the two mutex lock implementations?

Disable interrupts: Used only in Kernel mode, so that context switches cannot happen. May lose interrupts and can be slow.

Spin locks: Can be implemented in user space, rely on the test_and_set assembly instruction (since it is guaranteed atomic).

What are spin locks?

A type of lock that rely on the test_and_set assembly instruction, which is guaranteed to be atomic. Mutex locks are implemented on top of spin locks.

Spin locks makes the thread "spin", or keep checking a while loop, rather than putting the thread to sleep.

What are the advantages and disadvantages of spin locks?

Advantages

- Does not have any system overhead since the threads are not being put to sleep

- Easy to implement, can be used in small sections that take a short amount of time.

Disadvantages

- Spin locks do not enforce fairness, whichever thread unlocks it can use it. There is no FIFO queue.

- Clock cycles are wasted since the threads do not do anything besides "spin".

What is the difference between calling yield() in a spin lock versus nothing?

If we decide to call pthread_yield(), we are checking the condition once, then devoting the rest of our clock cycles to other processes. There is no need for the thread to constantly check the condition of the lock, it can do so on the next quantum. Thus, if we use the yield command, the thread that has the lock can complete more work, which produces a quicker overall time. If we do not call yield, the threads that do not have the lock waste clock cycles by constantly checking the status.

Do threads get duplicated when calling fork()?

Threads that have been created with pthread_create() are not duplicated except if it is the thread calling fork. (In Solaris they are duplicated however, but who cares about Solaris?)

Ex: In UNIX, if we create 5 threads using create() then call fork(), the child will only get one thread so we have a total of 6 threads.

What is a race condition?

A bug related to having multiple threads modifying a data structure simultaneously. Race conditions are difficult to debug.

What are semaphores?

Semaphores are a generalization of mutexes. Semaphores allow a maximun number of threads between a sema_wait and sema_post. The semaphore is initialized with a counter that is greater than or equal to 0.

When do semaphores wait?

When sema_wait is called, the count value is decremented by 1. If that new value is less than 0, then wait is called.

What are the three different use cases of semaphores?

Mutex: Initial counter = 1

N Resource: Initial counter is n > 1.

- If you have access to 5 printer with n=5, the 6th computer will need to wait.

Wait for event: Initial counter = 0

- All threads that call wait will block until the sema_post is called

Review the examples on the slides for bounded buffers, semaphores, read/write locks, and mutex locks.

May be important!

What are read/write locks?

They are locks for data structures that can be read by multiple threads simultaneously, but can only be modified by one thread at a time. They are fair but may suffer from starvation of writers.

What is deadlock?

It happens to one or more threads will have to block forever because they have to wait for a resource that will never be available. When a deadlock happens, the process will need to be killed.

What is starvation?

Starvation happens when a thread may need to wait for a long time before a resource becomes available.

How to prevent deadlocks?

Assign an order to the locks (m1, m2, ...). When we need to hold mutex lock mi, mj, where i < j lock the mutex mi and then mj.

Ex: If m1 and m3 have to be locked, lock m1 before locking m3. Note: order of unlocking does not matter.

See slides for more examples.

How is synchronization implemented in Java?

Java uses they keyword synchronized to denote atomic sections, no need for explicit calls to lock or unlock. Any Java object can also hold as a lock.

What are the different type of calls you can make on the lock object in Java?

object.wait() - The caller will wait until another thread calls notifiy/notifyAll.

object.notify() - Wake up one thread waiting.

object.notifyAll() - Wake up all threads waiting.

What are the different time components of a program (from the time command)?

User Time - Time spent in user mode

System Time - Time spent in Kernel mode

Real Time - Wall clock time.

What is the equation relating User time, System time, and Real time in a multiprocessor machine?

User time + system time < N * Real Time

(where N is the number of processors).

What are parallel computer systems?

These are systems in which there are more than 1 CPU in the same computer. Called SMP, or Symmetric Multiprocessing, each CPU runs a copy of the OS. If tasks are independent, a task that takes T seconds with 1 CPU now takes T/N. [but this is rarely the case since some instructions may have to be executed in order].

These are expensive however, cost is O(n^2) with number of processors.

Ex: Database servers

What is a cluster computer system?

A cluster is a collection of inexpensive computers connected through a fast network. The cost is linear [O(n)], which is an advantage over parallel systems. They are also more robust, since individuals can be serviced without affecting the system as a whole.

They do suffer from slow communication across nodes however. (Parallel systems are faster in this regard).

What are some examples of cluster computer systems?

The best example is the cluster that Google utilizes, since they leverage millions of computers distributed in different locations. Another example is rendering farms, which are used to create animated movies.

What is a grid computer system?

A collection of inexpensive computers across the internet running the same application to accomplish a collective task. People donate idle time of there CPU to be used on the grid.

Ex: SETI@home, BitTorrent

First Midterm Review!

Slide 478

What is the internet a collection of?

The internet is a collection of Networks, Routers interconnecting networks, and Hosts connected to networks.

How is the internet layered?

It reflects the layering used by the TCP/IP protocols.

Application [HTTP]

Transport [Prog to Prog, TCP and UDP]

Internet [Port Forwarding, IP]

Network Interface [LAN, Ethernet]

Physical [Basic HW]

What are the fundamentals of an IP Address?

As a whole, it is an abstraction to hide the network internals. It is independent from HW addressing.

It contains 32 bits, and there is a unique value for each host.

Important: An IP address does not specify a specific computer, but rather a connection between a computer and a network.

What are the two parts of an IP Address?

The prefix identifies a network

The suffix identifies the host in the network

What is a subnet mask?

A subnet mask is a parameter in the interface that tells the number of bits used for the network number.

What is a routing table?

A routing table lists the routes to particular destinations. The operations used to be manual when networks were small and static, but now it is done automatically and is required for larger networks.

Example on Slide 498

Review and re-watch lecture?

What is a packets "time to leave"?

It is the max time that a packet is allowed to be in a loop. The value starts at 255 and decrements after every router hop. If the count hits 0, the packet is discarded. This ensures that there are not endless packets floating around.

What is Address Resolution Protocol (ARP)?

When the router needs to deliver a packet directly, it is required to convert the IP to a hardware address. ARP does this translation.

What is stored in an ARP table/cache?

The cache (or table) stores a key value pair consisting of (IPAddr, EtherAddr) after the IP address has been resolved into a hardware address. This table is built as needed, and the values stay in the table for a set amount of time.

If the value is not in the table, it is required to broadcast across the network and ask to see what location is needed.

What is a DNS?

DNS is a service that translates host names to IP addresses. They use a lookup algorithm and contacts as many servers as necessary. (the cache is used to minimize lookup times however).

Host names are divided into domains:

host.dom2.dom1.dom0

ector.cs.purdue.edu

The most general domain is to the right, the most specific to the left.

What is Dynamic Host Configuration Protocol (DHCP)? What are the four components?

Allows connecting computers to the Internet without the need of an administrator. The four components are...

Local IP Address - Current Address

Subnet Mask - Used to send packets in same LAN

Default Router - Used to send packets outside of LAN

DNS Server - Used to convert the names to IP Addresses.

What are the two transport protocols?

The two available in the TCP/IP family are...

UDP - User Datagram Protocol

TCP - Transmission Control Protocol

What is UDP? What are some of the use cases?

User Datagram Protocol

Cons: Unreliable transfer, application will need to implement own reliability.

Pros: Benefits are minimum overhead in computation and communication. No initial setup is needed, just send and go.

Uses: LAN Applications, VOIP

How are messages sent in UDP?

UDP is message oriented. Each message is encapsulated in an IP datagram. The size is restricted by the Maximum Transfer Unit (MTU) of the network (MTU = 1500bytes for Ethernet).

The header has ports that identify source and destination.

What is TCP? What are the defining characteristics?

It is the major transport protocol used in the internet. It is...

Reliable - Uses acknowledgements and retransmission.

Connection-Oriented - An initial connection is required, both endpoints keep state.

Full-Dupex - Communication can happen in both ways simultaneously.

Stream Interface - Transfer of bytes looks like reading/writing files.

How does TCP achieve reliability?

It used acknowledgements and retransmissions.

What is an acknowledgement?

The receiver sends an acknowledgement when the data arrives.

What is a retransmission?

The sender starts a new timer whenever the message is transmitted. If the timer expires before an acknowledgement arrives, the sender retransmits the message.

What are the six important features of TCP?

1. Adaptive Retransmission

2. Cumulative Acknowledgements

3. Fast Retransmission

4. Flow Control

5. Congestion Control

6. Reliable Connection and Shutdown

What is Adaptive Retransmission?

This allows TCP to work in both slow and fast networks. The retransmission timer is set dynamically, using the equation...

RTT + 4*RTTSTDDEV (where RTT is the round trip time in that network).

This allows for the optimal time and timeout, so the correct amount of packets is retransmitted.

What is cumulative acknowledgments?

These are acknowledgements for all bytes received so far without holes (independent of packets).

What is fast retransmission?

It is a heuristic where a duplicated acknowledgement for the same sequence is signal of a packet lost. The data is then retransmitted before the timer expires.

What is flow control?

It slows down the sender if the receiver is running out of buffer space. The buffer space, or window, is sent every acknowledgement.

What is congestion control?

For TCP a lost packet is a signal of congestion. Instead of aggressively retransmitting, it will fisrt "slow start" and then a "congestion avoidance" where the window (buffer) of retransmittied data is reduced in size.

What is reliable connection and shutdown?

TCP uses a Three way handshake to close connections. Three packets are enough to make sure that lost packets will not interfere with future connections.

When should you use UDP?

Since UDP is unreliable, it should only be used in certain situations. Broadcasting (contacting all computers on LAN), Realtime Data: VOIP, Teleconferencing, any application where minimum delay is more important.

What is a Network Address Translation (NAT)?

A NAT is used when you want to connect multiple computers to the Internet using a single IP address. From the POV of the internet, all computers have the same address (which points to the NAT box).

What are the benefits of using a NAT?

As a side effect, NAT provides protection. The NAT is also called a Firewall, since packets will only be allowed in if that connection was started from inside the NAT.

How is a TCP connection uniquely defined?

It is defined by four values.

How does a NAT box work? What are the steps?

Review the examples of NAT box on the slides!

What are the different types of server concurrency?

Iterative

Fork Process

Create New Thread

Pool of Threads

Pool of Processes

What are relational databases? How are they constructed?

Relational databases store the information in tables. A table is made of rows and columns, where one row stores a record and a column stores an attribute of that record.

What is Structured Query Language (SQL)?

SQL is the standard language used to manipulate databases.

What are the three different SQL databases? Why are they used?

MySQL -> Free/Popular

Orace -> Enterprise

Microsoft SQL -> Microsoft product integration

What is a primary key?

One or more of the columns in the table can be dedicated as a primary key. The value is recommended to be unique, and a "B-tree" (like 2-3, but can have many children) is uses to search [O(log(n)) time].

How to select in SQL?

SELECT * FROM Books (will return all rows from Books table)

SELECT Price, Title FROM Books (return a table with only the price and title).

What does the WHERE feature do in SQL?

WHERE will put constraints on your query. Ex: WHERE Price <= 29.95 will only return entries that are less than 29.95 in price.

What does % and _ mean in SQL?

% -> Zero or more characters

_ -> any single character

How do you update entries in SQL?

UPDATE table SET Price = 10 ..., use the UPDATE command by first specifying the table and then selecting which fields to update.

How do you delete entries in SQL?

DELETE FROM table WHERE Title Like "%C++%", this deletes all entries in Books that contain C++ in their title.

How do you add a new entry into a SQL database?

Use INSERT to insert a new row in the table.

INSERT INTO Books VALUES(...). This creates a new entry with the values defined.

Who is Joel Spolsky?

Joel is a software developer who has written several books on software engineering. He created Stack Overflow.

What are the main components of Joel's test?

1. Source Control

2. Easy

3.Daily Build

4. Bug DB

5. Fix Bugs before new code

6. Up to date schedule

7. Project spec

8. Quiet Working conditions

9. Best tools

10. Testers

11. Code during interview

12. Hallway usability testing

What is Extreme (XP) Programming?

It is a practical methodology for software development. It gives a list of rules that have been successful, encourages iterative approach.

When should XP programming be used?

It is for projects that have some risk of completion (design changes continuously). Best for small groups, but requires good communication.

What is source control?

Source control will allow multiple developers to modify the same source code. It keeps track of changes, so you can always revert.

What are some of the different source control programs?

CVS (oldest)

SVN (rewrite of CVS, central repo)

Mercurial (Distributed, no need for central repo)

GIT (Distributed, fast)

What are some of the uses of source control?

Keep track of changes for multiple programmers, easy merging, go back in time, backup, peer review changes

How does centralized source control work (like SVN)?

There is one central repository that users can either push or pull from. There is only this location, all history is stored there.

How does distributed source control work?

There is no central repo, rather each programmer will have a local one. They can exchange changes without the need for a central repo.

How does Centralized vs Distributed Source Control compare?

Both work, but Distributed is better for when code needs to be worked on for a long time without submitting common code.

Why are tests important?

They are the most practical way to improve the quality of a program.

Who writes the tests?

Programmers write tests to verify software works as expected, tests the inner workings.

QA team tests like a black box and is independent from the development.

What are unitests?

Unitests are a group of tests that specify a specific class. Every class should have unitests, written by programmers.

What are system tests?

They test a specific subsystem of the product, can involve multiple classes. Written by programmers and QA.

What are regression tests?

These are tests written to reproduce a bug and also verify the bug has been fixed. Add to lists of overall tests to run, and run after every build. Written by QA and programmer.

What are acceptance tests?

These tests evaluate the software before a release. The tests tell if the product is ready for prime time or not. Written by QA.

When should tests be run?

After writing and committing new code, during the daily build. This will ensure new code does not break everything [but it is expected that it will].

Should we track bugs?

Yes! Tracking bugs is crucial to the success of a program.

What is the bug cycle?

1. Create a bug report

2. Manager assigns priority and severity.

3. Assign the bug to programmer.

4. Analyze and estimate time.

5. Fix bug and create regression tests.

6. Submit code for review.

7. QA ensures that it is fixed.

8. Close bug.

Why is refactoring important?

Very seldom will you start code from scratch. It is important to read and maintain code.

What are some things that should be refactored?

Duplicate Code, Large Class, Inconsistent Naming, Dead Code, Too General.

What is a software pattern?

They are reusable design solutions to reoccurring problems. They are modeled after architectural design.

What is synopsis, context, and forces for the proxy pattern?

S: Forces method call to an object to occur throgh a proxy object.

C: Proxy may give the illusion that the object is local, when really it is on a remote machine (can act as a logger or cache).

F: We want to add functionality to an object without modifying the object.

What is the solution and consequence of the proxy pattern?

S: Both proxy and service-providing object can inherit from a common class, or implement a common interface.

C: Service-providing object is used transparent to the object.

What is synopsis, context, and forces for the command pattern?

S: Encapsulate commands in objects so you can control sequencing, can undo or manipulate.

C: Graphics editor, want to undo a command. You can remove it from the list and play all other commands before it.

F: Need undo/redo management, can be stored for future testing or recovery.

What is the solution and consequence of the command pattern?

S: Create an abstract interface with do() and undo() methods. Have command objects implement abstract interface. Command manager stores commands in queue and does operations.

C: Flexibility and replay commands at any time.

What is synopsis, context, and forces for the observer pattern?

S: Allow to dynamically register dependencies between objects, so when one changes, the other is notified.

C: You have a directory viewer, need listener. You have a button in a GUI, register a listener. (e.g. Swing or GTK).

F: An instance of one class needs to notify an instance of another.

What is the solution and consequence of the observer pattern?

S: Implement a Listener abstract class, the observer implements this interface and registers itself as a listener of the observable object.

C: Cyclic dependencies may arise.

What is synopsis, context, and forces for the visitor pattern?

S: When you need to do operations in a complex structure, you can separate the operations from the structure by using a visitor class.

C: Want to separate the way a collection is implemented from they way you iterate over it (e.g. Iterator).

F: There are a variety of operations that need to be performed on that structure.