Stored procedure deadlocking itself, how do I resolve it? MSSQL 2012.  Stored procedure fires twice with the same parameters within 10ms of each other, and we get deadlocks.

Stored procedure basically looks like this (can't share actual code but here's the pertinent pseudocode):

BEGIN TRAN
UPDATE t
SET
    t.Column1 = NewValue1,
    t.Column2 = NewValue2,
    t.Column3 = NewValue3,
    etc for 20 columns...
FROM Table t
    INNER JOIN Results r
        ON r.ID = t.ResultID
WHERE 
    UserID = @userid
    AND Deleted = 0

UPDATE t
    SET Deleted = 1
FROM Table t
    LEFT JOIN Results r
        ON r.ID = t.ResultID
WHERE
    t.UserID = @userid
    AND t.Deleted = 0
    AND r.ID IS NULL
COMMIT TRAN


Deadlocks are occurring on Table, indexes involved are UserID (non-clustered covering index) and the Primary Key.  When I run the procedure in my test environment, the execution plans show that both UPDATEs are using the covering index to get the rows (seek, no lookups), then having to update the PK and the covering index.

Possible solutions I've thought of are:


Removing the explicit transaction control.  Since the two updates don't really rely on each other, that seems viable.  Would that resolve the deadlock?
Removing the PK and making UserID the (non-unique) clustered index.  This, however, may impact other things that use the PK elsewhere.
Implementing some boolean logic in the second UPDATE to avoid running it unnecessarily.  Doesn't actually fix the problem though, just makes it happen less often.


I'm about 2 months into my career as a dba, and deadlocks have been difficult to get my head around.  Any advice would be greatly appreciated!
Each of your 2 update statements may cause deadlock when executing within different transactions, no matter explicit or implicit.  They both change the same set of rows  , and nothing guaranties in which order the rows are locked.
One option is just to catch error and re-run failed transactions. Another approach is  to somehow "serialize" updates. 

In my opinion, the easiest and fastest way is to modify procedure so it waits until the other instance of the same procedure completes updates.  It can be implemented, for instance, by using sp_getapplock.  

Another option is to ensure that rows are locked in the same order (e.g. -open cursor that reads all required rows in particular (unique) order, iterate through it, and for each row issue SELECT WITH ROWLOCK), and issue update after all rows are locked.  Then in case of simultaneous execution the second transaction will wait for the first one. I think that for SQLServer a very little chance of deadlocks might exist because of potential lock escalation though.