program代做、代写c/c++程序设计

日期：2024-05-17 10:59

Project 3: Design and Implementation of File System

April 16, 2024

1 Objectives

1. Design and implement a basic disk-like secondary storage server.

2. Design and implement a basic ffle system to act as a client using the disk services provided by

the server designed above.

3. Study and learn to use the socket API. Sockets are used to provide the communication mechanism

between (i) the client processes and the ffle system, and (ii) the ffle system and the disk storage

server.

2 Problem Statement

This project will be developed in several steps to help you understand the concepts and encourage

modular project development. You must adhere to the speciffcations given below. To share your

experiences effectively, you are recommended to keep a record of your insights during the coding. This

includes writing down any challenges encountered or bugs costing you a long time for debugging. By

doing so, you’ll avoid forgetting the details of your experiences when writing the report.

Step 1: Design a basic disk-storage system

Description: Implement, as an Internet-domain socket server, a simulation of a physical disk. The

simulated disk is organized by cylinder and sector.

• You should include the seek time in your simulation to account for track-to-track time (using

usleep(3C), nanosleep(3R), etc). Make the seek time a value in microseconds, passed as a

command-line parameter to the disk server program.

• You should accept the number of cylinders and the number of sectors per cylinder from command

line parameters. Assume the sector size is ffxed as 256 Bytes.

• Your simulation should store the actual data in a real disk ffle, so you’ll need to accept a fflename

for this ffle as another command line option.

Hints:

1. You may ffnd that the mmap(2) system call provides you with the easiest way of manipulating

the actual storage. However, you are allowed to use ffle and ffle API to simulate the storage

representing your disk.

12. Given the challenges of socket programming, we have provided some functions. Please refer to

the code template provided on Canvas for how to use these functions. If you believe there are

bugs in the provided code, please contact the TA on time.

The Disk Server: The server should be able to understand the following commands and give

corresponding responses:

• I: Information request. The disk returns two integers representing the disk geometry - the number

of cylinders, and the number of sectors per cylinder.

• R c s: Read request for the contents of cylinder c sector s.

– The disk returns Yes followed by a whitespace and those 256 bytes of information, or No

if no such block exists.

– Hint: This will return whatever data happens to be on the disk in a given sector, even if

nothing has ever been explicitly written before.

• W c s l data: Write a request for cylinder c sector s. l is the number of bytes being provided,

with a maximum of 256. The data is those l bytes of data.

– The disk returns Yes to the client if it is a valid write request (legal values of c, s, and l),

or returns a No otherwise.

– In cases where l < 256, the contents of those bytes of the sector between byte l and byte

256 are undeffned, use zero-padded contents.

Hints:

1. The data format that you must use for c, s, and l above is a regular ASCII string, followed by

a space character. So, for example, a read request for the contents of sector 17 of cylinder 130

would look like R 130 17.

2. Strings are not equivalent to byte arrays: in a string, 0 represents the end of the string, but

this is not the case in a byte array. Besides, many bytes cannot be printed as visible characters.

Therefore, DO NOT use functions like strlen() or printf() on the data. The disk server will

not interact with users directly, so writing raw bytes to the ffle descriptor is acceptable.

The Disk Client: The client that you write here is mostly for the unit testing of the disk module.

The actual front-end user of this “disk” will be the ffle system implemented in the later steps. The

client should work in a loop, having the user type commands in the format of the above protocol, send

the commands to the disk server, and display the results to the user. Besides, you need to deal with

ASCII invisible characters. For example, add a command that prints data in binary or hexadecimal.

Otherwise, it would be difffcult to debug your disk server without such a debugging tool.

Command line:

a) Server:

./BDS <DiskFileName> <#cylinders> <#sector per cylinder> <track-to-track delay> <port=10356>

b) Client:

./BDC <DiskServerAddress> <port=10356>

2Figure 1: File System Architecture

Step 2: Design a basic ffle system

Implement an inode ffle system. The ffle system should provide operations including:

• Initialize the ffle system

• Create a ffle

• Read data from a ffle

• Write the given data to a ffle

• Append data to a ffle

• Remove a ffle

• Create directories

To provide the above ffle-like concepts, you need to operate on more than just the raw block

numbers that your disk server provides to you. You need to keep track of which blocks of storage are

allocated to which ffle, and the free blocks available on the disk.

Free space management involves maintaining a list of free blocks available on the disk. Two

alternative designs are suggested: a bit vector (1 bit per block) or a chain of free blocks. Associated

with each block is a cylinder# and sector#. “Writing to a ffle” is converted to “writing into a disk

location identiffed by (cylinder#, sector#)”. All this information should be stored on the disk, as the

ffle-system module in the memory is not persistent, and it could be shut down and restarted with data

lost.

The ffle system needs to support ffles of at least 16 KB in size, and fflenames must be at least 8

Bytes long.

Implement this ffle system server as another UNIX-domain socket server. On one hand, this

program will be a server for one UNIX-domain socket; on the other hand, it will be a client to the disk

server UNIX-domain socket from the previous parts, as shown below.

3The File-system Protocol: The ffle system server should be able to accept and respond to the

following commands.

• f: Format. This will format the ffle system on the disk, by initializing any/all of the tables that

the ffle system relies on.

• mk f : Create a ffle. This will create a ffle named f in the ffle system.

• mkdir d: Create a directory. This will create a subdirectory named d in the current directory.

• rm f : Delete ffle. This will delete the ffle named f from the current directory.

• cd path: Change the directory. This will change the current working directory to the path. The

path is in the format in Linux, which can be either a relative path or an absolute path. When the

ffle system starts, the initial working path is “/”. You need to handle “.” and “..” as special

cases.

• rmdir d: Delete a directory. This will delete the subdirectory named d within the current

directory.

• ls: Directory listing. This will return a listing of the ffles and directories in the current directory.

You are also required to return other meta information, such as ffle size, last update time, etc.

• cat f : Catch ffle. This will read the ffle named f, and return the data in it.

• w f l data: Write data into ffle. This will overwrite the contents of the ffle named f with the

l bytes of data. If the new data is longer than the data previously in the ffle, the ffle will be

extended longer. If the new data is shorter than the data previously in the ffle, the ffle will be

truncated to the new length.

• i f pos l data: Insert data to a ffle. This will insert l bytes of data into the ffle after the pos−1

th

character but before the pos

th

character (0-indexed). If the pos is larger than the size of the ffle,

append the l bytes of data to the end of the ffle.

• d f pos l: Delete data in the ffle. This will delete l bytes starting from the pos character

(0-indexed), or till the end of the ffle (if l is larger than the remaining length of the ffle).

• e: Exit the ffle system.

For testing/demonstration purposes, you need to implement a command-line client, similar to the

one that you wrote for the disk server in Step 1. The ffle-system client should work in a loop, allowing

the user to type commands in the format of the above protocol, send the commands to the ffle server,

and display the results to the user.

Hints: We suggest following the below steps to implement your ffle system:

• Implement an in-memory ffle system, reading commands via STDIN, where the data is stored in

memory and disappears after the system reboot.

• Write the data to a raw ffle to achieve the data persistence.

• Implement the ffle system as a server, accepting commands passed through a client.

4• Replace the raw ffle with the disk server implemented in Step 1. This should only require

modifying a few lines of code.

Command line:

a) Disk Server:

./BDS <DiskFileName> <#cylinders> <#sectors per cylinder> <track-to-track delay> <port=10356>

b) File-system Server:

./FS <DiskServerAddress> <BDSPort=10356> <FSPort=12356>

c) File-system Client:

./FC <ServerAddr> <FSPort=12356>

Step 3: Support multiple users in the ffle system

A real-world ffle system is supposed to store data for more than one user. In this step, you need to

make some changes to your ffle system so that it becomes a multi-user system. The key problem to

solve here is to separate the stored ffles and data for different users. Instead, how to support the

parallel operations by multiple clients is considered in the “Extension 2 - Multi-Clients” in Step 4 as

an optional extension. In other words, in this step, you can safely assume different users only connect

to and access the ffle system in sequential order. One client will ffnish the actions and disconnect

before another client establishes her/his connection and performs actions.

To support the multi-user feature, we ffrst need to design a data structure to store the user information,

which should be stored in the ffle system, instead of memory. Then you need to provide

approaches and interfaces to log into your ffle system, create new users, delete users, etc.

Each user should have her/his home folder, own ffles, and so on. Regarding the ffle access control,

the users can share some ffles with other users, or make ffles only visible to themselves. You need to

design a ffle access protocol to control ffle read/write permissions.

Step 4: Optional extensions

In this step, we provide some optional extra functions to the basic ffle system. Implementing any of

the following functions will help you earn bonus points. Besides, you are encouraged to implement any

other additional functions/optimizations that are useful to your ffle system. Please clearly indicate

the optional functions you have implemented in your ffle system, and demonstrate your extensions

through empirical performance evaluation or qualitative analysis.

Extension 1 - Caching: Reading ffles can be expensive, incurring many I/Os to the (slow) disk.

Imagine an open example: without caching, every ffle open would require at least two reads for every

level in the directory hierarchy (one to read the inode of the directory in question, and at least one to

read its data). With a long pathname (e.g., /1/2/3/ ... /100/ffle.txt), the ffle system would literally

perform hundreds of reads to just open the ffle. To remedy what would be a huge performance issue,

you can use a region in the system memory to cache frequently accessed or important blocks. Similar

to the virtual memory mechanism, strategies such as LRU and different algorithms would decide which

blocks to keep in the cache. Implement a cache in the memory, select your page replacement algorithm

5for the cache, and share your design and performance evaluation (e.g., how many times you have

accelerated your file read operations?)

Extension 2 - Multi-clients: You have supported multi-users in step 3 which mainly focuses on

separating the user folders/files and user account management. Another thing you can do is to support

more than one user to use the file system at the same time. That means your file system server should

support parallel requests from multiple clients. Different from the shell problem in Project1, here we

have more challenges when more than one user logs in to your file system. For example, user A wants

to write a file, while user B wants to read the same file. There is a read/write conflict. You can

come up with a solution to solve this conflict. There are still some other problems like this. It’s really

difficult to handle all such synchronization situations, so we encourage you to try your best to consider

as many issues as possible and explain your solutions in the report.

Extension 3 - Journaling: Consider the crash-consistency problem, that is, how to update persistent

data structures despite the presence of a system crash. The system may crash or accidentally

power off between any two writes, and thus the on-disk state may only partially get updated. After the

crash, the system boots and wishes to mount the file system again. Given that crashes can occur at

arbitrary points through time, how do we ensure the file system keeps the on-disk image in a reasonable

state? Many modern file systems use the idea of journaling (also known as write-ahead logging), where

a sequence of updates is treated as a single indivisible unit (called transaction), ensuring that either

all of the updates are committed to the disk, or none of them are. Try to implement a journaling and

transactions mechanism in your file system.

3 Implementation Details

In general, the execution of the programs above is carried out by specifying the executable program

name followed by the command line arguments.

• Use Ubuntu Linux and GNU C Compiler to compile and debug your programs. GCC-inlineassembly

is allowed.

• See the man pages for more details about specific system or library calls and commands: sleep(3),

gcc(1), mmap(2), usleep(3), nanosleep(3), etc.

• When using system or library calls you have to make sure that your program will exit gracefully

when the requested call cannot be carried out.

• One of the risks of experimenting with forking processes is leaving unwanted processes hanging

which wastes system resources. Please make sure that each process/thread is terminated cleanly

when the program exits. A parent process should wait until all its child processes finish, print a

message, and then quit.

• Your program should be robust. If any of the calls fail, it should print an error message and exit

with an appropriate error code. Please always check for errors when invoking a system or library

call.

• Please ensure that your program can work correctly with the tests we provided and exit properly.

64 Material to be submitted

• Create a folder named Prj3_studentID that includes your source codes, Makefile, and report.

Use meaningful names for the files so their contents are recognizable. Then compress the folder

into a file named Prj3_studentID.tar, ensuring that only the folder itself is included in the tar

file.

• You are not required to submit the executables. Make sure your programs can be compiled with

the Makefile before the submission.

• Enclose a README file that lists the files you have submitted along with a one-sentence explanation.

Call it README.md.

• Please state clearly the purpose of each program at the start of the program file. Add comments

to explain your program.

• Test runs: You must show that your program works for all possible inputs. Submit online a

single typescript file clearly showing the working of all the programs for correct input as well as

a graceful exit on error input. Call it test.md or test.pdf.

• Submit a short report to present the analysis. You can also write down important methods and

observations you find useful when finishing your project. Call it report.pdf.

• We provide a code template for this project. Here’s how the file structure looks (you can feel

free to add other files you need):

Prj3 52202191xxxx

Makefile

README.md

report.pdf

test.md

step1

BDS.c

BDC.c

Makefile

step2

FS.c

FC.c

Makefile

step3

Makefile

...

step4

Makefile

...

• Submit your Prj3_StudentID.tar file on Canvas.

• Due date: 23:59 on May. 31, 2024.

• Demo slots: Around June 1, 2024. Demo slots will be posted later on a shared document.

Please sign up for one of the available slots.

7• You are encouraged to present your design of the project optionally. The presentation time is

16:00-17:40, June 4, 2024 (Course meet time of the 16th week). Please pay attention

to the course website.

8