Tower Controller reported a busy session when a pilot thought they were told to line up and wait causing a go around and runway incursion.

Narrative

Aircraft X was an IFR departure holding back on the Alpha taxiway. I got his IFR release from P50. I told Aircraft X to proceed up to and hold short of Runway 21. Pilot read back the hold short instructions and proceed up to the runway at [Taxiway] A16. I had Aircraft Y (student solo) on right base and I had another aircraft on right downwind doing pattern work. I had an aircraft call inbound from the south and I gave them instructions to enter left traffic. I then went to the other aircraft on right down wind in the pattern and told them to extend down wind and I would call their base for traffic holding in position. I scanned my runway and saw Aircraft X entering the runway without clearance. Aircraft Y was on short final and I sent them around for the traffic on the runway. I told Aircraft X that he was instructed to hold short of the runway and the pilot responded that he was told to line up and wait. Due to traffic volume and complexity due to runway incursion and the go around I was not able to give the Brasher to Aircraft X. Aircraft Y went around and stayed in the pattern. I cleared Aircraft X for takeoff and shipped him to P50 in his right turn on the departure. When I was relieved I went and listened to the tapes and I never told Aircraft X to line [up] and wait and I didn't miss a read back in regards to that. The only time it was mentioned was when I was giving the required phraseology to the next to land aircraft. At the time the incident happened we only had 2 CPC's in the cab (myself and the GC) and CPCIT working FD (Flight Data). CIC (Controller in Charge) was combined with GC. More staffing wouldn't have prevented this from happening but it would have been more eyes and team work in the recovery getting the needed information. Pilots need more continuous training. Aircraft X clearly didn't understand what was going on and just assumed that instructions given to another pilot was for him. Due to traffic volume and number of students and inexperienced pilots we need to have some sort of runway status lights for the pilots to see that the runway in use or occupied.