3

I will start with the question and then proceed to explain the need:

Given a single C++ source code file which compiles well in modern g++ and uses nothing more than the standard library, can I set up a single-task operating system and run it there?

EDIT: Following the comment by Chris Lively, I would have better asked: What's the easiest way you can suggest to try to tweak linux into effectively giving me a single-tasking behavior. Nevertheless, it seems like I did get a good answer although I did not phrase my question well enough. See the second paragraph in sarnold's answer regarding the scheduler.

Motivation: In some programming competitions the communication between a contestant's program and the grading program involves a huge number of very short interactions.

Thus, using getrusage to measure the time spent by a contestant's program is inaccurate because getrusage works by sampling a process at constant intervals (usually around once per 10ms) which are too large compared to the duration of each interaction.

Another approach to timing would be to measure time before and after the program is run using something like *clock_gettime* and then subtract their values. We should also subtract the amount of time spent on I/O and this can be done be intercepting printf and scanf using something like LD_PRELOAD and accumulate the time spent in each of these functions by checking the time just before and just after each call to printf/scanf (it's OK to require contestants to use these functions only for I/O).

The method proposed in the last paragraph is ofcourse only true assuming that the contestant's program is the only program running which is why I want a single-tasking OS.

To run both the contestant's program and the grading program at the same time I would need a mechanism which, when one of these program tries to read input and blocks, runs the other program until it write enough output. I still consider this to be single tasking because the programs are not going to run at the same time. The "context switch" would occur when it is needed.

Note: I am aware of the fact that there are additional issues to timing such as CPU power management, but I would like to start by addressing the issue of context switches and multitasking.

user302099
  • 635
  • 1
  • 5
  • 17
  • Not sure that this belongs here. "Can you do something" type questions are almost always answered in the affirmative. This question is pretty vague. I'd suggest that you might first try implementing this and if/when you run into issues post the exact nature of your problem here for help. – NotMe Oct 23 '11 at 01:28
  • Are you asking as someone who runs a contest? or as a contestant? – Mike Dunlavey Oct 23 '11 at 01:41
  • possible duplicate of [Grading Program - Compile/executing c++ code within c++](http://stackoverflow.com/questions/5131085/grading-program-compile-executing-c-code-within-c) – Ben Voigt Oct 23 '11 at 02:00
  • @Chris: I changed the phrasing a bit now to be as specific as I currently can be. Thanks for the comment. – user302099 Oct 23 '11 at 06:16
  • @Mike: I am asking as someone who runs a C++ programming contest. – user302099 Oct 23 '11 at 06:16
  • @Ben: I don't think these questions are duplicates because only the current one deals with accurate timing of I/O intensive programs. – user302099 Oct 23 '11 at 06:18
  • I do have some concern that you're trying to remove the IO costs from the "costs" of your programs -- but IO cost is a very real cost in non-trivial programs. We have CPU registers because CPU caches are way too slow. We have L1, L2, and L3 CPU caches because main memory is way too slow. We have main memory because disks are way too slow. A huge part of computer science is managing caches of slower storage in an attempt to make the best out of meager resources. And your contestants probably need to know that IO costs real time and real money. – sarnold Oct 24 '11 at 21:55
  • @sarnold: I agree, those are real issues, but some of them are actually taken into account in our competition such as Cache vs. main memory. I/O is used to communicate with a grading program which acts as an adversary and we would not like to punish a contestant because he/she made the adversary grading program "think for a long time". That's the only cost I'm trying to remove. – user302099 Oct 24 '11 at 23:21
  • Hehe, you must not have many contestants actively trying to break your grading mechanism. That's awfully polite of them. :) – sarnold Oct 24 '11 at 23:28
  • @sarnold: So far I've tried psychological rather than technical methods to prevent this kind of cheating. Why are you saying that now though? (is there anything in my last comment which shows how cheating prone my system is?) – user302099 Oct 24 '11 at 23:33
  • @user302099, it was the _we would not like to punish a contestant because he/she made the adversary grading program "think for a long time"_ statement -- a smartass who thinks it'd be more fun to cheat might very well prevent the grading program from executing its duties in reasonable time. But if everyone is there to have fun with the problems you present to them, it shouldn't be a big concern. (At least my experience with contests shows the contestants _love_ solving problems and less breaking things.) – sarnold Oct 24 '11 at 23:37

1 Answers1

2

First things first, what I think would suit your needs best would actually be a language interpreter -- one that you can instrument to keep track of "execution time" of the program in some purpose-made units like "mems" to represent memory accesses or "cycles" to represent the speeds of different instructions. Knuth's MMIX in his The Art of Computer Programming may provide exactly that functionality, though Python, Ruby, Java, Erlang, are all reasonable enough interpreters that can provide some instruction count / cost / memory access costs should you do enough re-writing. (But losing C++, obviously.)

Another approach that might work well for you -- if used with extreme care -- is to run your programming problems in the SCHED_FIFO or SCHED_RR real-time processing class. Programs run in one of these real-time priority classes will not yield for other processes on the system, allowing them to dominate all other tasks. (Be sure to run your sshd(8) and sh(1) in a higher real-time class to allow you to kill runaway tasks.)

sarnold
  • 102,305
  • 22
  • 181
  • 238
  • As I cannot allow not to run the contest in C++, I will try the approach suggested by the second paragraph. – user302099 Oct 23 '11 at 06:26