The implementation of software based video/audio decoders is an advantageous solution over traditional dedicated hardware systems. However, simultaneously guaranteeing real-time performance, needed for processing video/audio bit-streams, and an efficient use of the processing power, remains a very difficult task. In this paper, we briefly discuss the main reasons of such difficulties and we present a new technique able to predict the decoding time of compressed video bit-streams without the need of the actual decoding. This result can be obtained when appropriate statistics about the actual decoding process are included and transmitted with the compressed video data. We also show how such results can be used to implement new efficient processing resource allocation strategies. New possible schemes of intelligent interactions, and in particular an efficient implementation of Computational Graceful Degradation, between the encoder and the real-time OS are also proposed. An example of results obtained implementing the proposed technique for the MPEG-4 VM6 video algorithm is presented. Although the techniques and concepts presented in this paper are of general application, they can only be used for video compression standards capable of transmitting in any appropriate form the associated statistical coding information. This capability has been included in the new defined MPEG-4 standard.