It used to be that you could get a municipal check (local police station), but it seems that this has changed and that the NIA now requires RCMP checks. See this thread for Motorcycle Rider’s description of how to go about it. 120 days for a criminal background check from Canada?
As for time frame, you have nothing to worry about, since you are still a resident. It seems that most people think that there is a time limit from the day you hit your 5 years. This is wrong. There is a time limit if you stop being a resident.