This is what I get by using bench.py script attached to issue13451:

CURRENT VERSION (NO LOCK)

test_cancel                    : time=0.67457 : calls=1 : stdev=0.00000
test_empty                     : time=0.00025 : calls=1 : stdev=0.00000
test_enter                     : time=0.00302 : calls=1 : stdev=0.00000
test_queue                     : time=6.31787 : calls=1 : stdev=0.00000
test_run                       : time=0.00741 : calls=1 : stdev=0.00000


LOCK WITH DECORATOR (no synchronization)

test_cancel                    : time=0.70455 : calls=1 : stdev=0.00000
test_empty                     : time=0.00050 : calls=1 : stdev=0.00000
test_enter                     : time=0.00405 : calls=1 : stdev=0.00000
test_queue                     : time=6.23341 : calls=1 : stdev=0.00000
test_run                       : time=0.00776 : calls=1 : stdev=0.00000


LOCK WITHOUT DECORATOR (always synchronized)

test_cancel                    : time=0.69625 : calls=1 : stdev=0.00000
test_empty                     : time=0.00053 : calls=1 : stdev=0.00000
test_enter                     : time=0.00397 : calls=1 : stdev=0.00000
test_queue                     : time=6.36999 : calls=1 : stdev=0.00000
test_run                       : time=0.00783 : calls=1 : stdev=0.00000


Versions #2 and #3 have the same cost, so it's better to get rid of the explicit argument and always use the lock (version #3).
Differences between #1 and #3 suggest that introducing the lock obviously have a cost though.
It's not too high IMO, but I couldn't say whether it's acceptable or not.
Maybe it makes sense to provide it as a separate class (SynchronizedScheduler).