2017/Synch3

From CS61
Jump to: navigation, search

Synchronization 3: Lock Synchronization and Networking

Lock Synchronization

Condition variables

A condition variable is a queue of threads. All threads in the queue are waiting for a wake up call. A condition variable can be initialized with a call to pthread_cond_init.

 pthread_cond_init (pthread_cond_t *cond, pthread_condattr_t *attr)

The wake up call is issued when the condition associated with the condition variable becomes true. You can structure the wake up call to either wake up one or wake all the threads waiting on the condition.

 pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex)

In one atomic step, the pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex) function unlocks the mutex and waits on the condition variable. In the next section, we will study the significance of this atomicity.

 pthread_cond_broadcast(pthread_cond_t *cond)
 pthread_cond_signal(pthread_cond_t *cond)

Upon receiving a signal, the wait function locks the mutex.pthread_cond_broadcast(pthread_cond_t *cond) wakes all of the threads, if there are any that are blocked on the condition variable. pthread_cond_signal(pthread_cond_t *cond) wakes one of the threads.

Sleep/Wakeup Race

 lock(&bbuf->mutex);
 while(&bbuf->empty) { 
   unlock(&bbuf->mutex);         
   wait(&bbuf->nonempty, NULL);   // [1]
   lock(&bbuf->mutex); 
 }
 unlock(&bbuf->mutex);

This code is well synchronized but it is susceptible to deadlock. If a writing thread writes into the buffer, it will signal the '&bbuf->nonempty' condition variable. However, if the reading thread is not yet listening for the condition variable, it will continue to sleep until the next call to write. In other words, if the reading thread has not yet reached point [1] in the code, there will be deadlock.

 pthread_mutex_lock(&bbuf->mutex);  
 while(&bbuf->empty) { 
   pthread_cond_wait(&bbuf->nonempty, &bbuf->mutex); 
 }
 pthread_mutex_unlock(&bbuf->mutex); 

The pthread library resolves this issue by combining the mutex with a condition variable. The resulting synchronization construct is called a monitor. The pthread library performs both the lock and wait instructions atomically.

In both of these code blocks, it is important that &bbuf->empty is accessed in a protected region of code. To prevent unwanted race conditions, all modifications or read accesses to shared states should be protected.

See more here

Networking

Client and Server

The client server model is commonly used to describe network relationships. The client is an active node that sends a request to a server. The server` is a passive node that responds to client requests with a response. The request and response data flows are called streams. The client and server can be the same machine.

Networking Syscalls

 int socket(int domain, int type, int protocol)

The socket() syscall creates a new network file descriptor. However, the resulting socket is not connected anywhere. A set of syscalls is devoted to connecting the resulting socket. These syscalls can be sorted into client and server side buckets.

 int connect(int sockfd, const struct sockaddr *addr, socklen_t addrlen)

The client can connect to a socket using the connect() syscall. This function connects the socket to a destination and will block.

 int bind(int sockfd, const struct sockaddr *addr, socklen_t addrlen)
 int listen(int sockfd, int backlog)
 int accept(int sockfd, struct sockaddr *addr, socklen_t *addrlen)

In the context of the server, the socket can be connected using the bind() syscall, which will associate a passive socket with a port. Once a socket has been connected, the file descriptor is open for both reading and writing. This is different from file descriptor behavior in pipes. The listen() syscall allows the server to start listening for connections from the client. The accept() syscall returns a new file descriptor for the next client and will block.

 int close(int fd) 

The close() syscall will free the file descriptor associated with the socket.

Networking Scheme

For example, the client will execute:

 socket()       // returns 3
 connect(6168)  // port 6168

Meanwhile, the server will execute:

 socket()       // returns 3
 bind(6168) 
 listen() 
 accept(3) 

In this setup, both the client and the server have a socket at file descriptor 3 in their file descriptor tables. The server's call to accept() will block until the client calls connect(). After the client has called connect(), the sever's call to accept() will return a new file descriptor like 4.

Note that the listening socket, file descriptor 3, does not change. This allows the server to listen for multiple clients in one thread and handle client requests in another. If your server only handles one client request at a time, one client will be able to monopolize the server. This is a denial of service (DoS) attack. A DoS attack is when a resource becomes unavailable to other users for a period of time.

Lock Granularity

Servers are intended to communicate with multiple clients. In order to prevent DoS attacks, this means that synchronization and locks are needed.

Lock granularity can be described as either coarse or fine.

  • Coarse granularity is when one mutex protects a lot or state and is easy to implement. However, it is inefficient because there are unnecessary waits because two threads will need to wait on one another even when they are modifying independent states.
  • Fine granularity is when one mutex protects a little state. This is difficult to implement but results in more efficient code. Fine grain locking typically involves locking specific elements of a data structure rather than the entire data structure.

In the wdbclient example shown in class, the database was implemented using hash tables. Coarse granularity only allowed modifying one key in the hashtable at a time because there was one mutex for the whole hashtable. However, each key in the hashtable is independent. Operations on key A should not affect operations on key B. A coarse grain locking scheme that locks the entire hash table will cause operations on A to block on operations on B. A finer grain lock implementation using one lock per bucket will cause operations on key A to be independent of operations on key B.