Dear, Pix! Not in parallel with other procedures! At least for location updating (normal, periodic, attach).
1)First of all there is Authentication
2)When Authentication procedure is comleted the network sends Ciphering Command to MS, and MS responds by Ciphering complete message.
3)After that the Tmsi reallocation procedure is started.
Hence, the TMSI reallocation procedure really increases the SDCCH occupancy rate (aproximately on 10-20%)