A virtual storage device including a releasable region decider that decides whether each of a plurality of management unit regions is a releasable region, being allocated a physical region and being a release candidate region, by referring to management data that associates allocation data representing a state of allocating a physical region to the management unit region and release candidate region data representing whether the management unit region is a release candidate region with each other; a determinator that determines whether the management unit region decided to be the releasable region by the releasable region decider is an all-zero region all data in which are zero; and a releaser that releases allocation of a physical region allocated to the management unit region determined to be the all-zero region by the determinator. This configuration makes it possible to efficiently use the storage region.