The general advice regarding deadlocks: make sure you do everything in the same order, i.e. acquire locks in the same order, for different processes.

You can find the same advice in this technical article on microsoft.com regarding Minimizing Deadlocks . There's a good reason it is listed first.

• Access objects in the same order.
• Avoid user interaction in transactions.
• Keep transactions short and in one batch.
• Use a lower isolation level.
• Use a row versioning-based isolation level.
• Set READ_COMMITTED_SNAPSHOT database option ON to enable read-committed transactions to use row versioning.
• Use snapshot isolation.
• Use bound connections.

Update after question from Cato:

How would acquiring locks in the same order apply here? Have you got any advice on how he would change his SQL to do that?

Deadlocks are always the same, no matter what environment: two processes (say A & B ) acquire multiple locks (say X & Y ) in a different order so that A is waiting for Y and B is waiting for X while A is holding X and B is holding Y .

It applies here because DELETE and UPDATE statements implicitely acquire locks on the rows or index range or table (depending on what the engine deems appropriate).

You should analyze your process and see if there are scenarios where locks could be acquired in a different order. If that doesn't reveal anything, you can analyze deadlocks using the SQL Server Profiler :
To trace deadlock events, add the Deadlock graph event class to a trace. This event class populates the TextData data column in the trace with XML data about the process and objects that are involved in the deadlock. SQL Server Profiler can extract the XML document to a deadlock XML (.xdl) file which you can view later in SQL Server Management Studio. You can configure SQL Server Profiler to extract Deadlock graph events to a single file that contains all Deadlock graph events, or to separate files.

I'd use sp_getapplock in the updating transaction to prevent multiple instances of this code running in parallel. This will not block the selecting statement as table locking hints do.

You still should program the retrying logic, because it may take a while to acquire the lock, longer than the timeout parameter.

This is how the updating transaction can be wrapped into sp_getapplock .

BEGIN TRANSACTION;
BEGIN TRY

    DECLARE @VarLockResult int;
    EXEC @VarLockResult = sp_getapplock
        @Resource = 'some_unique_name_app_lock',
        @LockMode = 'Exclusive',
        @LockOwner = 'Transaction',
        @LockTimeout = 60000,
        @DbPrincipal = 'public';

    IF @VarLockResult >= 0
    BEGIN
        -- Acquired the lock
        update FOO set ...
        where NON_CLUSTERED_ID = @id

        delete FOO where NON_CLUSTERED_ID in (@id1, @id2, @id3, ...)

    END ELSE BEGIN
        -- return some error code, so that the caller could retry
    END;

    COMMIT TRANSACTION;
END TRY
BEGIN CATCH
    ROLLBACK TRANSACTION;
    -- handle the error
END CATCH;

The selecting statement doesn't need any changes.

I would recommend against NOLOCK , even though you say that IDs in chunks do not overlap. With this hint the SELECT query can skip some pages that are being changed, it can read some pages twice. It is unlikely that such behavior can be tolerated.

Kindly use get applock in such format in code.  The stored procedure sp_getapplock puts the lock on the application resource .

EXEC Sp_getapplock
     @Resource = 'storedprocedurename',
     @LockMode = 'Exclusive',
     @LockOwner = 'Transaction',
     @LockTimeout = 25000

It is very helpful. Kindly increase LockTimeout to reduce deadlock