scheme | 作业project | RAID – UMass Boston CS 444

UMass Boston CS 444

scheme | 作业project | RAID – 这是一个RAID 的practice, 考察RAID 的理解, 涵盖了RAID 等方面, 这是值得参考的project代写的题目

scheme代写 代做scheme

project 3

1 Introduction

This project develops RAID 2 encoding and decoding capabilities for Minix based on the Ham- ming(7, 4) code. RAID 2 is described in Chapter 5 of the textbook. Hamming(7, 4) code is described in the Hamming code notes for the class on March 3. Briefly, RAID 2 splits every nibble of a file into four data bits and adds three parity bits. Thus, a nibble is encoded as seven bits: P1, P2, D1, P4, D2, D3, and D4. The P1 bits of all nibbles in the file are concatenated and stored in one disk drive; similarly for the other six bits. Should one drive fail, Hamming(7, 4) code can detect and correct the error. For this project, however, we are not going to use seven real drives. Instead, we use seven files to keep the seven parts of an encoded file. Typically we write the least significant bit on the right and the most significant bit on the left. Hamming code uses the reverse orientation. This endianness is critical to successful encoding, decoding, and error correction. Lets illustrate with an example. Consider a file of four bytes of the ASCII code of abcd: 0x61, 0x62, 0x63, and 0x64. The eight nibbles of the file are 0x61626364. The following table lists the corresponding Hamming(7, 4) bits.

nibble P1 P2 D1 P4 D2  D3 D
6 1 1 0 0 1 1 0
1 1 1 0 1 0 0 1
6 1 1 0 0 1 1 0
2 0 1 0 1 0 1 0
6 1 1 0 0 1 1 0
3 1 0 0 0 0 1 1
6 1 1 0 0 1 1 0
4 1 0 0 1 1 0 0
0xEF 0xFA 0x00 0x51 0xAB 0xBE 0x

Consider the row for the nibble 3, the third from the bottom. In binary, 3 is 0011 2 , where the two 1s occupy the less significant half of the nibble. However, in the scheme of Hamming code, they are the data bits D3 and D4, corresponding to the more significant half. With this table, the original four bytes are encoded as seven bytes. We read the columns top-down note this endianness. Column P1 is 11101111 2 , which is 0xEF in hexadecimal. The tasks for this project are to write two C programs. The first program shall be named raid.c. It encodes one file into seven files. It is run like this:

minix# ./raid -f xyz

It creates seven files:

xyz.part xyz.part xyz.part xyz.part

xyz.part xyz.part xyz.part

These files store the bits of P1, P2, D1, P4, D2, D3, and D4, in that order. The command-line option-f filenameis a required feature. The second program shall be nameddiar.c. It decodes seven files back to the original file. It is run like this:

minix# ./diar -f xyz -s 16

It looks for the seven filesxyz.part[0-6], decodes them, and creates a new file calledxyz.2. The command-line options-f filenameand-s numberOfBytesare required features.

2 Project Tasks

First, create a directory in the VM.

minix# mkdir /root/proj

Next, copy five files from the instructors directory to the VM.

mic$ scp -P 2213 /home/ming/444/proj3/* root@localhost:~/proj

The files are the following.

-rw-r–r–. 1 ming 5694080 Mar 6 17:22 completeShakespeare.txt -rwxr-xr-x. 1 ming 7755 Mar 6 17:22 diarMing* -rw-r–r–. 1 ming 107 Mar 6 17:22 Makefile -rwxr-xr-x. 1 ming 7749 Mar 6 17:22 raidMing* -rw-r–r–. 1 ming 16 Mar 6 17:22 test.txt

The two text filescompleteShakespeare.txtandtest.txtwill be used to test your programs. TheMakefilecan be used to compile. The two executablesraidMinganddiarMingare compiled from the instructors code. Although they are ELF executables, they run on Minix only you will get error messages if you try to run them on MIC.

2.1 Task 1: to RAID

You can runraidMingand see its output.

minix# ./raidMing -f test.txt minix# ls -l minix# ./raidMing -f completeShakespeare.txt minix# ls -l

Your task is to write your ownraid.cthat encodes RAID 2. It accepts the command-line option -f filename.

2.2 Task 2: from RAID

You can rundiarMingand see its output.

minix# ./diarMing -f test.txt -s 16 minix# ls -l minix# ./diarMing -f completeShakespeare.txt -s 5694080 minix# ls -l

Note that the sizes of these two test files are multiples of eight. Thus, the last bytes of the RAID files are filled with real data bits. If the size is not a multiple of eight, there will be trailing non-data bits, which must be ignored. However, you are not expected to handle this scenario assume the sizes of all test files are multiples of eight. You can verify that the restored files are identical to the originals.

minix# diff test.txt test.txt. minix# diff completeShakespeare.txt completeShakespeare.txt.

There should be no output from thediffcommand. When there are no failed drives, we can use just parts 2, 4, 5, and 6 to reconstruct the original file. RAID 2 can perform error correction when one drive fails. The techniques for error detection and correction are described in the notes for the class on March 3. You can test error correction by deliberately corrupting a RAID file. For example,

minix# cp completeShakespeare.txt completeShakespeare.txt.part minix# ./diarMing -f completeShakespeare.txt -s 5694080 minix# diff completeShakespeare.txt completeShakespeare.txt.

There should be no output from thediffcommand. If you want to corrupt a different file, remember to runraidMingagain to restore the corrupted file before you corrupt another RAID 2 can handle only one failed drive. Your task is to write your owndiar.cthat decodes RAID 2 and corrects errors. It accepts the command-line option-f filenameand-s numberOfBytes.

3 Grading Rubric

  • (50 points) Yourraid.ccompiles, and the executableraidcan encode.
  • (50 points) Yourdiar.ccompiles, and the executablediarcan decode and correct errors.