It's probably just the vocabulary I am missing to find out how to do this:
A job scheduled to run regularly every 5 mins, however keeping track that there are never two instances of it running at the same time, i.e. the next instance would be postponed or skipped if the prior runs longs than 5 mins.
What is the easiest/most elegant way to achieve this?
DBMS_JOB takes care of that. Just use it.