How do online judges identify Time Limit Exceeded?

Question: I have to design C++ code that calls a function. But I must not run that function for more than 2 seconds. 

Answer

Slow down young man, and let's proceed steadily. Shall we?

Now what exactly you want to achieve is unclear here. Do you simply want to measure the execution time of the function? Do you want to terminate the program after the time limit is exceeded? Are you calling the function in a child process? Is your process running as a privileged user?The implementation obviously depends on what you want to do and what environments you are initializing the process with.

Nevertheless, there are few different ways. I will get to them one by one with simplest first.

1. Measuring time

You can easily measure the time (clock time & CPU time) taken to execute a function using clock() and time() functions available in the header <time.h>.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

#include <stdio.h>
#include <time.h>


void my_function();


int main()
{
    clock_t c0, c1;
    time_t t0, t1;


    t0 = time(NULL);
    c0 = clock();


    my_function();


    t1 = time(NULL);
    c1 = clock();


    printf("wall clock time: %ld\n", (long) (t1 - t0));
    printf("CPU time: %f\n", (float) (c1 - c0) / CLOCKS_PER_SEC);


    return 0;
}


void my_function()
{
    printf("%s\n", "Returning from my_function.");
}



2. Using SIGALRM

See the code below to understand how you can check whether a function takes more time than you expect it. There are comments in between the code to make it easier to understand.

You can test by commenting `sleep(3)' and uncommenting `sleep(1)' in my_function() to see what is happening. (Although mixing alarm() and sleep() is a very bad idea, I thought this is the easiest way to show you the effect.)


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <stdio.h>
#include <unistd.h>
#include <signal.h>
#include <err.h>


#define TIME_LIMIT 2


void my_function();
void alarm_handler(int);


int main()
{
    if (sigaction(SIGALRM, NULL, NULL) == -1)
        err(1, NULL);


    // install an alarm handler for SIGALRM
    signal(SIGALRM, alarm_handler);


    // install an alarm to be fired after TIME_LIMIT
    alarm(TIME_LIMIT);


    // call your function
    my_function();


    // cancel any previously set alarm
    alarm(0);


    return 0;
}


void my_function()
{
    //sleep(1);
    sleep(3);
    printf("%s\n", "Returning from my_function.");
}


void alarm_handler(int sig)
{
    printf("%s\n", "Seems you crossed time limit!");
}



Now what happens is that when my_function() is still executing and TIME_LIMIT is crossed, SIGALRM is fired and alarm_handler() is invoked. It then prints the message "Seems you crossed time limit!". You can even kill the process using kill() in alarm_handler.


3. Resource Limits

Online judges don't implement TLE by the nasty method I have mentioned above. They use `struct rlimit' to enforce any type of resource limit including the time limit. Besides that, there are lots of other signals and checks used for security and integrity of online judges and even the simple implementations run into thousands of lines of code.

Before proceeding forward, you should take a look at 'man setrlimit'.

In C programs, you can set or get resource limits by setrlimit and getrlimit respectively. But the caveat is that only a privileged process may make arbitrary changes to either limit value.

Each resource has an associated soft and hard limit, as defined by the rlimit structure.

1
2
3
4

struct rlimit {
    rlim_t rlim_cur;  /* Soft limit */
    rlim_t rlim_max;  /* Hard limit (ceiling for rlim_cur) */
};


The code snippet below shows how it can be implemented in a very rudimentary way, but enough to give an idea.

-- snippet --
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <signal.h>
#include <sys/time.h>
#include <sys/resource.h>


#define TIME_LIMIT 2


if (sigaction(SIGALRM, NULL, NULL) == -1) {
    return -1;
} else if (sigaction(SIGXCPU, NULL, NULL) == -1) {
    return -1;
}


struct rlimit rlim;
rlim.rlim_cur = rlim.rlim_max = TIME_LIMIT
if (setrlimit(RLIMIT_CPU, &rlim) < 0)
    err(1, NULL);

-- /snippet --

If your program is running as privileged (root) user, setrlimit sets the CPU time limit for the program to TIME_LIMIT as defined in the code. When the soft time limit (rlim_cur) is crossed, SIGXCPU is sent to the process and when the hard time limit (rlim_max) is crossed, SIGKILL is sent to the process. You can catch SIGXCPU and do a clean exit.


Online judges

The implementation of online judges often takes into account many other factors like memory limit and security which makes them more complicated. But the underlying mechanism remains the same. Step by step they can be written as:
  1. Run the process as privileged user
  2. Install all signal handlers
  3. duplicate input file stream to stdin
  4. create a child process
  5. set resource limit values in child process
  6. switch to unprivileged user in child process
  7. exec the program to run in child process
  8. In parent process, check for the signals sent using WIFSIGNALED and WTERMSIG, etc. and determine the state of child process.


If you want to learn more about signals and process execution, read Advanced Programming in UNIX Environment by W. Richard Stevens.http://www.amazon.com/Programmin...

The above mentioned methods and resources may not exactly solve your problem, but I hope they give you enough idea on how to proceed!

P.S. Originally answered on Quora (Link)
Location: IIT Roorkee

Comments

Post a Comment