IC221: Systems Programming (SP16)

Home Policy Calendar Resources

Lab 13: Threaded Socket Server

Table of Contents

1 Preliminaries

In this lab you will complete a set of C programs to expose you to the threading library and threaded socket programming.

1.1 Lab Learning Goals

In this lab, you will learn the following topics and practice C programming skills.

  1. Using pthreads to create and join threads
  2. Passing arguments to threads and retrieving return values
  3. Create multi-threaded applications: factorization and socket server

1.2 Lab Setup

Run the following command 

~aviv/bin/ic221-up

Change into the lab directory 

cd ~/ic221/lab/13

All the material you need to complete the lab can be found in the lab directory. All material you will submit, you should place within the lab directory. Throughout this lab, we refer to the lab directory, which you should interpret as the above path.

1.3 Submission Folder

For this lab, all ubmission should be placed in the following folder: 

~/ic221/lab/13/

This directory contains 4 sub-directories; examples, timer, term-status, and mini-sh. In the examples directory you will find any source code in this lab document. All lab work should be done in the remaining directories.

  • Only source files found in the folder will be graded.
  • Do not change the names of any source files

Finally, in the top level of the lab directory, you will find a README file. You must complete the README file, and include any additional details that might be needed to complete this lab.

1.4 Compiling your programs with clang and make

You are not required to provide your own Makefiles for this lab.

1.5 README

In the top level of the lab directory, you will find a README file. You must fill out the README file with your name and alpha. Please include a short summary of each of the tasks and any other information you want to provide to the instructor.

1.6 Test Script

You are provided a test script which prints pass/fail information for a set of tests for your programs. Note that passing all the tests does not mean you will receive a perfect score: other tests will be performed on your submission. To run the test script, execute test.sh from the lab directory. 

./test.sh

You can comment out individual tests while working on different parts of the lab. Open up the test script and place comments at the bottom where appropriate.

2 PART 1: Threaded Socket Server (50 points)

When implementing a socket server that can handle multiple client connections, we run into problems with blocking. First, the server must accept an incoming connection, which blocks, and once the connection is established, reading and writing from the socket is also a blocking operation. All that blocking means that it can be challenging to service multiple client connections.

In class, we saw one way to mitigate blocking by using the select() system call. The relevant portion of the code is duplicated below: 

/* select_server.c*/

//set up a select set to select from
FD_ZERO(&activefds);

//add the server socket to the select set
FD_SET(server_sock, &activefds);

while(1){


  //set current active file descriptors
  readfds = activefds;

  //Perform a selct
  if( select(FD_SETSIZE, &readfds, NULL, NULL, NULL) < 0){
    perror("select");
    exit(1);
  }

  //check for activity on all file descriptors
  for(i=0; i < FD_SETSIZE; i++){

    //was the file descriptor i set?
    if(FD_ISSET(i, &readfds)){


      if(i == server_sock){
        //activity on server socket, incoming connection

        //accept incoming connections = NON BLOCKING
        client_sock = accept(server_sock, (struct sockaddr *) &client_saddr_in, &saddr_len);

        printf("Connection From: %s:%d (%d)\n", inet_ntoa(client_saddr_in.sin_addr), 
               ntohs(client_saddr_in.sin_port), client_sock);

        //add to active set
        FD_SET(client_sock, &activefds);

      }else{

        //otherwise client socket sent something to us
        client_sock = i;

        //get the foreign address of socket
        getpeername(client_sock, (struct sockaddr *) &client_saddr_in, &saddr_len);

        //clear response buffer
        memset(response, 0, BUF_SIZE);

        //read from client and echo back
        n = read(client_sock, response, BUF_SIZE);

        if(n == 0){
          //client close socket

          //close client sockt
          close(client_sock);

          //deactivate this client socket
          FD_CLR(client_sock, &activefds);


          //LOG
          printf("Client Closed: %s:%d (%d)\n", inet_ntoa(client_saddr_in.sin_addr), 
                 ntohs(client_saddr_in.sin_port), client_sock);


        }else{
          //client sent a message

          //null response for safety
          response[n] = '\0';

          //write message back to client
          write(client_sock, response, n);

          //LOG
          printf("Received From: %s:%d (%d): %s", inet_ntoa(client_saddr_in.sin_addr), 
                 ntohs(client_saddr_in.sin_port), client_sock, response);

        }

      }

    }

  }

}

You'll notice that you must track the current socket file descriptors, continually select from them to check if they are actionable before calling either accept() or read(). While the code is usable, it is not that elegant and can be challenging to write.

Instead, we'd like to use threading to solve this problem. The big idea is that we generalize the actions of the server for each client into a function. Whenever a client connects, the server accepts the connection and passing the client operations over to the handler routine. If that handler routine runs within a thread, then the server can continually just accept incoming connections in the main thread and allow worker threads to service client connections.

2.1 Task 1: threaded_server

For this task, change into the socket-server directory, where you will find four files:

  • threaded_server.c : multithreaded, multi-client socket server, which you will complete
  • select_server.c : select based multi-client socket server, for reference
  • echo_server.c : single thread single-client socket server, for reference
  • Makefile : to compile your program

Your goal is to complete the threaded_server program so that it meets the following specification.

  1. It should create a new thread for every client and echo back all data sent to the server to the client, like echo_server and select_server
  2. It should handle multiple clients simultaneously
  3. The server should provide meaningful output that matches select_server; logging incoming connections, read/writes to sockets, and connection close events.

Below is some sample output from a server with multiple connections, some open and closing: 

>./threaded_server
serer sock listening: (3)
Connection From: 127.0.0.1:56523 (4)
Received From: 127.0.0.1:56523 (4): testing 1
Connection From: 127.0.0.1:56525 (5)
Received From: 127.0.0.1:56525 (5): testing 2
Connection From: 127.0.0.1:56526 (6)
Received From: 127.0.0.1:56526 (6): testing 3
Client Closed: 127.0.0.1:56526 (6)
Connection From: 127.0.0.1:56527 (7)
Received From: 127.0.0.1:56527 (7): testing 4
Client Closed: 127.0.0.1:56527 (7)
Client Closed: 127.0.0.1:56525 (5)
Client Closed: 127.0.0.1:56523 (4)

The starter code for this task is purposely light, but all relevant code is available to you. You're primary task is to determine how to properly parallelize the code for threading.

3 PART 2: Parallel Prime Sieve (50 points)

Prime numbers are vital to many computer science problems, and so quickly finding prime numbers is an important process. There are many fast ways to find and identify primes, and in this part of the lab you will implement a parallel version of, perhaps, the simpilist prime finding routine, the Sieve of Eratosthenes. This routine was discovered in the times of Ancient Greece, it still one of the fastest algorithms today. It can also be trivially paralyzed.

The sieve works as follows. First, starting with smallest prime, 2, all factors of 2 are marked within the range of values we are interested. For example, if we are interested in finding all primes less than 30, we would first mark all factors of 2. 

1 *2* 3 -4- 5 -6- 7 -8- 9 -10- 11 -12- 13 -14- 15 -16- 17 -18- 19 -20- 21 -22- 23 -24- 25 -26- 27 -28- 29 -30-

The next lowest non marked values must be a prime, and then we can mark (or sieve) all factors of that prime. 

1 *2* *3* -4- 5 -6- 7 -8- -9- -10- 11 -12- 13 -14- -15- -16- 17 -18- 19 -20- -21- -22- 23 -24- 25 -26- -27- -28- 29 -30-

We can continue this process until we reach a prime greater than sqrt(30), and then we know all remaining non-marked values must be prime because factors of the value must be less than sqrt(30). The sqrt(30) is about 6 so after marking factors of 5, we've found all the primes 

1 *2* *3* -4- *5* -6- 7 -8- -9- -10- 11 -12- 13 -14- -15- -16- 17 -18- 19 -20- -21- -22- 23 -24- -25- -26- -27- -28- 29 -30-

Now we can identify all non-marked values as prime: 

1 *2* *3* -4- *5* -6- *7* -8- -9- -10- *11* -12- *13* -14- -15- -16- *17* -18- *19* -20- -21- -22- *23* -24- -25- -26- -27- -28- *29* -30-

In this lab, we are interested in identifying the 5 largest values less than a designated value. Here is a implementation (slow_sieve) that will sieve and print the 5 largest values. 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int main(int argc, char *argv[]){

  //print the largest prime less than value

  long top;         //top value to check through

  char * numbers;  //index is the number, value is either
                   // -1 : currently being sieved by a thread
                   //  0 : unchecked value, potential prime
                   //  1 : composite value



  //argument checks
  if( argc >= 2){
    top = atol(argv[1]);
  }else{
    fprintf(stderr, "ERROR: require top value\n");
    exit(1);
  }

  if(top < 3){
    fprintf(stderr, "ERROR: invalid top value, requre >= 3\n");
    exit(1);
  }


  //allocate array of numbers
  numbers = calloc(top,1); 

  long p=2; //prime seiving
  long q;   //a multiple of p
  long i;   //iterator for multiple

  //only need to sieve the bottom sqrt(top) primes
  while(p < sqrt(top)){

    //sieve routine
    for(i=2,q=p*i;q<top;q=p*++i){
      //mark q = p*2,p*3, ... , p*n where p*n < top
      numbers[q] = 1; //mark composite
    }

    //find the next prime to sieve
    while(p<sqrt(top)){
      p++;
      if(numbers[p] == 0) break;
    }

  }

  //working backwards, print the top 5 primes
  long j=0;
  for(i=top-1; i>0 && j < 5 ; i--){
    if(numbers[i] <= 0){
      printf("Larges Prime: %ld\n",i);
      j++;
    }
  }

  return 0;
}

Your goal is to write a threaded parallel version of this routine. The basic idea is that you will create n threads, each will start with a different initial prime and find next primes to sieve based on a shared numbers array. Once the bottom sqrt(top) primes are sieved, the largest primes can be printed to the screen.

Of course, the goal of writing this routine using threads is that it should be faster than the non-parallel version. So you will need to engineer yours to ensure that condition, but just throwing threads at it is not always going to make it faster. You will run some experiments to test the speed.

3.1 Task 2

For this task change into the prime-sieve directory where you will find two files:

  • slow-sieve.c a standard implementation of the prime sieve
  • parallel-sieve.c a parallel version of the sieve for you to complete

The routine for parallelization can be found in the source code. The general idea is that each thread will share a numbers array that is being sieved, where the index represents the number, and the value is the marking. The parallel processing comes from each thread starting with different initial prime. To bootstrap that process, I've hard-coded the first 100 primes.

The arguments to parallel_sieve is 

parallel_sieve top-value [threads]

The default number of threads is 1, and the max number is 100.

Here is some sample output. Note we can use the time function to see how long the routine runs for: 

aviv@saddleback: prime_sieve $ time ./slow_sieve 100000000
Larges Prime: 99999989
Larges Prime: 99999971
Larges Prime: 99999959
Larges Prime: 99999941
Larges Prime: 99999931

real	0m1.248s
user	0m1.236s
sys	0m0.012s
aviv@saddleback: prime_sieve $ time ./parallel_sieve 100000000 2
Largest Prime: 99999989
Largest Prime: 99999971
Largest Prime: 99999959
Largest Prime: 99999941
Largest Prime: 99999931

real	0m0.772s
user	0m1.519s
sys	0m0.008s
aviv@saddleback: prime_sieve $ time ./parallel_sieve 100000000 3
Largest Prime: 99999989
Largest Prime: 99999971
Largest Prime: 99999959
Largest Prime: 99999941
Largest Prime: 99999931

real	0m0.742s
user	0m2.171s
sys	0m0.008s
aviv@saddleback: prime_sieve $ time ./parallel_sieve 1000000000 3
Largest Prime: 999999937
Largest Prime: 999999929
Largest Prime: 999999893
Largest Prime: 999999883
Largest Prime: 999999797

real	0m8.312s
user	0m24.662s
sys	0m0.064s

Additionally, in the README file you are required to answer questions and run some experiments with your parallel sieve: 

  a) For just 2 threads, at what top value do you start to see
  improvements for your parallel sieve over the slow sieve?

  b) For finding the top primes less than 1000000, how much faster is
  your parallel sieve (2-threads) compared to the slow sieve? (Use the
  average across 5 runs)

  c) For finding the top prines less than 1000000, what is the optimal
  number of threads for the fastest resuts on a lab computer? Fill in
  the table below, and come up with a *conclusion and explanation*.


  *** EXPLANATION ***
 (DON'T FORGET TO FILL ME IN)
 

                             Runs
          .........................................................  
  Threads |    1   |    2    |   3    |    4   |    5   |   AVG   |
----------|--------|---------|--------|--------|--------|---------|
    2     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    3     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    4     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    5     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    6     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    7     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    8     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
    9     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
   10     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
   20     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
   40     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
   60     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
   80     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|
  100     |        |         |        |        |        |         |
----------|--------|---------|--------|--------|--------|---------|