How is it possible that two deletes give a deadlock, if they do have different primary key data

I am getting a deadlock by the same delete stored procedures that is called by two different threads for deleting two concurrent records.

The deadlock happened on the primary key index of the X table.
Do you have any idea for solve this problem?

Here is the delete query:

DELETE FROM "MetadataContexts_data" WHERE iid=@iidvalue AND locked=@lockedvalue;

where iid and locked values for those two different delete are is 1845, 2015-02-23T10:33:23:384.719 and 1846, 2015-02-23T10:33:23:509.9806 respectively.
There is no index on the locked column while iid is the primary key column.

Here is the deadlock graph: (table names obfuscated)

    
        
            
                
                    Delete  FROM "MetadataContexts_data" WHERE "MetadataContexts_data".iid in (SELECT iid from Deleted)     
                
                    DELETE FROM "MetadataContexts_data" WHERE iid=@iidvalue AND locked=@lockedvalue;     
            
            
    Proc [Database Id = 11 Object Id = 412593304]    
        
        
            
                
                    Delete  FROM "MetadataContexts_data" WHERE "MetadataContexts_data".iid in (SELECT iid from Deleted)     
                
                    DELETE FROM "MetadataContexts_data" WHERE iid=@iidvalue AND locked=@lockedvalue;     
            
            
                    Proc [Database Id = 11 Object Id = 412593304]    
        
    
    
        
            
                
            
            
                
            
        
        
            
                
            
            
                
            
        
    

You might be getting lock escalation. This is when SQL Server replaces many fine-grained (row) locks with a single coarse-grained (table) lock to save system resources. This is most likely if you are processing many rows within a transaction. That link suggests some work-arounds.

StackExchange Database Administrators Q#93557, answer score: 2