Operating System代写：COMP474 Kernel Memory Management

发表于   |   分类于

模拟内核中的Memory Management部分。

Memory Management

Assignment Overview

  1. Assignment Description
    • Developing a kernel simulator for memory management techniques.
  2. Assignment Goal
    • To understand basic kernel memory management techniques.
  3. Submission instruction
    • Submit (1) a PDF report file and (2) a lab assignment tar file to LearnUS.
  4. Additional Guidelines
    • This is one-person project, and you must work in your own environment.
    • The programming language must be C/C++ or Rust.
      • You can implement your assignment in any of the three programming languages (C, C++, or Rust) that you are most comfortable with, and there is no penalty on which one you choose. No other languages (Java, Python, etc.) are allowed other than the above.
      • The Rust language is a system programming language that was added as a Linux kernel development language in addition to C. Its main feature is memory safety. We will not cover this language in class, so it is only for interested students.
      • The standard library can be used, but the use of other external libraries is not allowed.
      • When compiling from a Makefile, C/C++ must be compiled with gcc and Rust must be compiled with rustc.
    • The assignment is done in a Linux environment. You are free to use any other type of Linux, version, and kernel version, but it is recommended to use the same with the grading environment. If it doesn’t work with the grading environment, you would not be able to get credit.
      • OS: Ubuntu 20.04.5 LTS, locale: UTF-8 (Do not use euc-kr or any other locales)
      • gcc/g++: 9.4.0 (C/C++), rustc: 1.68.2 (Rust)
    • Lab Assignment Program Structure (Note: Different structure may result in a zero score)
      • When you unzip your submission, the Makefile and the source code for the program should exist in the created folder.
      • Be sure to fill in the required options in your Makefile (library options, C++14/17 options, etc.) correctly to ensure the compatibility of your compiled project.
      • The make command should compile each of the source codes and create an executable binary named project3. This means that the program will run in the terminal via the command ‘./project3’.
      • Running the make clean command should delete the build output generated by make.
  5. Precautions
    • Late submissions will not be accepted.
    • All references including figures and code snippets must be cited. The score will be deducted when no references were specified.
    • All source code should have comments. The score will be deducted when no comments for the source code were provided.
    • Deductions or zeroes for not following the assignment submission method, program structure (especially the program name).
    • If you have any questions regarding the assignment, ask as a public question on the LearnUS course board.
      • But we may not answer simple questions such as the use of programming languages or compilation related questions.
    • Zero points if you are found to have distributed or questioned the content of this assignment online.
    • File extensions do not exist in this assignment. Do not attach arbitrary extensions such as *.txt.

Report Assignments

The report can be written in free form, but must be submitted as a PDF document that includes the following information:

  • Operation process and implementation analysis
    • Describe the source code in terms of the overall structure, rather than line by line.
    • Be sure to use a flowchart, diagram, or other pictorial representation for each algorithm.
  • Development environment specifications
    • uname -a results, operating system and compiler information, CPU information, etc.
  • Result screen and discussion (important)
    • Screen capture your results and indicate how complete your implementation is.
    • Do your best on analyzing how well your program works.
    • Create your own input cases and test your implementation against them.
    • Compare the performance with different page replacement algorithms.
  • Challenges and solutions on performing the assignment tasks.
  • Bibliography referenced during the assignment.

Lab Assignments

In this lab assignment, you will develop a kernel simulator to verify the memory management techniques of an operating system. Specifically, your objective is to build on the kernel simulator you developed in the second part of the lab and add functionality related to memory management. The main concepts covered in this kernel simulator are (1) physical and virtual memory, (2) page replacement algorithms, and (3) Copy-on-Write. Please note that this assignment description emphasizes on changes and additions form the second assignment.

The basic input and output structure is the same as the second assignment. The user mode of each process on top of the kernel simulator runs a virtual program file that exists in a directory given as an argument. The virtual program file consists of several lines of simplified instructions, but not the actual code.

memory_allocate 4
memory_allocate 3
memory_read 0
memory_write 1
memory_release 0
fork_and_exec program1
memory_release 1
wait
exit

The main difference from the second assignment is the added functionality of memory-related instructions. In the kernel simulator implemented in this task, each process has a virtual memory that operates on a page-by-page basis, and the entire system has one physical memory that operates on a frame-by-frame basis. One page of virtual memory corresponds to one frame of physical memory.

The virtual memory has a size of 32 pages, and the physical memory has a size of 16 frames. User processes can use the entire virtual memory, and each process has a page table that indicates where each page refers to in the physical memory. However, the page table in this assignment is implemented in a very simple form, containing only information of the page ID and frame ID. Also, this task does not consider a situation of running out of space in virtual memory. If the page to be referenced is not currently in physical memory, or if space is not enough in physical memory of the page to be allocated, a page replacement algorithm (lru, fifo, lfu, mfu) is used. All processes except for the init process copy the virtual memory of the parent process at the time of creation in a copy-onwrite format. In other words, the pages of the parent and child processes originally point to the same frame of physical memory, and when a write command is issued to a page of the child process, it is copied to a new frame.

Kernel Simulator I/O

  • The compiled and executed program’s name is project3.
  • The project3 file always executes with two arguments (see: argc, argv)
    • Arguemtn1. The directory where the files for the virtual programs exist.
      • Argument 2. Page replacement algorithm is given: lru, fifo, lfu, mfu
    • The two arguments are distinguished by a single space and must be given in order of ‘argument 1’ ‘argument 2’.
  • This simulator outputs the results by creating a file named result in the same directory as the project3 file.

Virtual Program Commands

  • System call: memory_allocate, memory_release, fork_and_exec, wait, exit
    • Assume the parent process executes and waits for the execution time of fork_and_exec.
    • Sleep from the second assignment is not implemented in this assignment.
  • User code commands: memory_read, memory_write

The detailed operation of a kernel simulator running a virtual program written according to the mentioned rules is as follows:

  • For detailed information, please refer to the second assignment specification. The current specification mainly focuses on the differences.
  • When a user program invokes a system call or a fault occurs, a mode switch to the kernel mode takes place.
  • The user mode is the context in which the instructions of the virtual program are executed.
    • Each instruction in the user mode consumes 1 cycle.
  • The kernel mode is the context in which the kernel functionalities are executed.
    • Each kernel mode operation also takes 1 cycle and does not occur simultaneously with a user mode operation.
    • There are five possible operations in the kernel mode:
      • (1) Boot operation (boot): This operation exists only in the 0th cycle and boots the system.
      • (2) System call handling (system call): It handles the system call commands from the user mode.
      • (3) Scheduler operation (schedule): It selects the next process to be executed from the ready queue.
        • In the cycle when the scheduler operation finishes, the output must indicate there is a running process.
      • (4) Idle state (idle): It waits until a scheduler operation occurs.
        • In the kernel mode state, if it is not in the context of processing a system call, and if the ready queue is empty in that cycle, it is in the idle state. If the ready queue is not empty, it is the scheduler operation.
      • (5) Fault handling (fault): It handles page faults or protection faults.
  • This simulator operates based on a simple FIFO scheduler.
  • Execution order within the same cycle:
    • (1) Update process states (transition from Waiting or New to Ready, delete Terminated process) and update the Ready Queue.
    • (2) Execute the command in the kernel mode or user mode.
      • If it is progressing in the kernel mode and not a boot/system call, and the ready queue is empty, it is in the idle state.
      • If it is progressing in the kernel mode and not a boot/system call, and the ready queue is not empty, it is scheduling (schedule).
      • The scheduler operation updates the ready queue once again and creates a running state process.
        • In other words, the cycle result of the scheduler operation is in kernel mode, but a running process exists.
    • (3) Output the results immediately after executing the cycle.
  • (Note) If multiple processes become ready at the same time in a specific cycle, follow the following rule. Since it has been modified slightly from the notice posted on April 16th, follow the description below.
    • There are two types of processes that become a ready state in the Nth cycle:
      • (1) Processes that become ready during the process state update phase (New Ready).
      • (2) Processes that become ready during system call or fault handling.
    • (1) and (2) are inserted into the ready queue at different times, so they are not “simultaneous”.
    • Unlike the second assignment, this assignment does not contain Sleep, and thus the case related to (1) is only the case of New Ready. In other words, there are no cases where multiple processes become Ready simultaneously from the Wait state in this assignment.
    • Similarly, in (2), there are some cases that the parent process is inserted into the ready queue during the exit system call handling. Also, there are some cases where a process that invokes other system calls or causes the fault is inserted into the ready queue during the process of corresponding system call/fault handling. However, in this assignment, there are no cases where the system call/fault handler inserts more than one process.
  • When allocating or referencing physical memory, use an appropriate page replacement algorithm depending on the situation. o
    • Multiple pages can be allocated or replaced in the same cycle by the memory allocation instructions. In other words, if there are pages having the same priority (determined by the algorithm), pages from the lower memory address are replaced first. Repeat the page replacement algorithm until all the physical memory indicated by the memory allocation instruction is allocated.

The operation results of the kernel simulator are printed as follows

  • This program creates a ‘result’ file containing the printed outputs in the same directory where the project3 file is located.
  • Although some information is not displayed, the system should have that information internally.
  • After each cycle, the system status after the execution of the command is printed with the following information:
    • The information for each cycle is separated by two newline characters. (Refer to the example code below)
    • In the beginning, the cycle number is printed.
    • Current execution mode
      • user: user mode
      • kernel: kernel mode. Even if there are no processes currently running, it is still considered kernel mode (idle state).
    • Command in execution
      • In user mode, the command and its arguments for the current cycle are printed as is.
      • In kernel mode, one of the following five options is printed: boot, system call, schedule, idle, and fault.
    • Process in execution
      • If there is a currently Running process, it will be printed in the format of ‘Process ID (Process Name, Parent Process ID)’. And if there is no currently Running process, it will be printed as ‘none’.
    • Current status of physical memory
      • The symbol “|” is used to distinguish every 4 frames. It is placed at the beginning and end, and there is no space inserted before or after the “|”. Each entity is separated by a single space.
      • The currently allocated memory is displayed with the format of ‘Process ID(Page ID)’, and empty memory spaces are printed as “-“. Specifically, if the process ID is 5 and the page ID is 3, it can be displayed as 5(3).
      • For frames shared by multiple processes due to Copy-on-Write (CoW), the parent process’s ID should be displayed.
    • Current state of virtual memory for the running process
      • The information is never displayed if there is no Running process.
      • The symbol “|” is used to distinguish every 4 frames. It is placed at the beginning and end.
      • The currently allocated memory is displayed with the Page ID, and empty memory spaces are displayed as “-“.
    • Current state of the page table for the running process
      • It will be printed in two lines, aligned with the information from 5 (current state of virtual memory for the running process).
      • In the first line, the physical memory location of each page is displayed. If it is not currently allocated in physical memory, it is displayed as “-“.
      • In the second line, the read/write permissions are displayed. By default, pages allocated by the current process have both read and write permissions, so they are displayed as “W”. However, for pages shared with the parent process by Copy-onWrite (CoW), they only have read permissions, so they are displayed as “R”.

Example input (Example virtual program)

  • Assuming that init and program1 are in the given directory.
  • Program init
memory_allocate 16
fork_and_exec program1
wait
memory_read 10
memory_write 10
memory_read 0
exit
  • Program program1
memory_read 0
memory_write 0
memory_allocate 2
memory_release 1
memory_allocate 3
memory_release 0
memory_allocate 2
exit

Example output

Assuming the directory containing the above example input (virtual program) is given as the command-line argument. FIFO is used for the page replacement algorithm.

Assignment Submission Instructions

The report (in PDF file) and source code (tar) need to be submitted as separate files. (important) 2 files for submission.

Report file (PDF)

Convert your report to a PDF file for submission. The file name should be hw3_yourstudentID.pdf. Example) If your student ID is 2023123123, the name should be hw3_2023123123.pdf.

Source code archive (tar)

Follow the instructions below to create the archive file. Other archive formats or double archiving are not allowed.

Example) Assuming your student ID is 2023123123 and you have been working in the “hw3” directory:

$ cd hw3/..
$ mv hw3 2023123123
$ tar cvf hw3_2023123123.tar 2023123123
  • After extracting the created tar file, only the “2023123123” directory should appear.
  • Under the “2023123123” directory, there should be a Makefile, and running the “make” command should generate an executable binary named “project3” in that directory.
  • Please ensure that you follow this submission format since our scripts will be used for scoring, and not adhering to the specified format may result in penalties.