Why do you think this would happen? Self-driving cars are poised to dramatically improve parking overall. One can be dropped off exactly at their destination, and the car can then go elsewhere. Even an elsewhere of "somewhere 5 minutes away" is a large amount of potential parking in a typical urban environment. Additionally, any existing parking lot that chooses to only accept self-driving vehicles instantly gets additional capacity: self-driving cars could cooperatively pack/unpack themselves into space efficient configurations.
And if your counter is "a minority of selfish entitled people", the answer to that is "laws and regulations". Self-driving cars will have to follow the laws of wherever they're driving. If your "circling the block" apocalypse comes to pass, the mitigation would literally be a law/regulation that self-driving cars would have to obey.