Companies don't just register patents. Patents are applied for. The process can take three or more years. Once filed, a patent examiner will evaluate the application to determine if it is 1) useful, 2) novel and 3) non-obvious. In the scenario you describe, company A's software would constitute prior art to company B's application and if the examiner is doing his/her job right would reject the patent application for lack of novelty. Of course, patent examiners might not find every instance of prior art so it is possible for Company A's product wouldn't be considered.
Company A can read company B's application when it publishes 18 months after filing. Many companies keep on top of evaluating patent applications to head off future problems. They can file opposing documents during the examination process. Should the patent actually be granted there are also procedures for challenging its validity.
Assuming company B gets a patent for exactly the same technology company A has already been selling (before the filing). Company B can sue company A. If they do, the suit can go to trial where company A would have an excellent chance of winning. If they do, then the precedent means company B's patent would be essentially useless. That said patent suits are very expensive and the companies may decide to settle with some sort of licensing agreement.
One additional thing to be aware of. Patents take time to acquire. It is not uncommon for the process to take 4 or 5 years. If company A starts selling their software in 2016 and company B gets their patent in 2017, then company B probably applied for their patent in 2013 or 2014. This means they indeed could had the idea first and the patent may indeed be valid.