Best online Nursing Writing Service agency

CS 385 –Operating Systems

CS 385 –Operating Systems – Fall 2012
Homework Assignment 2
Sockets and Threads
Due: Monday October 23rd at 3:00 P.M. via Blackboard. Optional hard copy may be turned in to
the TA.
Overall Assignment
For this assignment, you are to write two programs that will communicate with each other using
sockets in a client-server fashion. In addition the clients will use threads. The task to be solved is to
find the longest possible substring of a given search string within a file, and document all of the places
within the file where that longest substring was found. By launching multiple simultaneous clients,
each of which uses multiple threads, the search can be done in parallel, with branch-and-bound
techniques used to speed up the search.
Task and File Interpretation
This program will read in data from a file, ( ranging in size from 40 kB to 20 MB ), and search the data file
for the presence of a given search string.
 The filename will be provided to the server as a command-line argument.
 The data in the file is to be treated as a series of unsigned chars, i.e. a stream of bytes ranging in
value from 0 to 255 each.
 The first 500 bytes are to be ignored, to skip over any possible file headers. ( Read them and ignore
them or better yet, use fseek( ) to skip over them. )
 The next N characters define the string to be searched for, where N is provided to the server as a
command-line argument. ( This is the stringLength argument described below. )
 The remainder of the file is the search stream to be searched for the presence of the search string.
The first byte in the file is considered position 0, so the first byte in the search stream is byte
number 500 + N. ( For any position M that is reported by the clients as a search result, a fseek to
position M in the file should begin reading the found string. )
Server Operation and Details
 The syntax for running the server shall be:
stringSearcher filename [ stringLength ] [ searchLength ]
[ nChildren ] [ nThreads ] [ blockSize ] …
o The filename is the name of a data file to be used for the search.
o The stringLength is the length of the string to search for. Default value 100.
o The searchLength is how much of the data file to search. A value of zero indicates to
search the entire file. Default value 0.
o nChildren indicates how many clients the server should fork off initially. ( Clients can also
be launched independently from the command line. ) Default value 4.
o nThreads indicates how many threads each client should create. A value of zero leaves the
clients single threaded. Default value 4.
o blockSize indicates how big a block the server should feed at a time to each client.
Recommendation is around 10K for significant sized input files, though you may want to
start smaller while testing. Default value 10240.
o You may support additional arguments to appear after the ones shown here, provided they
are well documented in your README file.
 The server shall perform the following tasks:
1. Open the input file, skip the header, and read in the search string.
2. Create a socket and set up to listen for connection requests.
3. If nChildren is greater than zero, fork off children, each of which execs a new client.
( Client processes can also be started independently. )
4. Use select( ) to determine which socket(s) have data available.
 If new connection requests are present, establish new connections ( see below. )
 If new messages have arrived from clients, read the messages and respond
accordingly.
 Respond to requests for work by preparing and writing a new work packet.
 Respond to reported results by reading and processing the reported results.
5. Repeat step 4 as long as there is data left in the input file to process.
6. Close the socket used to set up new connections.
7. Continue to read incoming messages from the remaining sockets until each client has
completed their outstanding work.
 Respond to requests for new work with packets containing a zero-length search
string, ( indicating the client should exit. ) Then close each connection as each
client completes.
8. Report final results to the screen. The “answer” will be the length of the longest substring
found, and the list of locations at which that string was found. Print out also the substring
searched for and the longest substring found. ( Print non-printable characters as numbers,
such as hex pairs A3 4C, etc. )
 Data written from the server to clients will be in the form of “workPacket”s, a defined struct
containing:
 The lengths of each of the following two items.
 The string to be searched for.
 A block of data in which to search.
 The index of the beginning of the block. ( 500 + N + i * blockSize, where i is the index of
which block is being delivered in this work packet. )
 ( You may want to overlap the search ranges slightly, to ensure you don’t miss a
string that would otherwise span a search boundary. )
 The largest substring length that has been found so far. ( Used for branch-and-bound. )
Client Operation and Details
 The syntax for running the client shall be:
searchClient [ portNumber ] [ nThreads ] . . .
 The portNumber is the number of the port used to connect to the server. ( See below. )
 nThreads indicates how many threads each client should create. A value of zero leaves the
clients single threaded. Default value 4.
 You may support additional arguments to appear after the ones shown here, provided they
are well documented in your README file.
 The client shall perform the following tasks:
1. Contact the server to establish a connection.
2. Send the server a request for a new work packet.
3. Read in a work packet, as described above. Exit if the search string length is zero or less.
4. Create a separate vector of ints for each thread to store their results.
5. If threads are being implemented, then launch threads, assigning to each thread a subset of
the search space.
 Otherwise just call the function to do the searching as an ordinary function call.
6. After all threads have completed, assemble the best of the thread results and report it back
to the server in a results packet.
7. Repeat from step 2.
 Data written from the client to the server will be in the form of “requestPacket”s, a defined struct
containing:
 An integer indicating the type of packet – work request, results reporting, or both.
 For results reporting packets add:
 An int for the length of the longest substring found. Use zero if no strings were
found longer than or equal to the longest string previously found.
 An int for the number of such strings found. ( May be zero if none found. )
 N ints for the location(s) where the substrings were found, relative to the beginning
of the file. ( I.e. considering the beginning index delivered in the work packet. )
 You may add additional packet types and/or data fields, provided they are well documented
in your README file.
Thread Function Operation and Details
 The thread function shall accept the following input:
 Two const char * s for the search stream and the location in the search stream where this
thread should begin searching.
 Two ints for the length of the search string and the length of the search stream to search.
 An int for the longest substring found so far ( used for branch-and-bound. )
 A vector of ints ( passed by reference ) in which to store results.
 The return value is an int for the length of the longest substring found, or zero if no substrings were
found of length equal to or greater than the previously found maximum.
 The function checks every position in the search stream, to see if a substring of the search string is
found at that location.
 Since we only care about strings that are longer than or equal to the longest string found so
far ( by this thread or any other ), you can start the search by checking searchString[ 0 ] and
searchString[ maxFound – 1 ] to see if they match against the search stream. If not, skip
and check the next position.
 Otherwise a full check will have to be made to see how long a substring matches at this
position.
 If it is less than the longest found so far, skip and move to the next position.
 If it is equal to the longest found so far, push this position onto the results vector.
 If it is longer than the longest found so far, clear the existing results vector, push this
position, and update the max found to match this found length.
Socket Details
 The server needs to perform the following tasks regarding sockets:
1. Call socket( ) to create a socket for accepting connection requests. The type should be
PF_INET and SOCK_STREAM. ( some other alternatives may also work. )
2. Call bind( ) to bind this socket to a particular port number. You should try numbers in the
range 50000 to 64000. If bind fails, that number may be in use, so try a different one.
3. Call listen( ) to mark this socket as ready to accept connection requests.
( It is recommended to complete the first three steps listed above before forking
children. execlp is a good version of exec for this assignment. )
4. Call accept( ) to create new sockets based on connection requests received on the socket
created in step 2. All further communications with this client will be through the new
socket created by accept( ).
5. Use read( ) and write( ) to communicate with this client via the newly created socket.
6. Note: You can use select( ) to determine which socket(s) have data available to be read.
Note that the data structure sent to select gets modified, so you need to set it up again
before each call to select.
 The client needs to perform the following tasks regarding sockets:
1. Call socket( ) to create a socket for communications with the server.
2. Call connect( ) to request a connection from the server.
 Connect will need to know the name used by the server in the bind( ) step listed
above.
 Connect will fail if the client tries to connect before the server is ready. Check the
return value, and use a busy loop ( with a sleep( 1 ) call in it ) if connect fails with
errno equal to ENOENT.
3. Use read( ) and write( ) to communicate with the server.
Thread Details
 Implementation of threads requires a function with the prototype:
void * functionName( void * );
o The void * is a generic pointer that can point to anything, and in practice is usually type
cast to a pointer to a specific data type, usually a defined struct.
 The call to create ( and launch ) a new pthread is:
int pthread_create( pthread_t * thread_id,
const pthread_attr_t *attr,
void ( ( *functionName ) ( void * ),
void *arg );
o The return value is zero on success, or an error code otherwise.
o The ID of the newly created thread is returned via the passed pointer.
o The attr argument can be NULL to use default parameters, or a pointer to a struct to set
attributes such as scope contention. ( See optional enhancements. )
o The name of the function described above is passed as the third argument.
o The fourth argument is passed directly to the function, generally as a pointer to a struct.
 The call to wait for a thread to complete and get its result status is:
int pthread_join( pthread_t thread_id,
void **statusPointer );
o The return value is zero on success, or an error code otherwise.
o The first argument is the ID of the thread to wait for.
o The second argument returns the function return value via a pointer. ( I.e. you should
declare a void * variable, and pass the address of this pointer variable to thread_join, which
will fill it in with the pointer returned by the function. )
Evolutionary Development
It is recommended that the program be developed in the following order:
1. Develop simple server and client programs that create sockets and establish basic communications.
2. Modify the server to fork off clients as needed. Multiple clients should be simple enough with basic
communications. ( The server does not need to use select( ) at this point. )
3. Develop the search method to be used by the threads. Initially test it with a single client and without
threading. Up until this point you can test with small search strings, possibly ASCII.
4. Start passing real data from the server to the client. Initially you can use a single client and have the
client report the results directly instead of sending data back to the server.
5. Implement multiple threads.
6. Implement proper client-server communications, with defined packets passed in both directions. ( The
server now reports the results of the searching, instead of the client. )
7. Implement multiple clients. The server will now need to use select( ) to poll among all of its sockets.
8. Work out any remaining bugs so that the client-server system correctly solves the overall problem.
9. Optinal Enhancements – See below.
Recommended Input Parameters
o A number of data files have been provided on the web site, of differing sizes and properties.
o A blocksize of PIPE_BUF seems like a good choice of blocksize. ( 4096 on ernie. The blocksize may
need to be slightly smaller than this, so that the entire packet fits within a PIPE_BUF limit. )
Required Output
 All programs should print your name and CS account ID as a minimum when they first start.
 Beyond that, this program should print the results as described above, suitably formatted.
Other Details:
 A makefile is required, that will allow the TA to easily build your program. As always, you are
free to develop wherever you wish, but the TA will be grading the programs based on their
performance on the CS department Linux machines.
 ( The makefile may be omitted if compilation is straightforward, and documented in README. )
What to Hand In:
1. Your code, including a makefile, and a readme file, should be handed in electronically using
Blackboard.
2. The purpose of the readme file is to make it as easy as possible for the grader to understand your
program. If the readme file is too terse, then (s)he can’t understand your code; If it is overly verbose,
then it is extra work to read the readme file. It is up to you to provide the most effective level of
documentation.
3. The readme file must specifically provide direction on how to run the program, i.e. what command line
arguments are required and whether or not input needs to be redirected. It must also specifically
document any optional information or command line arguments your program takes, as well as any
differences between the printed and electronic version of your program.
4. If there are problems that you know your program cannot handle, it is best to document them in the
readme file, rather than have the TA wonder what is wrong with your program.
5. A printed copy of your program, along with any supporting documents you wish to provide, ( such as
hand-drawn sketches or diagrams ) should be handed in at the beginning of class on the date specified
above.
6. Make sure that your name and your CS account name appear at the beginning of each of your files.
Your program should also print this information when it runs.
Optional Enhancements:
It is course policy that students may go above and beyond what is called for in the base assignment if
they wish. These optional enhancements will not raise any student’s score above 100 for any given
assignment, but they may make up for points lost due to other reasons. Note that all optional
enhancements need to be clearly documented in your readme files. The following are some ideas, or
you may come up with some of your own:
 The substrings defined here are all anchored at the beginning of the search string. Relaxing this
constraint makes the searching more challenging. ( Actually this is a fairly trivial change. )
 Provide a means for the server to notify clients ( and for clients to notify threads and vice-versa up
the tree ) when a new maximum match length has been found, so that all threads are kept up to date
with the best result found so far.
 Implement timing measurements ( could be the time( ) command from the command line or use
your statsh ), and explore how adjustable parameters affect overall performance. Does parallel
processing and branch-and-bound speed things up over a single process? Or does the interprocess
communications overhead wipe out the potential savings? How does changing the contention
scope change things? One option would be for the “server” to do all the work itself if the number
of children is listed as -1, without implementing sockets or threads, as a base point for comparison.
Another option would be to establish a base point with a separate program, that uses the same
function but does not use any threads or communications.

[Button id=”1″]

WE WRITE ESSAYS FOR STUDENTS

Tell us about your assignment and we will find the best writer for your project

Write My Essay For Me

If you are seeking for fast and reliable essay help, you got on the right page. You can order essays, discussion, article critique, coursework, projects, case study, term papers, research papers, reaction paper, movie review, research proposal, capstone project, speech/presentation, book report/review, annotated bibliography, and more. From now on, you can stop worry and forget about writing assignments: your college papers are safe with our expert writers

STUCK with your assignments? Hire Someone to Write Your papers. 100% plagiarism-free work Guarantee!

PLACE YOUR ORDER