A translation lookaside buffer has a plurality of entries in which address translation information obtained by translating a virtual address into a physical address is registered. The entries each have a priority bit that is set when the registered address translation information is required to be resident. At the time an entry substitution request occurs while the priority bits of all the entries are in a set state, a control circuit for controlling the translation lookaside buffer chooses as a subject of substitution an entry that has been least recently referred to, irrespective of states of the priority bits. This allows execution of the entry substitution with the priority bits in all of the entries being set.