Try   HackMD

2020_OS_Fall_HW1: Benchmark Your Computer Black Box

Deadline: 10/6 00:00

Goals

  • Write a program that can sort numbers in ascending order, and the size of input file must be larger than the size of your physical memory.
  • Observe and analyze the usage of system resources(CPU, Memory, Disk I/O, etc.), find out how OS services our program.

Test data

Please write a program to generate the input data for this homework.

  • Please generate a single file that contains N random numbers which are separated by newline characters (LR).
    • Value range: -2147483648 ~ 2147483647, i.e. -231 ~ 231-1 (4 bytes int)
    • Be careful not to add white space before or after a newline character.
  • The size of input file must be larger than the size of your physical memory.
  • Please use UTF-8 encoding, and name the file as "input.txt".
    The test data you generate should look like this:
1016805454
1475107312
-773922153
-1631946082
-2117758124
1441150487
-1097602902
790246949
-323167788
1476584887
-1453834325
-27133615
220352360
-1417575783
1375480777
-1264143939
-1709228479
1737296785
1750366440
-2075608694
-1480735945
1708474629
...

How To Start

  1. Please follow the instructions in the preceding paragraph to generate the input file for this homework.
  2. Write a program that can sort input data and store the result to "output.txt".
    • Note that the sorting program must be able to handle a huge amount of data.
  3. Observe and analyze your program, and then optimize it (e.g., reduce the execution time).
    • Try to run out your system resources, make them fully utilized by your program, and minimize the idle resources.
  4. Write a performance analysis report of what you have observed(think about what OS did).
    • It will be the key point on evaluating your score, so please write as more as you can.
    • Observe the usage of the resources, try to conclude what OS did so that every program get the best service.
    • Try to run several your program simultaneously if it is single-thread, and observe them.
  5. Upload your code and documentation within the deadline as specified in the homework.

Document

There is no limitation of the file format, you can also use Markdown.
The Document should contain the following.

Student ID:
Name:
Department and Grade:

Development environment:

  • OS: Ubuntu 20.04.1
  • CPU: Intel® Core™ i7-10700 CPU @ 2.90GHz × 16
  • Memory: 32GB
  • Programming Language(version): Java 1.8.0_261

Execution time:

  • Please add the elapsed time function to get the actual value.

Development and user guide:

  • How you develop the program to make it support large data sorting?
  • How to run your program? Please describe the steps in detail.
# Please ensure that TA can run your program by the following steps
# And there is a way to get the path of input data
# Compile
$ javac ./YourSourceCode.java
# Run
$ java ./YourSourceCode [Data Path]

Performance analysis report:

Please note that the content of the analysis report must contain the following two parts.

  • How great is your optimization and how did you verify it?
  • What did you observe when OS managing multiple your sorting programs.
    • You can use charts, pictures, or external information to describe it.
    • It will be the key point on evaluating your score, so please write as more as you can.

Upload homework

  • deadline: 10/06 00:00
    • one day late: -10pts
    • two days late: -30pts
    • three days late: -60pts
    • more than four days: you got 0pt :)
  • Please compress your source code and documents to a zip file named "HW1_{your student ID}.zip"
    • The document can be an HTML file if you use HackMD, otherwise it should be PDF.
    • Don't put the input and output data in the zip file.
  • Please double check the correctness of your program, and make sure all the abovementioned requirements are included in the document.
  • Upload the zip file to Moodle.

Grading

The highest score is 100pts.

  • Sorting program
    • Whether your program can handle a huge amount of data.
      • TA will validate it with different scales of data.
    • Performance of your sorting program.
    • How well you optimized your program.
  • Document: the analysis report will be the key point.
    • Whether the document contains the specified content.
    • Correctness and completeness of your document.
    • Insightful observation and presentation.
    • How did you optimize this sorting program and explain it.

Notes

  • You can develop in any programming language, but TA will test it only on Ubuntu.
  • You can develop in any environment(e.g., Windows, Windows Subsystem for Linux, Virtual Machine,etc.), but TA will test it only on Ubuntu.
  • Do NOT use external libraries to do the sort.
  • NO plagiarism, or you will get 0pt.

Reference