代写program、代做Python/Java设计程序

日期：2024-03-28 11:01

Motivation

Virtual memory provides memory for processes above the limit of physical

memory in a computer by swapping unused pages to a secondary storage

device, such as a disk (mechanical or solid-state). This type of hierarchical

memory is also used for CPU instruction caching and in database systems. In

this assignment, you will explore some aspects of constructing hierarchical

memory structures by building a simulation, and then further explore page

replacement algorithms.

Background: Hierarchical Memory

In the context of computer systems, the term "memory hierarchy" refers to the

organization and structure of various types of memory storage devices within

a computer, arranged in a hierarchy based on their proximity to the CPU

(Central Processing Unit) and their speed, capacity, and cost characteristics.

Memory hierarchy is a crucial concept in computer architecture and plays a

vital role in determining the overall performance of a computer system.

The memory hierarchy typically consists of several levels, each with different

properties:

1. Registers: These are the fastest and smallest storage units directly

accessible by the CPU. Registers store data that the CPU is currently working

on. Data can be read from or written to registers in a single clock cycle.

Registers provide the highest performance but have the smallest capacity.

2. Cache Memory: Cache memory is a small-sized, high-speed memory that

sits between the CPU and main memory (RAM). It stores frequently used data

and instructions to reduce the time it takes to access them. Cache memory is

divided into multiple levels (L1, L2, L3), with L1 being the smallest and fastest,

and L3 being larger but slightly slower. Caches use a mechanism called caching

to manage data movement between levels.

3. Main Memory (RAM): Main memory is the primary storage used to store

data and programs that the CPU is actively using. While it is larger in capacity

compared to cache memory, it is slower in terms of access times. Data must be

moved between main memory and cache when needed. The CPUs memory

management unit (MMU) does this automatically.

4. Secondary Storage: This includes non-volatile storage devices like hard disk

drives (HDDs), solid-state drives (SSDs), and optical drives. Secondary storage

provides much larger storage capacity but is significantly slower in terms of

access times compared to main memory. Data from secondary storage must be

loaded into main memory before the CPU can work on it. The virtual memory

subsystem manages the movement of pages from secondary storage to main

memory.

5. Tertiary Storage: This level includes slower and high-capacity storage

solutions, often used for long-term archival and backup purposes. Examples

include magnetic tapes and cloud storage.

The memory hierarchy is designed to optimize the trade-off between speed

and capacity. Data that is frequently accessed is kept closer to the CPU in

faster memory levels (e.g., registers and cache), while less frequently used data

is stored in slower, higher-capacity memory levels (e.g., main memory and

secondary storage). This organization aims to minimize data access times and

maximize overall system performance while balancing cost.

Efficient management of the memory hierarchy is a critical aspect of computer

architecture, and memory hierarchies are designed to ensure that the CPU can

access data and instructions for processing as quickly as possible while

maintaining a balance between cost and performance.

Tasks

Part 1 (30 Points) / Memory Hierarchy Simulation

The tasks below are a simulation and explore hierarchical memory, page faults,

page swapping, and page replacement algorithms. The tasks below explore

only some aspects of the simulation. Subsequent assignments explore

additional details. The assignments are intentionally decomposed to allow for

flexibility and level the effort across all assignments in this course.

You will implement a cache mechanism for a message-oriented data store.

Messages need to be retrieved rapidly but due to the volume of messages not

all of them will fit into main memory and need to be stored in secondary

memory (on disk through the file system).

You may set up the source code in any way you deem reasonable, although we

do expect that you use reasonable software engineering practices, follow

naming conventions, appropriately split code into source files and use header

files as necessary. All code must be written in C.

1. (15 min / 5 pts) Set up a data structure for a "message". The

message must minimally contain a unique identifier, time sent, the

sender (right now that is just some text), a receiver (again, for now,

just some text), content (text), and a flag indicating whether the

message was delivered.

2. (20 min / 10 pts) Write a function create_msg() that creates a new

message with the fields appropriately set and returns a dynamically

allocated message "object". Define arguments and return types as

necessary. You may discuss the design of the function signature and

behavior (but not the implementation) with your peers.

3. (90 min / 35 pts) Write a function store_msg() that stores the

message in a message store on disk. The design of the message

store is up to you, but you should consider how you can quickly

retrieve messages from disk when needed. Define arguments and

return types as necessary and appropriate. You may discuss the

design of the function signature and behavior (but not the

implementation) with your peers.

4. (90 min) / 30 pts) Write a function retrieve_msg() that finds and

returns a message identified by its identifier. You may discuss the

design of the function signature and behavior (but not the

implementation) with your peers.

Part 2 (30 Points) / Caching

Currently, messages are stored on disk (in either a file per message stored in a

folder, or a block per message in a single file). Finding a message therefore

requires access to disk. In this part, you will add a "cache" so that some

number of messages are stored in a paged structure in memory. Your

messages must be a fixed size; the choice of size is yours (but should be a

power of 2, e.g., 256, 512, or 1024 bytes). Of course, part of the message's

bytes are used for "house keeping" such as identification of the sender and the

receiver, time sent, and perhaps priority, whether it is encrypted, etc. Modify

your code from Part 1 as needed.

For testing purposes, a smaller cache and message size is recommended, e.g.,

1024 bytes per message and 16 message cache. Of course, you should adjust

these limits and sizes as you see fit for development and testing.

Having a cache means that every messages that is stored ("sent") is stored in

the cache and also written to disk. When a message is read (found), it should

first be looked for in cache. If the message cannot be found in the cache, the

message needs to be loaded from disk and place in the cache.

Create appropriate lookup data structures to facilitate finding messages in the

cache. In your code, thoroughly describe your strategy and design and why

you chose it. Mention alternative designs and why you did not consider them.

You may discuss your caching strategy and implementation approach with

your colleagues on Piazza, but you may not share code.

Part 3 (20 Points) / Page Replacement

If a message is placed into the cache but no "slot" for a message is open in the

cache, then an existing message in the cache must be replaced. Devise and

then implement two page (a message in our case) replacement algorithms:

1. Random Replacement: a replacement page is chosen at random

2. LRU: the least recently used page is replaced

Part 4 (10 Points) / Evaluation

Design and implement code that will test that the cache mechanism and

calculate the following cache metrics for each page replacement algorithm:

1. number of cache hits per 1000 random message accesses

2. number of cache misses per 1000 random message accesses

3. cache hit ratio per 1000 random message accesses

You need to create a representative message set for testing. You may share

your testing approach, test message mix, and metrics with your colleagues on

Piazza and discuss. You may discuss the calculation algorithms and formulas

and share test messages but not code.

Quality (10 Points)

The remaining points are awarded based on the quality, documentation,

thoroughness, and professionalism of your code.

Simplifying Assumptions, Hints, and Tips

1. You do not need to be concerned about internal fragmentation

within messages.

2. Additional hints and clarifications will be posted on Piazza, so keep

checking Piazza regularly, discuss and participate until the due date.

Submission and next steps

In addition to submitting your code, there are two next steps involved with

grading your practicum: First, we want you to review your own work perform

a self evaluation of you or your team's work. Next, you will have an

opportunity to present your work to us in a review session, where we will take

into account your work, your explanation of design choices and walkthroughs,

and how your self-evaluation lines up with your work.

Here are the next steps:

? Submit a .tar file containing all of your code, notes, explanations,

metrics, and test cases. You may embed everything in your code or

write a separate report. For those working in teams, one

submission per pair is sufficient, but please include a quick note of

the team members in the submission, to help us keep track.

? Schedule time for your review and attend as scheduled