Date of dispatch of assignment: August 24, 2006

Deadline for submission: September 7, 2006

 

A library maintains the following two tables for books and issuance of books respectively:

 

Book( Title, Section, AccNo )
Issue( RollNo, AccNo, Date-of-issue, Date-of-return )

 

Each book can be uniquely identified by its AccNo, which is an integer. The title of the book is a character string
of fixed size (say 30 characters). The books in the library are arranged in different sections based on the major
discipline under which it may be used -- let us assume that this is coded with two characters, such as CS for
Computer Science, EE for Electrical Engineering, etc. The second table shows us which students have issued which books. All fields in both tables are of fixed length. The two tables are stored in two text files, with one record in each line. For some internal survey, the library wants to find out which students had issued books from which sections. To create this information we decide to compute the join between the two tables, which produces a third
table:

 

NewTable( Section, AccNo, RollNo )

 

What is our task? Our task is to write a program that reads the two tables, Book and Issue, into memory and computes the entries of NewTable. We wish to develop this program as a multithreaded program that divides the task of joining the tables into a given even number of threads (the number of threads is an input to the program). The tables, Book and Issue, may be stored as arrays of structures in shared memory. The parent thread reads
the number of threads, creates that many threads, and distributes the task between them. This distribution
is done as follows. Suppose we partition the records in Book into k partitions and the records in Issue into
q partitions. Then we have kq join subproblems (why?).  The parent must choose k and q in such a way that
kq = n, where n is the given number of threads. A partition may be specified by the index of the first record
and the index of the last record in the partition.

 

How do we collect the results from the participating threads? We want the result (that is NewTable) to appear
in another array of structures (again in the shared memory/global data structure). Note that the number of records of NewTable contributed by each subproblem can be different (why?)

 

Therefore, each thread must compute its assigned subproblem in its own local memory. Next the thread locks (if the variable is free) a global variable (say currIndex, which contains the current index value of the NewTable) to update it and write the computed result in NewTable. While the currIndex is locked, the other threads must busy-wait until it is free.

 

As an example, suppose thread pthread1 wants to write 5 new entries in the NewTable, when it already contains 7 entries. Therefore, before locking,

 

                                          currIndex = 7

 

pthread1 locks the variable and copies 5 new entries from its local memory, into NewTable and before leaving the critical section it updates the variable currIndex. Therefore after unlocking,

 

                                          currIndex = 12

 

 When all child threads complete the writing, the parent thread prints the contents of NewTable and terminates.

 

How do we lock a variable? We may use inline assembly code for SPARC Architecture (refer manual and the class lectures). See the usage of the instruction ‘swap’. This instruction is used to swap the values either between a memory location or a register. e.g. “swap [%0], %%o1”  swaps the values between the memory location (pointed by register %O) and the register %%o1.

 

PS: Note that for computing this result, not all attributes of Book and Issue needs to be read into memory.

Guidelines for submission:

The file name of the C program should be <rollNo>_04.c, it should contain your identity e.g name, roll number, assignment number etc. This file should be available in the subdirectory <roll_number>.oslab e.g. 04cs1048.oslab in your home directory, on or before the last date of report. 

 

 

OS Laboratory Assignment 3

Operating Systems Lab: Assignment 4

 

Computing Join with Threads: