Transaction was deadlocked - attempting to 'lock' records for processing

I have the following stored procedure that is being called by a number of instances of a a worker service. When the services first start, there is contention on the table and I get deadlocks and need to get rid;

 SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;

    BEGIN TRAN

    DECLARE @Inserted TABLE (
        [Id] BIGINT NOT NULL PRIMARY KEY,
        [Status] INT NOT NULL,
        [LockDate] DATETIME NULL,
        [InternalId] BIGINT NULL,
        [SourceUpdated] BIT NOT NULL
    )

    UPDATE tm
            SET
                tm.LockDate = DATEADD(MINUTE, @LockDuration, GETDATE()), [ModifiedDate] = GETDATE()
            OUTPUT
                Inserted.[Id],
                Inserted.[Status],
                Inserted.LockDate,
                Inserted.InternalId,
                Inserted.SourceUpdated

            
            INTO @Inserted

            FROM  [Transactional].[Message] tm WITH (UPDLOCK)
            INNER JOIN
               (SELECT TOP 250 [Id] FROM  [Transactional].[Message]
            WHERE [Status] = 0 AND LockDate IS NULL
            ORDER by [ModifiedDate] ASC) tmc on tmc.Id = tm.Id


    COMMIT TRAN

    SELECT 
        [Id],
        [Status],
        [LockDate],
        [InternalId],
        [SourceUpdated]
    FROM
        @Inserted

The objective here is to lock 250 records for each process. The code is called from Entity Framework if that could be a factor;

var records = await _context.TransactionalMessages!
							.FromSqlRaw($"EXEC [Records].[LockRecordsForProcessing]")
							.ToListAsync(cancellationToken: token);

The error I get is;

Microsoft.Data.SqlClient.SqlException (0x80131904): Transaction (Process ID 91) was deadlocked on lock resources with another process and has been chosen as the deadlock victim. Rerun the transaction.

Add UPDLOCK to the TOP 250 subquery too. SERIALIZABLE by default reads with S locks, which will lead to deadlocks. Basically SERIALIZABLE enforces isolation by creating deadlocks.

So you either need more restrictive locking than SERIALIZABLE, or you need to retry on deadlock.

I think this is poor design but the following should get rid of the deadlocks without an explicit transaction:

DECLARE @OP TABLE
(
	[Id] bigint NOT NULL PRIMARY KEY,
	[Status] int NOT NULL,
	[LockDate] datetime NULL,
	[InternalId] bigint NULL,
	[SourceUpdated] bit NOT NULL
);
WITH Msg
AS
(
	SELECT TOP (250) Id, [Status], LockDate, InternalId, SourceUpdated
		,ModifiedDate
	FROM Transactional.[Message] WITH (UPDLOCK, SERIALIZABLE)
	WHERE [Status] = 0 AND LockDate IS NULL
	ORDER BY ModifiedDate
)
UPDATE Msg
SET LockDate = DATEADD(minute, @LockDuration, CURRENT_TIMESTAMP)
	,ModifiedDate = CURRENT_TIMESTAMP
OUTPUT Inserted.[Id], Inserted.[Status], Inserted.LockDate
	,Inserted.InternalId, Inserted.SourceUpdated
INTO @OP;

SELECT Id, [Status], LockDate, InternalId, SourceUpdated
FROM @OP;

If you still have a lot of blocking, and want to keep this design pattern, you could also look at making Transactional.[Message] an In-Memory table.