1. A computer system, for enabling concurrent cache line replacement operations to a plurality of cache line sets of a congruence class, the computer system comprising: a cache controller; and a cache operatively connected to the cache controller, the system configured to perform a method comprising: marking, by the cache controller, one or more sets of the congruence class with marked bits to indicate that the marked sets are unavailable while performing replacement operations on the marked sets, wherein the sets are respectively unmarked based on the replacement operations being complete for the sets; and selecting, by the cache controller, unmarked sets of the congruence class without the marked bits to permit new replacement operations to be performed on the unmarked sets.