You can get deadlocks on more than just row locks, e.g. see this. The scripts may be competing for other resources, such as index blocks.
I've gotten around this in the past by engineering the parallelism in such a way that different instances are working on portions of the workload that are less likely to affect blocks that are close to each other; for example, for an update of a large table, instead of setting up the parallel slaves using something like MOD(n,10)
, I'd use TRUNC(n/10)
which mean that each slave worked on a contiguous set of data.
There are, of course, much better ways of splitting up a job for parallelism, e.g. DBMS_PARALLEL_EXECUTE.
Not sure why you're getting "PL/SQL successfully completed", perhaps your scripts are handling the exception?