Submit: Turn in your reverse.c source file using the turnin command on morbius.mscsnet.mu.edu or one of the other Systems Lab machines.

Work is to be completed individually. Be certain to include your name in the file. You may submit multiple times, but only the last turnin will be kept. The automatic submission system will not accept work after the deadline. (See turnin instructional video HERE. Note that the video is for a different course number, and that Morbius's domain name has changed since the video was made: morbius.mscs.mu.edu -> morbius.mscsnet.mu.edu)

Include a comment block at the very top of each file that contains the following:

/**
 * COSC 3250 - Project #
 * Explain briefly the functionality of the program.
 * @author [your name]
 * Instructor [your instructor]
 * TA-BOT:MAILTO [your email address]
 */


A Stunning Reversal

The Program

Write a C program that reads in an arbitrarily long sequence of positive integers, and outputs that same sequence in reverse order.

Your program should understand positive integers in binary (starting with "0b",) octal, decimal, and hexadecimal, but all output will be in decimal (base-10). This should reuse code from your calculator project.

Your program should ignore any amount of white space between integers, including tabs, spaces, newlines, etc. See the isspace() function in your text or in the man pages for details. Your output, however, should consist entirely of base-10 representation integers in a line by themselves.

In order to store an arbitrary list of integers, your program will need to request more memory from the operating system when the space it already has runs out. This kind of dynamic allocation is performed using the malloc() function, as detailed in your text and in the man pages. You may assume that we will test your program with at least 100,000,000 integers. Your program should exit gracefully if a malloc() request is denied.

The professor has provided an example program for your reference, executable on Morbius as ~brylow/os/Projects/reverse. In addition, there is a test generator executable as ~brylow/os/Projects/billionrandom. The test generator takes a single command-line parameter for the number of integers desired, and then outputs a predictable sequence of pseudo-random numbers [Wikipedia] using a linear congruential generator [Wikipedia] and rotating through the various bases.

Notes

• There are a variety of approaches for storing an arbitrarily long list of integers. The approach I recommend is building a linked list of structures that store a reasonable number of integers. So, for example, you could define a struct that contains an array of a few thousand integers. Every time you fill up that structure, request another one and string it into a linked list with all of the previous blocks. This is an excellent balance in efficiency -- if your block size were too small (one integer per malloc() in the most absurd case,) your program would spend most of its time asking the O/S to allocate more memory. If the block size were too large, (say, a Gigabyte,) your program would needlessly waste resources when the input was only a small list, and might not even be able to allocate a single chunk that large.
• This project is inherently dangerous; please exercise both great care and ethical consideration during this assignment. For large numbers of integers, this program is essentially a stress test for the operating system's virtual memory subsystem. On Elsinore (a late model 3 GHz Pentium IV) running my program with a test list of 1,000,000,000 runs for over 15 minutes, and practically locks up all user interfaces for the last 10 minutes of that. The reference implementation, in combination with the test generator, can bring pretty much any server to its knees in a matter of minutes. As a result, there is a particularly important list of DO NOTs for this project:
  • DO NOT run your program with a large test size on Morbius or Pascal, or any other large server relied upon by multiple users.
  • DO NOT pipe the output of billionrandom or your program to a text file for list sizes over a few million. If you do the math, you'll see that this could quickly fill up the space in your home directory (and thus the home directories of everyone else on the same server hard disk) and clog up the network with file server traffic.
  • DO check your dynamic allocation code by adjusting your block size downward to insure that even small numbers of integers will require multiple malloc() requests.
  • DO check your malloc() error handling by adjusting your block size upward until your first request fails.
  • DO run your program with large test input (more than a few million) only once you are relatively certain it is working properly -- so that you only have to do it once.
  • DO NOT run large test cases when it is apparent that a bunch of other people are trying to do their work on the same machine. See the top and w UNIX commands for more info.
• For reference, your assignments will be compiled and graded on Morbius.
• The Systems Lab (CU 310) is the primary development environment for COSC 3250. It is expected that you will learn to use the required tools for developing, testing, and submitting your projects. The Systems Lab machines are available locally in Cudahy 310, and can be accessed remotely via ssh using your CS Department credentials. (See D2L Laboratory Instructions for instructions for learning your credentials.) Free secure shell (ssh and scp) clients are readily available for other platforms, including Windows and Macs.
• The Systems Lab machines run the Linux operating system. If you need a refresher on using the UNIX environment, please see the UNIX Tutorial.
• The reference implementation is considered an integral part of the specifications for this assignment. Project grades will be based in significant part upon an automated comparison of behavior against the reference implementation. Devise test cases to discover the expected behavior, and do your best to match it precisely. Creativity will be valued in later assignments, but first one must master the tools.
• Use the electronic turnin system to submit your work. The command is "turnin", followed by the name(s) of files(s) you wish to submit. The command "turnin -v" will print a listing verifying the contents of your submission. See "turnin -h" for a list of other relevant options. The system does not accept work after the deadline, and neither does the professor.

---

[back]

[Revised 2020 Sep 01 11:36 DWB]