Reference no: EM132411820

CS3103 - Operating Systems Assignment - City University of Hong Kong, Hong Kong

Project - Parallel Zip

I. Project Instructions

Overview - In the earlier programming assignment, you implemented a simple compression tool based on run-length encoding, known simply as czip. For this project, you'll implement something similar, except you'll use threads to make a parallel version of zip. We'll call this version pzip.

There are three specific objectives to this project:

- To familiarize yourself with the Linux pthreads package for threading.

- To learn how to parallelize a program.

- To learn how to program for performance.

II. Project Description

For this project, you will implement a parallel version of zip using threads. First, recall how zip works by reading the description in Assignment 1 (Part II). You'll use the same basic specification, with run-length encoding as the basic technique.

Your pzip will externally look the same as czip. However, internally, the program will use POSIX threads to parallelize the compression process. The general usage from the command line will be as follows:

$ ./pzip file.txt > file.z

Doing so effectively and with high performance will require you to address (at least) the following issues:

How to parallelize the compression. The central challenge of this project is to parallelize the compression process. Think about what can be done in parallel, and what must be done serially by a single thread, and design your parallel zip as appropriate. For example, does it possible to zip several small files using multiple threads instead of a large file using only one thread (czip)? If it's possible, how to divide the large file and merge the zip result of several small files? One interesting issue that the "best" implementations will handle is this: what happens if one thread runs more slowly than another? Does the compression give more work to faster threads? This issue is often referred to as the straggler problem.

How to determine how many threads to create. On Linux, this means using interfaces like get_nprocs() and get_nprocs_conf(); read the man pages for more details. Then, create an appropriate number of threads to match the number of CPUs available on whichever system your program is running.

How to efficiently perform each piece of work. While parallelization will yield speed up, each thread's efficiency in performing the compression is also of critical importance. Thus, making the core compression loop as CPU efficient as possible is needed for high performance.

How to access the input file efficiently. On Linux, there are many ways to read from a file, including C standard library calls like fread() and raw system calls like read(). One particularly efficient way is to use memory-mapped files, available via mmap(). By mapping the input file into the address space, you can then access bytes of the input file via pointers and do so quite efficiently.

To understand how to make tackle these problems, you should first understand the basics of thread creation, and perhaps locking and signaling via mutex locks and condition variables. Review the tutorials and read the following chapters from OSTEP book carefully in order to prepare yourself for this project.

- Intro to Threads

- Threads API

- Locks

- Using Locks

- Condition Variables.

Attachment:- Operating Systems Assignment File.rar