---
tags: 2020_OS_HW1, en-US
---
# 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. -2^31^ ~ 2^31^-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.
6. 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.
7. 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.
7. 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
* Ｍemory: 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
* [Merge sort](https://en.wikipedia.org/wiki/Merge_sort)
* [External_sorting](https://en.wikipedia.org/wiki/External_sorting)
* [Linux Perf](http://wiki.csie.ncku.edu.tw/embedded/perf-tutorial)
Sign in with Wallet
Connect another wallet