A method, system, and a computer program product for gracefully stopping a multi-threaded application. An aspect of the present invention requires each thread in a multi-threaded application to acquire a work permit before performing a task and to release the work permit after completion of the performance of the task. The multi-threaded application is stopped only when all of the work permits have been released by the threads in the application. The release of all of the set of work permits indicates that all the currently performing tasks/threads are completed, thereby “gracefully” stopping the multi-threaded application.