So WHY does QoS work? Why does congestion control drop packets randomly from queues? The answer lies in the two metrics of connection quality. Packet delay, and packet loss. Any decent internet protocol uses at least one and sometimes both metrics to adjust transmission speed with two main goals. Maximum transmission speed, and low latency. Several other measures of connection quality exist but are rarely used by protocols. These include jitter (variance in packet delay) or monitoring buffer size(which is rarely done due to bufferbloat in modern networks).
QoS hijacks these basic mechanisms to convince protocols to individually slow down their communication speed. The QoS queues themselves cause packet delay, and congestion control algorithms (Aka. Active Queue Management) like RED and tail drop signal the network protocols that the link is saturated and they need to slow down. You can think of QoS as tricking different protocols into believing they are on separate links of different speeds. Essentially that is exactly what they do if you pretend that each queue is a different network interface.
Difference in QoS effectiveness
Different protocols are affected differently by QoS. TCP generally responds extremely well, and many queue discipines were designed with primarily TCP in mind. The exact algorithm used to detect network link saturation depends, surprisingly, on the client operating system. TCP is generally implemented in the kernel. All TCP algorithms measure either delay or packet loss or both, so QoS measures like RED and the delay of the queue buffer itself will cause TCP senders to decrease their own transmission rate and overall delay will remain low. Technically, all TCP traffic could be put into the same queue and performance would be at least decent.
Queues containing TCP traffic will tend not to overflow, UDP is the wild west.
UDP is less well behaved, because more details are left to the individual designer, and most software engineers only have a basic understanding of networking. In the worst case, QoS is almost completely ineffective at getting UDP senders to decrease their transmission rate, causing network delay in whatever queue they are in to increase exponentially until the QoS system dumps most packets outright. Because of this, it is VITAL to make sure your TCP traffic goes to different queues than UDP traffic.
QoS avoidance in badly behaving protocols
Certain protocols are either badly designed or intentionally saturate the network to get more bandwidth in return for worse latency, forcing better behaving protocols like TCP to reduce their transmission rate while sending packets without any regard to network quality metrics like delay and packet loss. These flows must be directed to their own QoS queue because whatever queue they are assigned to will have insane delay and loss rates as they massively overflow the buffer.
Difference in network performance depending on OS network stacks
Because TCP and UDP are implemented at the OS level, different hosts have different level of packet friendliness. Linux based hosts generally use TCP Vegas, a very "nice" implementation of the TCP protocol that is designed to share network traffic with other protocols. Vegas is delay-based so it will back off before packet loss occurs. Windows uses more aggressive TCP scheduling that uses packet loss as the primary metric. Even if the delay gets large, the senders will not back off until they start losing data from over-filled buffers. This loss based scheduling is fairly common which makes techniques such as RED very important.
For example, if you have a queue with both windows and Linux hosts for http traffic (TCP port 80), if the link gets saturated the queue buffer will start to fill. As it fills, the delay sending a packet on the wire will increase. Linux hosts will tend to back off transmission rate as the delay increases, preventing packet loss from happening.
Giving fair traffic to different implementations of TCP and other protocols
Windows and some other hosts will continue to maintain TCP transmit speed as the queue fills until it overflows and starts dropping packets. This is a problem for other operating systems and protocols with "nicer" network stacks. The best way to even this out is manipulate both measures of connection quality, delay and packet loss, at the same time using QoS and congestion control. QoS queues work fine for inducing delay, and protocols that use delay as a metric tend to be easier on hardware as well. Some avid designers instead focus on loss rates as a metric of quality, usually in protocols more interested in speed than latency. This causes problems when different applications and network stacks need to share the same pipe. Congestion control algorithms like RED and other more advanced techniques like CoDel were developed as solutions to this problem. Essentially, they force packet loss BEFORE the buffers overfill and cause tail drop. This means they start dropping more packets as delay increases, causing both delay and loss based protocols to back off. Congestion control, also known as AQM, will even out the transmission rates between delay based and loss based protocols because they simulate loss when delay occurs.