Appellant, a California state prisoner, filed a pro se action in federal court under 42 U.S.C. § 1983 against the defendants — a public defender, a district attorney, a deputy district attorney, and a state trial judge — seeking damages and injunctive relief on the ground that the defendants had deprived him of his constitutional right to a fair trial. The matter was referred to a magistrate. 1 The magistrate found that three of the defendants were immune from an award of damages and that Reynaga’s request for injunctive relief — his early release from prison — was precluded because his sole federal avenue for such a remedy was via a writ of habeas corpus. See Marchetti v. Bitterolf, 968 F.2d 963, 966-67 (9th Cir.1992).

The magistrate ordered the § 1983 action “stayed until plaintiff exhausts his state remedies.” The magistrate directed that “THIS ACTION WILL NOT PROCEED FURTHER UNLESS AND UNTIL HE [Reynaga] NOTIFIES THE COURT THAT HE HAS EXHAUSTED STATE REMEDIES." (emphasis in original). Finally, the magistrate stated that “[t]he Clerk of the court is directed to administratively close the file in this case” and commanded that “[t]his action shall not proceed further unless and until plaintiff notifies the court *416 in writing that he has exhausted state remedies and that he wishes to resume prosecution of this action.” Reynaga appeals the magistrate’s order, including the imposition of the stay.

The power of federal magistrates is limited. See 28 U.S.C. § 636 . Here, because the parties did not consent to the magistrate’s exercise of plenary authority, 2 that officer’s power was confined to the authority granted by 28 U.S.C. § 636 (b)(1). Section 636(b)(1)(A) states that

(emphasis added). Pursuant to § 636(b)(1)(B), a judge may also authorize a magistrate to “conduct hearings, including evidentiary hearings, and to submit to a judge of the court proposed findings of fact, and recommendations for the disposition” of those motions exempted in § 636(b)(1)(A) as well as “applications for posttrial relief made by individuals convicted of criminal offenses.”

The primary difference between subsections (1)(A) and (1)(B) is that the former allows the magistrate to “determine” the matter (subject to the review of the district court for clear or legal error) while the latter allows the magistrate only to submit “proposed findings and recommendations” for the district court’s de novo review. See 28 U.S.C. § 636 (b)(1); see also Taylor v. Oxford, 575 F.2d 152, 154 (7th Cir.1978) (“[I]t was not intended that the magistrate would have the power to hear and determine dispositive motions. It was only intended that a judge could assign a disposi-tive motion to a magistrate for hearing and submission of proposed findings and recommendation to the judge for ultimate disposition. The adjudicatory power over disposi-tive motions was to be exercised only by the judge, but it could be with the assistance and upon the recommendation of the magistrate.”). Under neither section may a magistrate issue a final order directly appealable to the court of appeals: only in subsection (1)(C) cases is that officer vested with such authority. See 28 U.S.C. § 636 (c)(3); supra at 415 n. 1.

Here, the magistrate did not submit proposed findings to the district court: instead, he entered an order that purported to stay Reynaga’s action. It is clear that, in the absence of the parties’ consent on the record to the magistrate’s exercise of such powers, that order was beyond his authority. Subsection (1)(A) specifically exempts “motions for injunctive relief” from the category of pretrial matters upon which a magistrate may enter an order. The Magistrate’s imposition of the stay effectively denied Reynaga’s request for an injunction: it was therefore not authorized under subsection (1)(A). Subsection (1)(B) explicitly states that with respect to “applications for posttrial relief made by individuals convicted of criminal offenses,” magistrates may only “conduct hearings, including evidentiary hearings, and [ ] submit to a judge of the court proposed findings of fact and recommendations for [] disposition”. 3 The Magistrate construed Reyna- *417 ga’s action as presenting precisely such an application: subsection (1)(B) therefore did not afford him the authority to enter a stay in that action or to order the Clerk to close the file until Reynaga exhausted his state remedies. Cf. United States v. Sweeney, 914 F.2d 1260, 1263 (9th Cir.1990) (holding that magistrate had no authority to order Clerk not to report a conviction to California authorities). Finally, the Magistrate’s order was in essence an involuntary dismissal of Reynaga’s action: subsection (1)(A) provides that a magistrate has no authority to enter an order to that effect. See 28 U.S.C. § 636 (b)(1)(A) (stating that magistrates cannot determine motions “for judgment on the pleadings, for summary judgment, ... to dismiss for failure to state a claim upon which relief can be granted, and to involuntarily dismiss an action”).

Although there is no doubt that the magistrate was not authorized to enter the orders that stayed Reynaga’s action, his issuance of those unauthorized orders raises a somewhat difficult question concerning our jurisdiction over Reynaga’s appeal of those orders. Although neither party raises the jurisdictional issue, we have an obligation to consider it sua sponte. See Bender v. Williamsport Area School Dist., 475 U.S. 534, 541 , 106 S.Ct. 1326 ; 1331, 89 L.Ed.2d 501 (1986).

Ordinarily, we have appellate jurisdiction only over “final” orders, see 28 U.S.C. § 1291 , although that is not always the case. See, e.g., 28 U.S.C. § 1292 (interlocutory decisions); 28 U.S.C. § 1292 (a)(1) (injunctions); Carson v. American Brands, Inc., 450 U.S. 79, 84 , 101 S.Ct. 993, 996 , 67 L.Ed.2d 59 (1981) (orders having “the practical effect of refusing an injunction”); Cohen v. Beneficial Loan Corp., 337 U.S. 541 , 69 S.Ct. 1221 , 93 L.Ed. 1528 (1949) (collateral orders); see also Fed.R.Civ.P. 54(b) (partial judgments), In general, stays are not appealable.. See Silberkleit v. Kantrowitz, 713 F.2d 433, 434 (9th Cir. 1983). However, exceptions to that rule exist. See, e.g., Moses H. Cone Memorial Hosp. v. Mercury Const. Corp., 460 U.S. 1, 9-10 , 103 S.Ct. 927, 933-34 , 74 L.Ed.2d 765 (1983) (stays leaving plaintiff “effectively out of court”). In this case, the magistrate was free to recommend to the district court that Reynaga’s action be stayed: if the district court had then adopted the recommendation, we would have jurisdiction over Reynaga’s appeal of the district court’s order because the district court’s action would have “the practical effect of refusing an injunction,” Carson, 450 U.S. at 84 , 101 S.Ct. at 996 , and would have left Reynaga “effectively out of court”. Cone, 460 U.S. at 9-10 , 103 S.Ct. at 933-34 . See also Marchetti v. Bitterolf, 968 F.2d at 964-66 (9th Cir.1992) (holding that appellate jurisdiction exists over district court order staying § 1983 action until plaintiff exhausts habeas corpus remedies).

Here, however, the magistrate did not recommend the imposition of a stay; rather, he imposed it himself. That order was beyond the magistrate’s authority: it was beyond his jurisdiction and was, in essence, a legal nullity. Under such circumstances, it might be argued that because 28 U.S.C. § 636 (b)(1) requires the district court to approve and enter the type of action performed by the magistrate here, the magistrate’s order was not a “final” (or valid) one and hence was not appealable. See Jaliwala v. United States, 945 F.2d 221, 223 (7th Cir.1991) (dismissing appeal for want of jurisdiction because final order entered by magistrate was without explicit consent of parties).

On the other hand, if we conclude that we lack jurisdiction over erroneous orders of the type before us, individuals in Reyna- *418 ga’s situation might suffer serious injustices. The Magistrate entered an order that stayed Reynaga’s action: although that order was legally invalid, there is no indication whatsoever that it was not obeyed by the Clerk. Because the order was entered, and not merely recommended to the district court, Reynaga (a pro se litigant) appealed it to this court. If we dismiss that appeal for lack of jurisdiction, Reynaga will be in a quandary: although the Magistrate’s stay is invalid, because we fail to vacate it, Reynaga may be powerless to prevent individuals from acting in accordance with the Magistrate’s unauthorized order. 4

We need not resolve the difficult issue of whether we have appellate jurisdiction over the direct “appeal” of the order that the magistrate was without authority to enter because we find a sufficient basis for the exercise of appellate jurisdiction under 28 U.S.C. § 1651 . Even if the magistrate’s commands are not “final orders” or appeal-able under one of the exceptions to the final judgment rule, we may nevertheless treat Reynaga’s “appeal” as a petition for a writ of mandamus or prohibition. See Hartland v. Alaska Airlines, 544 F.2d 992, 1001 (9th Cir.1976); United States v. Moore, 368 F.2d 990, 991 (9th Cir.1966) (per curiam). Although mandamus is an exceptional remedy, see Admiral Ins. Co. v. United States District Court, 881 F.2d 1486, 1488-91 (9th Cir.1989); see also In Re Cement Antitrust Litigation, 688 F.2d 1297, 1301 (9th Cir.1982) (noting guidelines for granting mandamus), aff'd for lack of quorum, 459 U.S. 1190 , 103 S.Ct. 1173 , 75 L.Ed.2d 425 459 U.S. 1191 , 103 S.Ct. 1173 , 75 L.Ed.2d 425 (1983), issuance of such a writ is appropriate where, as here, a lower court has exceeded its jurisdiction. See People of the Territory of Guam v. District Court of Guam, 641 F.2d 816, 820 (9th Cir.1981); Hartland, 544 F.2d at 1001 . Compare Marchetti v. Bitterolf 968 F.2d at 967 (9th Cir.1992) (not granting writ of mandamus for stay of discovery in § 1983 action). Because we find that issuance of such a writ is available and appropriate, we need not address the related jurisdictional issue concerning the propriety of Reyna-ga’s purported direct appeal: “the availability of a writ makes it unnecessary to determine whether an immediate appeal is available.” Guam, 641 F.2d at 821 n. 6.

Accordingly, we issue a writ of mandamus vacating the stay. We remand the case to the district court for further proceedings consistent with this opinion.

VACATED AND REMANDED.

. Although the district court’s docket sheet indicates that Reynaga’s action was "assigned” to Judge Shubb and "referred to” Magistrate Hollows, the record contains no order from the district judge authorizing the magistrate to exercise jurisdiction in that action. If no such order, specific or general, exists, the magistrate was not permitted to participate in any way in Reynaga’s action. In view of our disposition of this appeal, however, we need not determine the consequences of the absence of such an order from the record: we will assume for purposes of this appeal that the order exists but was "lost in the shuffle”. United States v. Wilson, — U.S. -,-, 112 S.Ct. 1351, 1355 , 117 L.Ed.2d 593 (1992).

. Section 636(c) grants magistrates, upon the consent of the parties, expansive powers in civil actions, including the power “to conduct any or all proceedings in a jury or nonjury civil matter and order the entry of judgment in the case, when specially designated to exercise such jurisdiction by the district court or courts he serves." 28 U.S.C. § 636 (c)(1). The record does not reflect that any such consent was given here. See also Columbia Record Productions v. Hot Wax Records, Inc., 966 F.2d 515, 516-17 (9th Cir. 1992) (noting that consent must be explicit and on the record). Section 636(a) grants magistrates similar powers in criminal cases involving misdemeanors when the defendant consents in writing to a trial before a magistrate. See 28 U.S.C. § 636 (a); 18 U.S.C. § 3401 .

. That subsection contains an identical limitation for "prisoner petitions challenging conditions of confinement.” We express no opinion on whether Reynaga’s action contained such a *417 claim. Compare McCarthy v. Bronson, — U.S. -,-, 111 S.Ct. 1737, 1740 , 114 L.Ed.2d 194 (1991) (noting evidence that "Congress intended [subsection (1)(B) ] to include in their entirety the two primary categories of suits brought by prisoners — applications for habeas corpus relief pursuant to 28 U.S.C. §§ 2254 and 2255 and actions for monetary or injunctive relief under 42 U.S.C. § 1983”) with Houghton v. Osborne, 834 F.2d 745, 749-50 (9th Cir. 1987) (holding that § 1983 action challenging jail clothing rules is not subject to subsection (1)(B) and noting that "[t]he prison conditions covered by section 636(b)(1)(B) relate to the type of confinement, and matters concerning health, safety, or punishment").

. Reynaga has already taken his case before the district judge, a magistrate, and now this court, all without making any progress in having the substance of his civil rights claim adjudicated. The magistrate’s ultra vires order has halted the proceedings and unnecessarily complicated the ease. Reynaga doubtlessly will have great difficulty reactivating his case unless we act to lift the unauthorized order that stands in his way. He may simply give up, or he may try another futile tactic. Meanwhile, his civil rights case will continue to languish.