1. A computer implemented method for enabling concurrent cache line replacement operations to a plurality of cache line sets of a congruence class, the method comprising: recognizing, by a cache controller, a cache miss to a given congruence class in congruence classes of the cache, each of the congruence classes having its own addressable index, wherein the congruence classes are rows in the cache, wherein sets are columns in the cache, such that each of the sets is included in each of the congruence classes, and wherein a cache directory has status indications for each memory element in the cache; in response to the cache miss to the given congruence class having a given addressable index in the cache, placing a lock on the given congruence class to prevent access to the given congruence class as a whole while at least one set in the given congruence class is in a process of being marked by adding a marked bit in a status indication in the cache directory for the at least one set; wherein the at least one set and other sets are in the given congruence class having the given addressable index, such that the at least one set and the other sets are on a same row defined by the given congruence class; marking, by the cache controller, the at least one set of given the congruence class as a marked set by adding the marked bit into the status indication for the at least one set, the marked bit indicating that the marked set is unavailable while replacement operations are being performed on the marked set; removing the lock on the given congruence class as a whole once the at least one set has been marked with the marked bit, such that the marked bit blocks access only to the marked set in the given congruence class while allowing access to the other sets in the given congruence class on the same row having the given addressable index; selecting, by the cache controller, the other sets of the given congruence class without marked bits in their status indications in order to permit new replacement operations to be performed on the other sets without the marked bits in their status indications while the marked bit still blocks access only to the marked set in the given the congruence class on the same row having the given addressable index; wherein the at least one set is unmarked based on the replacement operations being complete for the at least one set.